ZeroCho Blog

안녕하세요. 이번 시간에는 버블 정렬만큼 간단하고 성능도 안 좋은 선택 정렬에 대해 알아보겠습니다.

성능이 좋지 않아도 배우는 이유는 코드가 간단하고, 작은 수(보통 30 이하)에서는 효과적이기 때문입니다. 성능이 좋다고 표현되는 정렬들은 오히려 30 이하의 작은 수에서는 성능이 안 좋은 경우가 많습니다. (다른 정렬들이 작은 수에서도 성능이 좋았으면 아무도 버블 정렬, 선택 정렬, 삽입 정렬을 쓰지 않았겠죠? 버블 정렬은 쓰지 맙시다.)

선택 정렬은 배열을 처음부터 훑어서 가작 작은 수를 제일 앞에 가져다 놓습니다. 그 다음, 다시 배열을 훑어서 두 번째로 작은 수를 두 번째 칸에 가져다 놓습니다. 계속 반복해서 끝까지 정렬합니다. 성능이 안 좋을 수밖에 없는 게, 배열을 한 번 훑었을때 숫자 하나밖에 정렬을 못 합니다. 하지만 사람이 정렬을 하는 방법과 상당히 유사합니다. 간단히 예제를 보죠.

[5,1,4,7,2,6,8,3] 배열을 처음부터 훑어 가장 작은 1을 앞으로 보냅니다.
[1,5,4,7,2,6,8,3] 다시 훑어 2를 앞으로 보냅니다.
[1,2,4,7,5,6,8,3] 3을 앞으로
[1,2,3,7,5,6,8,4]
[1,2,3,4,5,6,8,7]
[1,2,3,4,5,6,8,7]
[1,2,3,4,5,6,7,8] 정렬 끝

버블 정렬처럼 무식한 방법이긴 하지만 직관적이네요. 성능은 O(n^2)입니다. 코드로 볼까요?

var selectionSort = function(array) {
  var length = array.length;
  var minIndex, temp, i, j;
  for (i = 0; i < length - 1; i++) { // 처음부터 훑으면서
    minIndex = i;
    for (j = i + 1; j < length; j++) { // 최솟값의 위치를 찾음
      if (array[j] < array[minIndex]) {
        minIndex = j;
      }
    }
    temp = array[minIndex]; // 최솟값을 저장
    array[minIndex] = array[i];
    array[i] = temp; // 최솟값을 제일 앞으로 보냄
  }
  return array;
};

selectionSort([5,1,4,7,2,6,8,3]); // [1,2,3,4,5,6,7,8]

역시나 반복문을 두 번 중첩해서 돌고 있는 것을 확인할 수 있습니다. 하지만 이 정도는 보통 사람들도 배우지 않고도 만들 수 있다는 점에서, 활용하기 좋습니다. 또 return 값이 array라 메모리를 추가적으로 사용하지 않습니다.

다음 시간에는 퀵 정렬에 대해 알아보겠습니다. 정렬 기법 중 반드시 알아야할 정렬입니다. 하지만 어려우니 집중하셔야 할 겁니다!