C++로 쉽게 풀어쓴 자료구조/ 정렬

정렬이란?

정렬(sorting)은 물건을 크기순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것을 말한다.

일반적으로 정렬시켜야 될 대상은 레코드(record)라고 불린다. 레코드는 다시 필드(field)라고 하는 보다 작은 단위로 나누어진다. 예컨대 학생들의 레코드에는 이름, 학번, 주소, 전화번호 등이 필드가 될 것이다. 여러 필드 중에서 특별히 레코드와 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 한다. 학생들의 레코드의 경우에는 학번이 키가 될 수 있다.

정렬 알고리즘의 분류

정렬 알고리즘은 다음의 2가지 그룹으로 나눌 수 있다.

  • 단순하지만 비효율적인 방법 – 삽입 정렬, 선택 정렬, 버블 정렬 등
  • 복잡하지만 효율적인 방법 – 퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬 등

정렬 알고리즘을 내부 정렬(internal sorting)과 외부 정렬(external sorting)으로 구분할 수도 있다. 내부 정렬은 정렬하기 전에 모든 데이터가 메인 메모리에 올라와 있는 정렬을 의미한다. 반면 외부 정렬은 외부 기억장치에 대부분의 데이터가 있고 일부만 메모리에 올려놓은 상태에서 정렬하는 방법이다. 여기서는 내부 정렬만을 다루기로 한다.

선택 정렬

선택 정렬의 원리

선택 정렬(selection sort)은 가장 이해하기 쉬운 정렬 방법이다. 정렬이 안 된 리스트에서 최솟값이 선택되면 이 값을 배열의 첫 번째 요소와 교환한다. 이렇게 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법을 제자리 정렬(in-place sorting)이라고 한다.

선택 정렬 알고리즘

선택 정렬의 유사 코드는 다음과 같다. 요소의 개수가 n이면 최솟값을 찾고 교환하는 과정은 n-1번만 반복하면 된다.

selectionSort(A, n)
    for i <- 0 to n-2 do
        least <- A[i], A[i+1], ... A[n-1] 중에서 가장 작은 값의 인덱스;
        A[i]와 A[least]의 교환;
        i++

선택 정렬의 시간 복잡도 분석

선택 정렬의 성능 분석을 위하여 비교횟수와 이동횟수를 따로 구해보자. 먼저 비교횟수를 구하기 위하여 두 개의 for 루프의 실행횟수를 계산해 보자. 외부 루프는 n-1번 반복한다. 내부 루프는 0에서 n-2까지 변하는 i에 대하여 (n-1)-i번 반복한다. 키값들의 비교가 내부 루프 안에서 이루어지므로 전체 비교 횟수는 다음과 같다.

(n-1) + (n-2) + ... + 1 = n(n-1) / 2 = O(n2)

레코드 교환은 외부 루프의 실행횟수만큼 이루어지고, 한번 교환하기 위하여 3번의 이동이 필요하므로 전체 이동횟수는 3(n-1)이 된다.

선택 정렬의 장점은 자료 이동 횟수가 미리 결정된다는 점이다. 그러나 전체 시간 복잡도가 O(n2)이므로 효율적인 알고리즘은 아니다. 또 하나의 문제점은 안정성을 만족하지는 않는다는 점이다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

삽입 정렬

삽입 정렬의 원리

삽입 정렬(insertion sort)은 손 안의 카드를 정렬하는 방법과 유사하다. 즉, 카드를 한 장씩 받을 때 새로운 카드를 먼저 받아 정렬한 카드들 사이의 올바른 자리에 넣는 것이다. 이것을 새로 받는 모든 카드에 대해 수행하면 전체 카드가 정렬된다.

배열에서 생각해 보자. 삽입 정렬은 그림 13.10과 같이 배열에서 정렬이 되지 않은 부분의 숫자를 정렬된 부분의 적절한 위치에 삽입하는 과정을 반복한다. 선택 정렬과 마찬가지로 추가적인 배열을 사용하지 않고 입력 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누어서 사용하면 된다.

정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단한 후 해당 위치에 이 숫자를 삽입하게 되면, 정렬된 부분의 크기는 하나 커지게 되고, 정렬이 되지 않은 부분의 크기는 하나 줄어들게 된다. 이러한 삽입 연산을 정렬되지 않은 요소가 없을 때까지 반복하면 전체 리스트가 정렬된다.

삽입 정렬의 알고리즘

insertionSort(A, n)
    for i <- 0 to n-1 do
        key <- A[i];
        j <- i-1;
       while j ≥ 0 and A[j] > key do
           A[j+1] <- A[j];
           j <- j-1;
       A[j+1] <- key;

삽입 정렬의 시간 복잡도 분석

삽입 정렬의 복잡도는 입력 자료의 구성에 따라 달라진다. 먼저 입력 자료가 이미 정렬되어 있는 경우는 가장 빠르다. 삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 1번의 비교와 2번의 이동만 이루어지므로 총 비교횟수는 n-1번, 총 이동횟수는 2(n-1)번이 되어 알고리즘의 시간 복잡도는 O(n)이다.

최악의 경우는 입력자료가 역으로 정렬된 경우이다. 각 단계에서 앞에 놓인 자료들은 전부 한 칸씩 뒤로 이동하여야 한다. 따라서 외부 루프 안의 각 반복마다 i번의 비교가 수행되므로 총 비교횟수는 다음과 같다.

총 이동횟수는 외부 루프의 각 단계마다 i+2번의 이동이 이루어지므로 다음과 같다.

n(n-1)/2 + 2(n-1) = (n2 + 3n – 4) / 2 = O(n2)

버블 정렬

버블 정렬의 원리

버블 정렬(bubble sort)은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 방법이다. 이러한 비교-교환 과정은 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 비교-교환 과정이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이것은 마치 물속에서 거품이 보글보글 떠오르는 것과 유사하여 버블 정렬이라 부른다. 비교-교환 과정은 더 이상 교환이 일어나지 않을 때까지 계속된다.

그림 13.13은 버블 정렬의 한 번의 스캔 과정을 보여준다. 먼저 5와 3을 비교하면 5가 더 크므로 서로 교환하고, 다음으로 5와 8을 비교하면 8이 더 크므로 교환 없이 다음 단계로 진행한다. 이러한 과정이 반복되면 8이 리스트의 가장 오른쪽 끝으로 이동하게 된다.

버블 정렬의 알고리즘

BubbleSort(A, n)
    for i <- n-1 to 1 do
        for j <- 0 to i-1 do
            j와 j+1번째의 요소가 크기순이 아니면 교환;
            j++;
         i++;

버블 정렬의 시간 복잡도 분석

버블 정렬의 비교횟수는 최상, 평균, 최악의 어떤 경우에도 항상 일정하고 다음과 같다.

자료의 이동 횟수의 경우, 최악의 경우는 입력 자료가 역순으로 정렬되어 있는 경우에 비교 연산 횟수의 3배가 발생하고, 최상의 경우는 입력 자료가 이미 정렬되어 있는 경우로 자료 이동이 한 번도 발생하지 않는다. 따라서 전체적인 시간 복잡도는 O(n2)이다.

셀 정렬

셀 정렬의 원리

셀 정렬(shell sort)은 Donald L. Shell이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안했다. 삽입 정렬의 최대 문제점은 요소들이 삽입될 때 이웃한 위치로만 이동한다는 것이다. 만약 삽입할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야 한다. 셀 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.

삽입 정렬과 달리 셀 정렬은 전체 리스트를 한꺼번에 정렬하지 않는다. 리스트를 일정한 기준에 따라 분류해 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용해 정렬한다. 모든 부분 리스트가 정렬되면 셀 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만들어 앞의 과정을 되풀이 한다.

각 부분 리스트는 전체 리스트에서 거리가 k만큼 떨어진 요소들로 이루어진다. 이 k를 간격(gap)이라고 한다. 셀 정렬에서는 큰 간격으로 시작해서 각 단계마다 간격 k를 줄이는데, 이에 따라 하나의 부분 리스트에 속하는 요소의 개수는 증가된다. 마지막 단계는 간격이 1이 된다.

그림 13.15는 k=5인 경우의 부분 리스트의 정렬 과정을 보여준다. 먼저 (a)와 같이 입력 리스트의 각 5번째 요소를 추출하여 부분 리스트들을 만든다. 첫 번째 부분 리스트는 10, 3, 16을 포함하고 있고 두 번째 부분 리스트는 8, 22를 포함하고 있고 이런 식으로 부분 리스트들이 구성된다. 이러한 부분 리스트에 대해 삽입 정렬이 수행되는데, (b)와 같이 부분 리스트들이 정렬되면 전체 리스트도 약간 정렬된 것에 주목하라. 부분 리스트나 삽입 정렬을 위해 추가적인 공간이 필요하지는 않다.

첫 번쨰 패스가 끝나면 비슷한 방식으로 다시 부분 리스트를 구성하는데 이번에는 간격을 1/2 줄여서 입력 배열의 각 2번째 요소를 추출하여 부분 리스트를 만든다. 간격은 처음에는 n/2 정도로 하고 각 패스마다 간격을 절반으로 줄이는 방식을 많이 사용한다.

셀 정렬의 분석

셀 정렬은 삽입 정렬에 비해 2가지 이점이 있다.

  • 연속적이지 않은 부분 파일에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 반면 삽입 정렬에서는 한 번에 한 칸씩만 이동된다. 따라서 교환되는 아이템들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.
  • 부분 리스트가 하나가 되면 셀 정렬은 전체 리스트를 정렬해야 한다. 그러나 삽입 정렬이 거의 정렬된 리스트에 대해 매우 효율적이므로 이 과정도 빠르게 수행된다.

실험적인 연구를 통하여 셀 정렬의 시간 복잡도는 최악의 경우에는 O(n2)이지만 평균적인 경우에는 O(n1.5)인 것으로 알려져있다.

합병 정렬

합병 정렬의 개념

합병 정렬(merge sort)은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법이다. 이것은 분할 정복(divide and conquer) 기법에 바탕을 두고 있는데, 하나의 문제를 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

합병 정렬은 다음의 단계들로 이루어진다.

  1. 분할(Divide): 입력 배열을 같은 크기의 2개 부분 배열로 분할한다.
  2. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다.
  3. 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 통합한다.

합병 정렬 알고리즘

mergeSort(A, left, right)
    if left < right
        mid = (left + right) / 2;
        mergeSort(A, left, mid);
        mergeSort(A, mid+1, right);
        merge(A, left, mid, right);

합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병(merge)하는 단계이다. 합병 방법을 생각해 보자. 합병은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 요소 중에서 더 작은 요소를 새로운 리스트로 옮긴다. 두 리스트 중에서 하나가 모두 끝날 때까지 이 과정을 반복한다. 하나의 리스트가 먼저 끝나면 나머니 리스트의 요소들을 전부 새로운 리스트로 복사한다.

merge(A, left, mid, right)
    b1 <- left;
    e1 <- mid;
    b2 <- mid+1;
    e2 <- right;
    sorted 배열을 생성;
    index <- 0;
    while b1 ≤ e1 and b2 ≤ e2 do
        if(A[b1] < A[b2]) then
            sorted[index] <- A[b1];
            b1++;
            index++;
        else
            sorted[index] <- A[b2];
            b2++;
            index++;
    요소가 남아 있는  부분 배열을 sorted로 복사한다;
    sorted를 A로 복사한다.

합병 정렬의 복잡도 분석

합병 정렬은 순환 호출 구조로 되어 있다. 따라서 레코드의 개수 n이 2의 거듭제곱이라고 가정하고 순환 호출의 깊이가 얼마나 되는지를 분석해보자. 만약 n = 23인 경우에는 부분 배열의 크기가 23 -> 22 -> 21 -> 20 순으로 줄어들어 순환 호출의 깊이가 3임을 알 수 있다. 따라서 일반적으로 n = 2k라고 하면 부분 배열의 크기는 2k -> 2k-1 -> … -> 20이 되어 순환 호출의 깊이가 k가 된다. 이때, k = log2n가 된다.

배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산은 수행되지 않는다. 부분 배열이 합쳐지는 merge 함수에서 비교 연산과 이동 연산이 수행되는 것이다. 순환 호출의 깊이만큼의 합병 단계가 필요하다. 그러면 각 합병 단계에서는 몇 번의 비교 연산이 수행될까? 그림 13.17의 n = 23인 경우를 살펴보면 크기 1인 부분 배열 2개를 합병하는데는 최대 2번의 비교 연산이 필요하고, 부분 배열의 쌍이 4개이므로 2 x 4 = 8번의 비교 연산이 필요함을 알 수 있다. 마지막 합병 단계인 크기가 4인 부분 배열 2개를 합병하는데는 최대 8번의 비교 연산이 필요하다. 따라서 또한 8 x 1 번의 연산이 필요함을 알 수 있다. 따라서 일반적인 경우를 유추해 보면 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요함을 알 수 있다. 이러한 합병 단계가 k = log2n번 만큼 있으므로 총 비교 연산은 최대 nlog2n번 필요하다.

이동 연산은 얼마나 수행되는 것일까? 하나의 합병 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 하므로 이동 연산은 총 부분 배열에 들어 있는 요소의 개수가 n인 경우, 레코드의 이동이 2n번 발생하므로 하나의 합병 단계에서 2n개가 필요하다. 따라서 log2n 개의 합병 단계가 필요하므로 총 2nlog2n 개의 이동 연산이 필요하다. 결론적으로 합병 정렬은 O(nlog2n)의 복잡도를 가지는 알고리즘이다.

합병 정렬의 특징은 입력 데이터가 어떻게 이루어져 있는지에 상관없이, 즉 최악, 평균, 최선의 경우에도 모두 동일한 시간에 정렬된다는 것이다.

퀵 정렬

퀵 정렬의 개념

퀵 정렬(quick sort)은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 합병 정렬과 같이 분할-정복(divide and conquer)을 사용한다. 그러나 합병 정렬과 달리 리스트를 균등하지 않게 분할한다.

먼저 리스트 안에 있는 한 요소를 피벗(pivot)으로 선택한다. 여기서는 리스트의 첫 번째 요소를 피벗으로 하자. 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮긴다. 결과적으로 피벗을 중심으로 왼쪽은 피벗 보다 작은 요소들로 구성되고 오른쪽은 피벗 보다 큰 요소들로 구성된다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

그러면 퀵 정렬은 어떻게 피벗을 기준으로 나누어진 왼쪽 부분 리스트와 오른쪽 부분 리스트를 정렬할까? 여기에서도 순환 호출이 사용된다. 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정이 되풀이 된다. 이 과정은 부분 리스트를 더 나눌 수 없을 때까지 반복 된다.

quickSort(A, left, right)
    if left < right
        q = partition(A, left, right);
        quickSort(A, left, q-1);
        quickSort(A, q+1, right);

partition 알고리즘

퀵 정렬에서 가장 중요한 함수가 partition()이다. 이 함수는 데이터가 들어 있는 배열 A의 left부터 right까지를, 피벗을 기준으로 2개의 부분 리스트로 나눈다. 피벗보다 작은 데이터는 모두 왼쪽 부분 리스트로, 큰 데이터는 모두 오른쪽 부분 리스트로 옮겨진다.

그림 13.21을 살펴보자. 먼저 간단하게 피벗을 입력 리스트의 첫 번째 데이터로 하자. 따라서 이 경우 피벗은 5가 된다. 인덱스 변수 low는 왼쪽 부분 리스트를 만드는데 사용하고 high는 오른쪽 부분 리스트를 만드는데 사용하자. low는 왼쪽에서 오른쪽으로 탐색해가다가 피벗보다 큰 데이터(8)를 찾으면 멈춘다. high는 오른쪽 끝에서부터 왼쪽으로 탐색해가다가 피벗보다 작은 데이터(2)를 찾으면 멈춘다. 탐색이 멈추어진 위치는 각 부분 리스트에 적합하지 않은 데이터이다. 따라서 low와 high가 가리키는 데이터를 서로 교환한다. 이러한 탐색-교환 과정은 low와 high가 엇갈리지 않는 한 계속 반복한다. 알고리즘이 진행되면서 언젠가는 low와 high가 엇갈려서 지나가게 되면서 멈추게 된다. 이때 high가 가리키는 데이터(1)와 피벗(5)을 교환하게 되면 피벗을 중심으로 왼쪽 리스트에는 피벗보다 작은 데이터만 존재하게 되고, 오른쪽에는 피벗보다 큰 데이터만 남는다. 결국 피벗을 중심으로 2개의 리스트로 나누어지게 된다.

그림 13.21의 마지막 상태에서 피벗(5)은 이미 제 위치에 있음을 알 수 있다. 따라서 피벗을 제외한 왼쪽과 오른쪽 리스트를 독립적으로 다시 퀵정렬하면 전체 리스트가 정렬된다.

퀵 정렬의 복잡도 분석

n이 2의 거듭제곱이라고 가정하고 만약에 퀵 정렬에서의 리스트 분할이 항상 리스트의 가운데에서 이루어진다고 가정하면 합병 정렬의 복잡도 분석과 마찬가지로 n개의 레코드를 가지는 리스트는 n/2, n/4, n/8, … n/2k의 크기로 나누어질 것이다. 크기가 1이 될 때까지 나누어지므로 n/2k = 1일 때까지 나누어질 것이고 따라서 k = log2n 개의 패스가 필요하게 된다. 각각의 패스에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어지므로 퀵 정렬은 비교 연산을 총 nlog2n번 실행하여 O(nlog2n) 알고리즘이 된다. 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

퀵 정렬에서의 최악의 경우는 그림 13.24처럼 리스트가 계속 불균형하게 나누어지는 것이다. 이 경우 레코드의 수만큼 총 n번의 패스가 실행되고, 각 패스에서 n번의 비교가 이루어지게 되므로 비교 연산을 n2번 실행하게 된다. 따라서 최악의 경우 퀵 정렬은 O(n2)의 시간 복잡도를 가지게 된다.

퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는 등 장점이 있는 반면, 정렬된 리스트에 대해서는 오히려 수행 시간이 더 많이 걸리는 단점이 있다. 이러한 불균형 분할을 방지하기 위하여 피벗을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신 보다 리스트의 중앙 부분을 분할할 수 있는 데이터를 선택한다. 많이 사요오디는 방법은 리스트 내의 몇 개의 데이터 중에서 중간값(median)을 피벗으로 선택하는 것이다. 일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개 데이터 중에서 중간 값을 선택하는 방법이 많이 사용된다.

힙 정렬

힙 정렬의 개념

힙은 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료구조이다. 힙에는 최대 힙과 최소 힙이 있는데, 최소 힙의 루트는 가장 작은 값을 가진다. 정리된 배열을 먼저 최소 힙으로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법을 힙 정렬(heap sort)이라 한다.

힙은 완전 이진 트리이므로 1차원 배열을 이용하여 완전하게 기술할 수 있다. 힙은 외관상으로는 그냥 1차원 배열로 보인다.

힙 정렬의 복잡도 분석

요소의 개수가 n일 때 힙의 삽입과 삭제 연산에 각각 log2n에 비례하는 시간이 걸리는 것을 공부했다. 힙 정렬은 n번의 삽입과 n번의 삭제 연산이 필요하므로 결국 2nlog2n에 비례하는 연산이 필요하다. 따라서 힙 정렬의 시간 복잡도는 O(nlog2n)이다.

힙 정렬은 전체 리스트 중에서 일부만 정렬할 필요가 있는 경우에 매우 유용하다.

기수 정렬

기수 정렬의 원리

이전까지의 정렬 방법들은 모두 레코드를 비교하여 정렬하는 반면, 기수 정렬(radix sort)은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬할 수 있는 색다른 정렬 기법이다. 다른 방법들이 O(nlog2n)이라는 정렬의 이론적인 하한선을 꺨 수 없는데 비해 기수 정렬은 이 하한선을 꺨 수 있는 유일한 기법이다. 사실 기수 정렬은 O(kn)의 시간 복잡도를 가지는데 대부분 k < 4 이다. 기수 정렬은 추가적인 메모리를 필요로 하는데, 이런 단점을 감안하더라도 다른 방법들에 비해 빠르기 때문에 인기 있는 정렬 기법이다.

기수(radix)란 숫자의 자릿수이다. 예컨대 숫자 42는 4와 2의 두 개의 자릿수를 가지고 이것이 기수가 된다. 기수 정렬은 이러한 자릿수의 값에 따라 정렬하기 때문에 기수 정렬이라는 이름을 얻었다. 기수 정렬은 다단계 정렬이다. 단계의 수는 데이터의 자릿수의 개수와 일치한다.

기수 정렬의 동작 원리에 대하여 알아보자. 그림 13.25와 같이 한 자리로 이루어진 숫자 리스트가 있다고 할 때 십진수에서는 각 자릿수가 0에서 9까지의 값만 가지는 것에 착안하면 다음과 같이 10개의 버켓(bucket)을 만들어 입력 데이터를 값에 따라 상자에 넣는다. 각 왼쪽 상자부터 순차적으로 버킷 안에 들어 있는 숫자를 읽으면 정렬된 숫자 리스트를 얻을 수 있다. 이 과정에서 비교 연산은 전혀 사용되지 않았다. 각 자릿수의 값에 따라 버킷에 넣고 빼는 동작을 되풀이 했을 뿐이다.

그렇다면 여러 자리로 이루어진 수는 어떻게 정렬해야 하는가? 2자리 수의 리스트라면 100개의 버킷을 사용하면 같은 방법으로 정렬할 수 있지만, 1의 자릿수와 10의 자릿수를 따로 사용하여 정렬하면 효과적이다.

먼저 1의 자릿수 버킷을 사용하고, 그 후에 10의 자릿수 버킷을 이용하면 리스트를 정렬할 수 있다.

기수 정렬의 알고리즘

RadixSort(A, n)
    for d <- LSD의 위치 to MSD의 위치 do
        d번째 자릿수에 따라 0번부터 9번 버킷에 집어 넣는다.
        버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.
        d++;

각각의 버킷에서 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버킷은 큐로 구현되어야 한다. 큐로 구현되어야 리스트 상에 있는 요소들의 상대적인 순서가 유지된다. 버킷에 숫자를 집어 넣는 연산은 큐의 삽입 연산이 되고 버킷에서 숫자를 읽는 연산은 삭제 연산으로 대치하면 된다.

버킷의 개수는 키의 표현 방법과 밀접한 관계가 있다. 만약 키를 2진법으로 사용하여 표현하고 정렬한다면 버킷은 2개만 있으면 된다. 또한 키가 알파벳 문자로 되어 있다면 26개의 버킷이 필요하다. 기수 정렬은 숫자를 10진법으로 생각하면 10개의 버킷을 이용하면 되지만 32비트의 정수를 8비트씩 나누어 적용할 수도 있다. 이 경우 필요한 버킷의 수는 256개가 되지만 대신 필요한 패스의 수는 4개로 줄어든다.

기수 정렬의 분석

만약 입력 리스트가 n개의 정수를 가지고 있다면 알고리즘의 내부 루프는 n번 반복될 것이다. 만약 각 정수가 d개의 자릿수를 가지고 있다고 하면 외부 루프는 d번 반복된다. 따라서 기수 정렬은 O(dn)의 시간 복잡도를 가진다. 시간 복잡도가 d에 비례하기 때문에 기수 정렬의 수행 시간은 정수의 크기와 관련이 있다. 그러나 일반적으로 컴퓨터 안에서의 정수의 크기를 제한된다. 32비트 컴퓨터의 경우에는 대개 10개 정도의 자릿수 만을 가지게 된다. 따라서 일반적으로 d는 n에 비하여 아주 작은 수가 되므로 기수 정렬은 O(n)이라고 하여도 무리가 없다.

기수 정렬은 다른 정렬 방법에 비해 빠른 수행 시간을 갖지만 정렬에 사용되는 키 값이 자연수로 표현되어야만 적용 가능하다. 예컨대 실수나 한글, 한자 등으로 이루어진 키값을 이 방법으로 정렬하고자 할 경우 매우 많은 버킷이 필요하게 되므로 적용이 불가능하다.

정렬 알고리즘의 비교

정렬 알고리즘의 성능 비교

알고리즘 최선 평균 최악
삽입 정렬 O(n) O(n2) O(n2)
선택 정렬 O(n2) O(n2) O(n2)
버블 정렬 O(n2) O(n2) O(n2)
셀 정렬 O(n) O(n1.5) O(n1.5)
퀵 정렬 O(nlog2n) O(nlog2n) O(n2)
힙 정렬 O(nlog2n) O(nlog2n) O(nlog2n)
합병 정렬 O(nlog2n) O(nlog2n) O(nlog2n)
기수 정렬 O(dn) O(dn)  O(dn)

 

정렬 알고리즘별 실험 결과(정수: 60,000개)

알고리즘 실행 시간(단위: sec)
삽입 정렬 7.438
선택 정렬 10.842
버블 정렬 22.894
셀 정렬 0.056
힙 정렬 0.034
합병 정렬 0.026
퀵 정렬 0.014
It's only fair to share...Share on FacebookShare on Google+Tweet about this on TwitterShare on LinkedIn

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기