JavaScript 알고리즘 (1) 선택 정렬 (Selection Sort)

 

 

 

예전에는 알고리즘을 생각해볼 여유도 없이 프로그래밍 언어와 문법 위주로만 공부하기 바빳다. 

알고리즘까지 배울 레벨과 여력이 안된다고 생각하여 주위에서 중요성을 설파할 때면 귓등으로 넘긴 것 같다.

코딩테스트를 그때그때 머리에 의존하여 풀어내면서 이제서야 알고리즘에 대한 중요성을 확실히 깨달았다. 

하지만 자바스크립트로 푸는 알고리즘 자료는 많이 없다. 아마도 자바스크립트 언어 특성상 파이썬이나 자바에 비해 자료구조 등을 효율적으로 쉽게 풀어내기가 어려워서라고 생각한다. 그렇지만 포기는 없다. 자 그럼 이제부터 한걸음씩 시작해보자.

 

updated 06/09/24

알고리즘 강의를 2번째 보고있는 중이다. 개념과 이해는 어느정도 잡혔지만

어느날 누군가 나에게 던진 질문처럼 이 알고리즘이 왜 사용해야하는지에 대한 답은 아직도 찾고 있다.

하지만 확실히 알고리즘은 개발 능력에 도움이 되며 논리적이고 타당한 사고방식의 원천이 되는 것 같다.

다음에는 전체적으로 구조적으로 알고리즘 별로 비교 분석할 수 있는 여유가 생기는 그날이 오기를 바란다.

 

 

---

JavaScript 알고리즘 (1) 선택 정렬 (Selection Sort)

 

정렬알고리즘 중 선택 정렬은 가장 작은 것을 선택해서 앞으로 보낸다.

원소 중에서 가장 작은 것을 선택해서 제일 앞으로 보내자!

 

 

뒤죽박죽인 배열 내의 숫자들을 오름차순(1, 2, 3, ... 10)으로 정렬해보자

자, 준비물은 array, min, index, temp 다. 이 변수들 안에 숫자들을 담아 능력껏 줄세워보자.

 

첫번째 원소자리에는 1st - 10th 원소 검사해서 젤 작은 수를 맨앞으로 넣고,

두번째 원소자리에는 2nd - 10th 원소 검사해서 젤 작은 수를 맨앞으로 넣고,

세번째 원소자리에는 3rd - 10th 원소 검사해서 젤 작은 수를 맨앞으로 넣고,

 

1. 일단 for문으로 array 를 크게 한바퀴 돌면서, (1차 for문) 

2. 그 안에서 남는 애들로 원소 검사 한바퀴 또 돌면서 최소값 찾고 (2차 for문)

3. 찾은 최소값과 현재 원소를 바꿔치기 해주는 거다.

let array = [1, 10, 5, 8, 7, 6, 4, 3, 2, 9]; //오름차순 정렬할 배열
let min;   	//최소값
let index; 	//최소값의 인덱스#
let temp;  	//두 숫자(현재 값이랑 최소값)를 바꿔치기하는 임시장소

// 1. 포문으로 배열을 검사한다.
for (let i = 0; i < 10; i++){
  min = 9999; 	// array의 모든 원소보다 큰 숫자로 정의
  
 // 2. 2차원 포문으로 최소값 찾기
  for (let j = i; j < 10; j++) {
    if (min > array[j]){ // 만약 현재 원소(min)가 현재 검사순서인 값(array[j])보다 작다면
      min = array[j]; 	 // 현재 원소(min)의 값을 array[j]로 바꿔치기! 한다	
      index = j;	 // index 값은 j로 넣어주고요
    }
  }

  // 3. 배열 안 두 원소 스와칭
  temp = array[i]; 	   // temp에 현재 검사값 넣기
  array[i] = array[index]; // 인덱스i를 위에서 정의한 index값으로 바꿔치기
  array[index] = temp;	   // index에 위치한 array 원소값을 temp에 넣기 
}

 

 

 

자, 이제 선택 정렬을 함수로 만들어보자 

function selectionSort(arr){
  for(var i = 0; i < arr.length; i++){
    var lowest = i;    // 제일 작은 값일 때의 인덱스 저장할 공간 (inner for문 한바퀴 돌고는 i로 리셋)
    
    for(var j = i + 1; j < arr.length; j++){ // j 는 i 다음 인덱스이다 (i랑 j랑 겹치지 않도록)
      if(arr[j] < arr[lowest]){  	     // arr[j] 값이 < 가장 작은 값(lowest)보다 작으면
        lowest = j; 			     // 이구역의 작은 값의 인덱스는 j가 된다.
      }
            
      if(i !== lowest){ // i 와 lowest 값이 같으면 굳이 자리를 바꿀(swap) 필요가 없다
        // SWAP!
        var temp = arr[i];
        arr[i] = arr[lowest];
        arr[lowest] = temp;
      }
    }
  }
}

selectionSort([0, 2, 34, 22, 10, 19, 17])

 

 

 

outer For문을 도는 과정을 콘솔로 찍어보았다.

포문을 다돌면 가장 작은 수(옥석)을 가려내고 i 의 첫 자리(왕좌)에 앉게 된다.

그렇게 1대 2대 3대 ...  왕좌에 앉을 작은 수가 결정되고, 배열은 오름차순 정렬이 되어간다.., 는 해피엔딩

 

 

 

선택정렬은 검사를 꽤 많이 하기 때문에 그렇게 효율적이진 않다.

이중루프로 구성되며 시간복잡도는 O(N^2) 이다. 

어려워보이는데 O는 시간을 표현하는 방식 N^2는 N의 제곱을 뜻한다.

 

데이터 입력상태에 민감하지 않다. 입력 데이터가 어 상태의 순서를 갖는지에 무관하게 언제나 동일한 수행시간 O(n2) 를 갖는다.

제자리 정렬 알고리즘 이다. 입력데이터가 저장공간 이외에 별도의 공간을 상수개로만 사용한다.

불안정 정렬 알고리즘이다.  

 

ref: https://www.youtube.com/playlist?list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz