[선택정렬] 자바스크립트 SelectionSort

오늘은 거품 정렬 , 삽입 정렬 등 과 함께 3 대장으로 불리는 선택 정렬을 정리해 보겠습니다.

 

선택 정렬 (SelectionSort)

작동원리는 배열에 맨 첫 번째 요소를 작다고 가정하고 그 이후 값들과 비교해 가면서 제일 작은 값의 인덱스를 찾은 후 

그 제일 작은 값을 배열에 첫번째 요소에 넣어줍니다. 

그러면 배열에 첫 번째 요소에는 작은 값이 정렬되어 있으므로 그 이후부터는 배열 첫 요소 이후인 두 번째 요소에 

그다음으로 작은 값을 넣어야 겠죠 ? 이런 식으로 배열을 순회하면서 정렬하는 알고리즘입니다.

 

예시를 들면서 설명하겠습니다. 

 

Example

[6,3,1,2,5]라는 배열이 있다고 가정하겠습니다.

 

1 PASS 

배열에 어느 값이 제일 작은지 알 수 없습니다. 고로 배열에 첫 번째 요소인 6을 제일 작다고 가정합니다.

 [6,3,1,2,5]과 그 뒤에 값들을 다 교하면서 만약 더 작다면 그 값을 최솟값으로 지정해줍니다.

(1) 6과 3을 비교합니다. 3이 더 작기 때문에 최솟값으로 지정해 줍니다.

(2) 3과 1을 비교합니다. 1이 더 작기 때문에 최솟값으로 지정해 줍니다.

(3) 1과 2를 비교합니다. 1이 더 작기 때문에 넘어갑니다.

(4) 1과 5를 비교합니다. 1이 더 작기 때문에 넘어갑니다.

이렇게 비교를 하게 되면 배열중 어느 값이 가장 작은지 알 수 있습니다. 

이렇게 비교로 인해서 알게 된 제일 작은 값을 배열에 첫 번째 값과 교환해 줍니다.. 

->  [1,3,6,2,5]

2 PASS

첫 번째 요소에는 1 PASS로 인해서 제일 작은 값이 들어있을 테니 그 이후에 값들을 비교해 줍니다.

[1,3,6,2,5] 

(1) 3과 6을 비교합니다. 3이 더 작기 때문에 넘어갑니다.

(2) 3과 2를 비교합니다. 2가 더 작기 때문에 최솟값에 2를 넣어줍니다.

(3) 2와 6을 비교합니다. 2가 더 작기 때문에 넘어갑니다.

첫 번째 값은 정렬되어 있기 때문에 그 이후 두 번째 자리에 최솟값 2를 교환해줍니다..

-> [1,2,6,3,5]

3 PASS

첫 번째 두 번째 요소는 정렬이 되어 있으므로 3번째 요소를 정렬을 해 줍니다.

[1,2,6,3,5]

(1) 6과 3을 비교합니다. 3이 더 작기 때문에 최솟값으로 3을 지정해 줍니다.

(2) 3과 5를 비교합니다. 3이 더 작기 때문에 넘어갑니다.

최솟값인 3과 6을 교환해 줍니다.

-> [1,2,3,6,5]

4 PASS

[1,2,3,6,5] 

(1) 6과 5를 비교합니다. 5가 더 작기 때문에 최솟값에 5를 넣어줍니다.

최솟값 5와 6을 교환해 줍니다.

-> [1,2,3,5,6]

 

4번까지만 비교하는 이유는 5개 숫자 중 4개가 정렬되면 나머지 하나는 자동 정렬된 거기 때문에 불필요한 

계산을 해줄 필요가 없습니다.

 

자바스크립트 코드 

function SelectionSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    console.log(`${i + 1}PASS >> `, arr);
  }
  return arr;
}

console.log(SelectionSort([6, 3, 1, 2, 5]));

첫 번째 for : 각각 PASS 과정을 진행해 주는 반복문입니다. 

배열 길이 - 1 해주는 이유는 5개 중 4개가 정렬되면 나머지 하나는 자동 정렬이기 때문입니다.

 

minIdx = i : 배열에 첫 번째 요소를 제일 작다고 가정합니다.

 

두 번째 for : 최솟값으로 가정한 minIdx 값들과 그 이후 값들을 비교하는 부분입니다.

j = i + 1 : 이 부분은 첫 번째 요소를 제일 작다고 가정했기 때문에 그 이후 값들과 비교하면 됩니다.

 

if (arr [j] < arr [minIdx]): 만약 minIdx로 지정한 값이 j 값 보다 크다면 j 값이 더 작 다는 거기 때문에 

최솟값 인덱스를 바꿔줘야 합니다. 

 

[arr [i], arr [minIdx]] = [arr [minIdx], arr [i]] 

- for 문이 끝난 후 최소 값을 찾으면 i 번째 인덱스랑 최솟값으로 찾은 인덱스를 서로 교환해줍니다.

 

for문이 끝나면 정렬이 완료된 배열을 리턴해 줍니다.

결과 

 

시간 복잡도는O(N**2)입니다.