정렬 1: 버블, 선택, 삽입 정렬

선택 정렬은 값 10개짜리 목록이라면 섞여 있든 이미 정렬되어 있든 정확히 45번 비교합니다.

순서대로 놓기

정렬은 목록을 작은 값에서 큰 값 순서로(또는 이름, 날짜, 가격처럼 비교할 수 있는 어떤 순서로든) 다시 늘어놓는 일입니다. 휴대전화의 연락처, 관련도 순으로 늘어선 검색 결과, 날짜순으로 정렬한 스프레드시트 열처럼 컴퓨터가 가장 자주 하는 일 가운데 하나입니다. 정렬해 두면 다른 일도 쉬워집니다. 앞 단원에서 본 것처럼 정렬된 목록에는 이진 탐색을 쓸 수 있고, 같은 값은 서로 붙어 있게 됩니다.

이 단원에서는 쉬운 방법 세 가지를 다룹니다. 셋 다 한 번에 두 값을 비교하고 같은 목록 안에서 값을 옮깁니다. 짧게 쓸 수 있고 따라가기 쉽지만, 셋 다 목록이 길어지면 급격히 느려집니다. 왜 느려지는지 지켜보는 것이 다음 단원의 빠른 방법을 이해하는 가장 좋은 준비입니다. 내내 두 가지를 셉니다. 비교(「이 값이 저 값보다 큰가?」를 묻는 것)와 교환(두 값을 맞바꾸는 것)입니다.

버블 정렬: 순서가 틀린 이웃을 바꾸기

버블 정렬은 목록을 따라가며 이웃한 두 값을 차례로 비교합니다. 왼쪽 값이 더 크면 둘을 바꿉니다. 한 번 끝까지 훑고 나면 가장 큰 값이 거품이 떠오르듯 한 칸씩 밀려 맨 오른쪽에 닿고, 다시는 움직일 필요가 없습니다. 다음 훑기는 한 칸 앞에서 멈춰도 됩니다. 흔히 덧붙이는 개선은 교환이 한 번도 없는 훑기를 알아차리는 것입니다. 그렇다면 모두 이미 제자리이므로 일찍 멈춰도 됩니다.

[5, 1, 4, 2, 8]로 따라가 봅니다. 첫 훑기에서 5와 1(교환), 5와 4(교환), 5와 2(교환), 5와 8(그대로)을 비교하면 목록은 [1, 4, 2, 5, 8]이 되고 8이 제자리에 놓입니다. 두 번째 훑기에서 1과 4, 4와 2(교환), 4와 5를 비교하면 [1, 2, 4, 5, 8]이 됩니다. 세 번째 훑기는 1과 2, 2와 4를 비교하고 교환이 없으니 멈춥니다. 모두 4 + 3 + 2 = 9번 비교하고 4번 교환했습니다.

function bubbleSort(a) {
  for (let pass = 0; pass < a.length - 1; pass++) {
    let swapped = false;
    for (let j = 0; j < a.length - 1 - pass; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];  // swap
        swapped = true;
      }
    }
    if (!swapped) break;  // already sorted
  }
  return a;
}

선택 정렬: 가장 작은 값을 찾아 다음 자리에

선택 정렬은 많은 사람이 손에 든 카드를 정리하는 방식과 같습니다. 목록 전체에서 가장 작은 값을 찾아 첫 자리로 바꿔 넣습니다. 나머지에서 가장 작은 값을 찾아 둘째 자리로 바꿔 넣고, 이렇게 계속합니다. [5, 1, 4, 2, 8]이라면 첫 훑기에서 1을 찾아 5와 바꾸고, 둘째 훑기에서 2를 찾아 5와 바꿉니다. 마지막 두 번은 4와 5가 이미 제자리입니다. 교환은 2번뿐이지만 훑으면서 비교는 4 + 3 + 2 + 1 = 10번 합니다.

선택 정렬은 일찍 멈추는 법이 없습니다. 이미 정렬된 목록이라도 가장 작은 값인지 확인하려면 남은 값을 모두 봐야 합니다. 값이 n개면 비교 횟수는 언제나 (n − 1) + (n − 2) + … + 1 = n(n − 1)/2입니다. 10개면 45번, 100개면 4,950번, 1,000개면 499,500번입니다. 장점은 교환이 적다는 것입니다. 많아야 n − 1번이라서 값을 옮기는 데 비용이 클 때 쓸모가 있습니다.

삽입 정렬: 새 값을 제자리로 밀어 넣기

삽입 정렬은 목록의 왼쪽 부분을 정렬된 상태로 두고, 그 부분을 값 하나씩 늘려 갑니다. 다음 값을 꺼내 왼쪽 이웃이 더 크지 않을 때까지 이웃과 바꾸며 왼쪽으로 옮깁니다. 그러면 그 값은 정렬된 값들 사이에서 제자리를 찾습니다. 거의 정렬된 목록에서는 새 값이 한두 칸만 움직이므로 삽입 정렬이 아주 빠릅니다. [5, 1, 4, 2, 8]에서는 비교 7번, 교환 4번입니다.

교환 세기: 뒤바뀐 쌍

버블 정렬과 삽입 정렬이 몇 번 교환할지 미리 알아내는 깔끔한 방법이 있습니다. 서로 순서가 뒤바뀐 두 값의 쌍을 역순 쌍이라고 하는데, 이 쌍을 세면 됩니다. [5, 1, 4, 2, 8]의 역순 쌍은 (5, 1), (5, 4), (5, 2), (4, 2)로 모두 넷입니다. 순서가 틀린 이웃 둘을 바꾸면 역순 쌍이 정확히 하나 없어지고 새로 생기지는 않으므로, 두 방법 모두 정확히 4번 교환합니다. 거꾸로 놓인 값 n개는 모든 쌍이 뒤바뀌어 있어 역순 쌍이 n(n − 1)/2개이고, 이것이 최악의 경우입니다.

칸마다 비교 횟수 / 교환 횟수입니다. 예시 목록은 [5, 1, 4, 2, 8]입니다. 버블 정렬은 교환이 없는 훑기 뒤에 멈추는 방식입니다.

세 방법에는 같은 약점이 있습니다. 최악의 경우 거의 모든 값의 쌍을 비교하므로 비교가 약 n²/2번입니다. 목록이 두 배가 되면 일은 네 배가 됩니다. 열 배면 백 배입니다. 값이 수십 개라면 별 문제가 없지만, 100만 개라면 감당할 수 없습니다. 다음 단원에서 훨씬 나은 방법을 봅니다.