최솟값을 찾는 끈기

크리스는 방금 배운 버블 정렬로 100개의 데이터를 정렬해 보았다.

결과는 충격적이었다. 운이 나쁘면 정렬을 완료하기 위해 수천 번이나 자리를 바꾼다(Swap).

"아니, 그냥 가장 작은 숫자를 찾아서 맨 앞으로 딱 한 번만 옮기면 되는 거 아니야?"

"왜 굳이 옆 친구랑 계속 자리를 바꾸면서 힘을 빼지?"

크리스의 직관은 정확했다. 버블 정렬의 무식한 교환 횟수를 획기적으로 줄인 방식, 바로 선택 정렬(Selection Sort)이다.

1. "딱 너만 골라서 데려올게"

선택 정렬의 아이디어는 매우 인간적이다. 우리가 카드 정리를 할 때 무의식적으로 쓰는 방법과 비슷하다.

버블 정렬이 "내 옆에 있는 애보다 내가 크면 바꾼다"라면,

선택 정렬은 "일단 끝까지 훑어보고 제일 작은 녀석을 선택(Selection)해서 데려온다"이다.

2. 자바스크립트로 구현하기

코드로 구현할 때는 "현재까지 발견된 최솟값의 위치(인덱스)"를 기억하는 변수가 필요하다.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 1. 일단 현재 위치(i)가 제일 작다고 가정한다.
    let lowest = i;
    
    // 2. i+1부터 끝까지 돌면서 진짜 최솟값을 찾는다.
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[lowest]) {
        lowest = j; // "찾았다! 네가 새로운 최솟값이야."
      }
    }

    // 3. 만약 최솟값이 현재 위치(i)가 아니라면 교환한다.
    // (자기 자신이 최솟값인데 굳이 바꿀 필요는 없으니까)
    if (i !== lowest) {
      console.log(`Swap: {arr[i]} <-> {arr[lowest]}`);
      [arr[i], arr[lowest]] = [arr[lowest], arr[i]];
    }
  }
  return arr;
}

selectionSort([34, 22, 10, 19, 17]);

3. 성능 분석: 버블 정렬보다 나은가?

이 코드의 시간 복잡도를 계산해 보자.

결론적으로 시간 복잡도 자체는 O(N^2)로 버블 정렬과 같아서 데이터가 많아지면 여전히 느리다.

하지만 "쓰기(Write/Swap)" 연산이 매우 비싼 메모리 환경이라면, 선택 정렬이 버블 정렬보다 훨씬 효율적일 수 있다.

4. 선택 정렬의 치명적인 단점

선택 정렬은 치명적인 단점이 하나 있는데, 바로 불안정 정렬(Unstable Sort)이라는 점이다.

같은 값(예: [3, 3])이 있을 때, 정렬 과정에서 뒤에 있던 3이 앞으로 튀어나와 순서가 뒤집힐 수 있다.

(예: [5, 5, 1]을 정렬할 때, 맨 앞의 5가 1과 자리를 바꾸면서 뒤에 있던 5보다 뒤로 가게 된다.)

핵심 정리

이제 우리는 "큰 수를 뒤로 보내기(버블)"와 "작은 수를 앞으로 가져오기(선택)"를 배웠다.

그런데 우리가 카드 게임을 할 때 실제로 쓰는 방법은 따로 있다. 카드를 한 장씩 집어서 "적절한 위치에 꽂아 넣는" 방식이다.

데이터가 거의 정렬되어 있을 때, 현존하는 정렬 알고리즘 중 가장 빠르다는 삽입 정렬(Insertion Sort)을 만나보자.

🔗 참고 링크