§ 1 · 가장 작은 값 고르기선택 정렬의 절차
선택 정렬(selection sort)은 버블 정렬과 또 다른 정렬 알고리즘이다. 둘이 빅 오로 어떻게 비교되는지가 이 장의 핵심이다.
① 최솟값 찾기 — 각 셀을 왼쪽에서 오른쪽으로 확인하며 가장 작은 값의 인덱스를 변수에 추적한다.
② 교환 — 최솟값 인덱스를 찾으면, 그 값을 패스스루를 시작한 인덱스의 값과 교환한다.
③ 반복 — 모든 데이터가 정렬될 때까지 ①②를 반복한다. 패스스루마다 시작 인덱스가 한 칸씩 오른쪽으로 간다.
§ 2 · 한 단계씩선택 정렬 실행
배열 [4, 2, 7, 1, 3]을 선택 정렬한다. 한 패스스루 동안 가장 작은 값을 추적하다가, 끝에서 단 한 번 교환한다.
function selectionSort(array) { for(var i = 0; i < array.length; i++) { var lowestNumberIndex = i; for(var j = i + 1; j < array.length; j++) { if(array[j] < array[lowestNumberIndex]) { lowestNumberIndex = j; } } if(lowestNumberIndex != i) { var temp = array[i]; array[i] = array[lowestNumberIndex]; array[lowestNumberIndex] = temp; } } return array; }
§ 3 · 절반의 교환선택 정렬의 효율성
선택 정렬도 비교와 교환으로 이루어진다. 비교는 버블 정렬과 같이 (N-1) + (N-2) + … + 1번이다. 그러나 교환은 패스스루당 최대 한 번뿐이다 — 버블 정렬이 최악의 경우 모든 비교마다 교환했던 것과 대조된다.
| N 요소 | 버블 정렬 | 선택 정렬 |
|---|---|---|
| 5 | 20 | 14 (비교 10 + 교환 4) |
| 10 | 90 | 54 (비교 45 + 교환 9) |
| 20 | 380 | 199 (비교 180 + 교환 19) |
| 80 | 6320 | 3239 (비교 3160 + 교환 79) |
선택 정렬은 버블 정렬의 약 절반 단계만 거친다 — 두 배 빠르다.
§ 4 · 두 규칙상수 무시하기
그런데 빅 오의 세계에서 선택 정렬과 버블 정렬은 정확히 똑같이 O(N²)로 설명된다. 선택 정렬의 단계 수는 대략 N² / 2처럼 보이지만, 빅 오는 그렇게 쓰지 않는다.
§ 5 · 분류기빅 오의 역할
빅 오가 상수를 무시하는 이유 — 빅 오의 목적은 알고리즘의 장기적 성장률을 분류하는 것이다. 어떤 양의 데이터에서든 O(N)은 결국 O(N²)보다 빠르고, O(100N)조차 어느 지점부터 O(N²)보다 영원히 빠르다. 그 지점이 정확히 언제인지는 빅 오의 관심사가 아니다.
그러나 이 장의 핵심은 이것이다 — 두 알고리즘이 같은 빅 오 등급이라고 같은 속도인 것은 아니다. 버블 정렬과 선택 정렬은 둘 다 O(N²)이지만 선택 정렬이 두 배 빠르다. 같은 등급 안에서는 추가 분석이 필요하다.
every_other 예제처럼, each_with_index로 N번 조회하고 N/2번 삽입하는 코드(1.5N 단계)와, while로 한 칸씩 건너뛰며 N/2번만 조회하는 코드(N 단계)는 둘 다 O(N)이다. 그러나 후자가 1.5배 빠르다 — 빅 오가 못 보는 차이다.
§ 6 · 정리이 장이 남긴 것
빅 오는 서로 다른 등급의 알고리즘을 대조하는 데 완벽하다. 그러나 같은 등급에 속한 둘을 비교할 때는 단계 수를 직접 세는 추가 분석이 필요하다. 그리고 지금까지 우리는 줄곧 최악의 경우만 봤다. 다음 장에서는 평균과 최선의 경우까지 본다.