[자료구조 및 프로그래밍] 14. 정렬 (선택정렬, 삽입정렬, 퀵소트, 머지소트, 기수정렬)

정렬은 큰 사이즈의 작업에 대해 컴퓨터가 자주 수행하는 동작 중 하나다.

이번 글에서는 5가지 정렬 방법에 대해 간단하게 정리하고자 한다.

선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort) 은 말 그대로 정렬 기준에 맞는 값을 선택해서 정렬하는 알고리즘이다.

선택 정렬은 In-Place 방식으로, O(n^2) 시간에 수행된다.

 

알고리즘은 다음과 같다.

 

1. 정렬된 결과의 0번째 원소를 결정하려고 한다.

2. 0번째원소를 1번째 원소부터 N-1번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap 한다.

3. 이번엔 1번째 원소를 결정하려고 한다.

4. 1번째 원소를 2번째 원소부터 N-1 번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap 한다.

5. i 번째 원소를 결정하려고 한다.

6. i 번째 원소를 i+1번째 원소부터 N-1 번째 원소까지 하나하나 비교해보면서 그 중 제일 작은 원소와 swap한다.

7. i < N 에 대해 반복한다.

 

N 개 사이즈의 배열에 대해 이 알고리즘을 수행하면, 비교횟수는 아래와 같다.

 

0번째 원소 결정에 N-1번 비교

1번째 원소 결정에 N-2번 비교

i 번째 원소 결정에 N-(i+1) 번 비교

(i = N-1까지 반복)

 

따라서 총 비교횟수는 1부터 N-1까지의 합인 N(N-1) / 2 이고, 이 알고리즘의 수행 시간은 O(N^2) 이다.

또한, 이 알고리즘에서 swap이 일어나는 횟수는 최대 N-1 번이므로 스왑에는 O(N) 에 시간이 소요된다.

 

결과적으로 O(N^2) + O(N)  = O(N^2) 이다.

선택 정렬의 수도코드는 아래와 같다.

selection_sort(arr[0..n-1]) {
    min, k
    for (j <- 0; j < n; j++) {
        min <- arr[j];
        k <- j;
        for (i <- j+1; i < n; i++) {
            if (arr[i] < min) {
                min <- arr[i];
                k <- [i];
            }
        }
        
        swap(arr[j], arr[k]);
    }
}

---

삽입 정렬 (Insertion Sort)

삽입 정렬은 선택 정렬과 마찬가지로 In-Place 정렬이다.

삽입 정렬은 이름 그대로, 어떤 원소를 정렬된 배열에 '삽입' 해서 정렬하는 방식이다.

 

삽입 정렬의 알고리즘은 다음과 같다.

i 번째 원소를 볼때는, i-1 번째 원소까지는 이미 정렬된 상태임이 보장되어 있고, i 번째 원소부터는 정렬되어 있는 상태가 보장되어 있지 않은 상태라고 정의한다.

i 번째 원소부터 하나씩 이전 인덱스를 보면서, 이미 정렬된 배열 [0..i-1] 의 어떤 위치에 i 번째 원소가 들어가야 되는지 찾는다.

이는 직전 원소와 비교해서 자신이 더 작으면 직전원소와 자기 자신을 교환하는 방식으로 진행할 수 있다.

 

예를 들어 아래와 같은 배열이 있다고 해보자.

 

3 9 1 6 5 2 7

 

먼저 0번째 인덱스는 왼쪽에 탐색할 원소가 없으니 건너간다.

0번째 인덱스까지는 정렬되어 있다.

 

다음으로 1번째 인덱스를 본다. 왼쪽 원소와 비교해보니 자신이 더 크다.

따라서 제대로 된 위치에 있으니 건넉나다.

이제 1번째 인덱스까지는 정렬되어 있다.

 

2번째 인덱스를 본다.

왼쪽 원소와 비교해보니 자신이 더 작다.

따라서 왼쪽 원소와 자신의 위치를 바꾼다.

 

3 1 9 6 5 2 7

 

다시 왼쪽 원소와 비교해보니 이번에도 자신이 더 작다.

다라서 왼쪽 원소와 자신의 위치를 바꾼다.

 

1 3 9 6 5 2 7

 

더 이상 왼쪽으로 갈 수 없으니 자신의 위치를 찾았다.

이제 2번째 인덱스까지는 정렬되어 있다.

 

....

 

이 과정을 모든 인덱스에 대해 반복하면 된다.

이 정렬 알고리즘은 선택정렬보다 비교 횟수 측면에서 더 개선된 알고리즘이다.

 

최적의 경우로 이미 정렬된 배열이 주어지면, 선택 정렬은 그럼에도 불구하고 모든 원소와 다 비교하며 최솟값을 찾기 때문에 여전히 N(N-1)/2 번의 비교를 거친다.

그러나 삽입 정렬의 경우, 이 경우 자신의 왼쪽 원소와 비교하는 과정을 N-1 번만 거치면 되며,  O(N)

정렬이 역순으로 된 채로 주어지는 최악의 경우가 되어야 N(N-1)/2 번의 비교가 일어나게 된다. O(N^2)

 

그러나 선택 정렬과 비교하여 한가지 안 좋은 부분도 있다.

선택정렬은 최솟값을 탐색해서 찾으면 그 원소와 직접 바로 교환을 하면 되므로, 최대 N-1 번의 교환이 일어나게 되었다.

하지만 삽입 정렬은 자신의 왼쪽에 작은 값이 위치할 때까지, 계속해서 교환을 시도하므로, 최악의 경우 N(N-1)/2 번의 교환을 해야한다. O(N^2)

---

여기까지 O(N^2) 의 시간복잡도를 갖는 정렬 방법 2가지를 알아보았다.

이 외에도 버블 소트와 같은 다른 O(N^2) 알고리즘이 더 존재한다.

 

그러나 Heap 에서 정리했던대로, Heap 에 데이터를 N번 넣고, N 번 빼는 행위를 통해 정렬을 O(N log N) 에 할 수 있음을 이미 알고 있다

이를 Heap Sort 라고 하는데 또 다른 N log N 시간 정렬 방법은 더 없을까?

다음으로 또 다른 N log N 시간 정렬 방법인 병합 정렬에 대해 정리해보고자 한다.

---

병합 정렬 (Merge Sort)

병합 정렬은 분할 정복을 이용해 정렬을 수행한다.

 

1. 최초 함수는 정렬할 사이즈 N 의 배열을 받는다.

2. 받은 배열을 반씩 쪼개어 N/2 씩 정렬하라고 서브 함수에 넘긴다.

3. 서브 함수는 다시 받은 배열을 반씩 쪼개서 N/4 씩 정렬하라고 또 서브함수에 넘긴다.

4. 이 과정을 반복하다가 받은 배열의 사이즈가 1이 되면 더 이상 쪼갤 수 없으므로 그냥 부모 함수에게 해당 배열을 돌려준다.

5. 부모함수는 2명의 자식에게 나눠주었던 배열을 받아 새롭게 정렬한다.

각 자식에게 돌려받은 반쪽짜리 배열 2개는 각각 모두 정렬되어 있다.

따라서 각 배열의 앞쪽부터 차례대로 살펴보며 하나의 정렬된 배열을 만든다.

6. 이 과정을 모든 부모 함수가 반복하면 된다.

 

그림과 같이 주어진 배열을 먼저 반씩 쪼개는 과정을 반복한다.

사이즈가 1이 되면 그때는 쪼개지 않고 부모에게 돌려준다.

부모는 돌려받은 배열의 인덱스를 비교하면서 재정렬한다.

 

이 알고리즘을 수도 코드로 나타내면 아래와 같다.

mergesort(arr[l..r]) {
  if (l < r) {
    mid = (l + r) / 2
  
    mergesort(arr[l .. mid])
    mergesort(arr[mid+1 .. r]
  }
  
  merge(arr[l .. mid], arr[mid+1 .. r])
}

 

일단 반씩 쪼개서 재귀적으로 함수를 호출하고, 반으로 나눌 수 없으면 그때는 그냥 반환한다.

반씩 쪼개서 나눠줬던 배열은 정렬된 채 돌아오고, 그 배열 둘을 merge 해서 다시 부모 함수에게 돌려주는 과정을 반복하면 된다. merge 함수는 두 정렬된 배열을 합치는 연산으로, 이 곳에서 키값을 비교하기 때문에 실질적으로 정렬이 일어나는 부분이기도 하다.

 

merge 부분의 수도 코드는 아래와 같다.

merge(a[l .. m .. r]) {
    copy a[l..r] into c[l..r]
    i <- l
    j <- m+1
    k <- l
    while (i <= m and j <= r) {
        if (c[i] <= c[j])
            a[k++] <- c[i++]
        else
            a[k++] <- c[j++]
    }
    
    if ( i > m )
        while( j <= r )
            a[k++] <- c[j++]
    else
        while ( i <= m )
            a[k++] <- c[i++]
}

 

merge 연산은 in-place 에서 할 수 없고, 새로운 임시 배열 공간이 필요하다.

우선 반씩 정렬된 두 배열을 합쳐 임시 배열에 넣어두고, 기존배열을 l 부터 r 까지 다시 채워나간다.

이때, B 에 있는 이미 정렬된 두 배열의 인덱스를 앞에서부터 하나씩 비교해서 작은 쪽을 채워넣고, 채워준쪽만 인덱스를 증가하는 식으로 운영하다, 먼저 다 채워진 쪽을 빼고 나머지를 그대로 다시 기존배열에 넣어주면 된다.

 

정렬된 두 배열의 사이즈가 각각 m, n 일 때, 비교횟수의 최소값은 min(m, n) 이다.

1 2 3 으로 정렬된 배열과, 4 5 6 7 으로 정렬된 배열에서 merge 가 실행되면, 1은 4와 비교해서 끝나고, 2는 4와 비교해서 끝나고, 3도 4와 비교해서 끝나므로 비교는 더 이상 일어나지 않고, 반복문을 돌면서 4 5 6 7 을 쭉 넣을 것이다.

따라서 비교는 min(m, n) = 3 번만 일어난다.

 

그러나 서로 엇갈려 있다면 어떨까

2 4 6 / 1 3 5 7

 

처음에는 2 1 을 비교해서 1을 넣고

2 3 을 비교해서 2를 넣고

4 3 을 비교해서 3 을 넣고

4 5 를 비교해서 4를 넣고

5 6 을 비교해서 5를 넣고,

6 7 을 비교해서 6을 넣고,

더이상 비교할 수 있는 게 없으니 나머지는 반복문을 쭉 돌린다.

 

총 7개의 데이터가 이렇게 얼기설기 있으면 최악의 경우 m + n - 1 = 6번의 비교를 하게 된다.

그래서 한번 merge 하는데 필요한 비교 시간복잡도는 O(m+n) 이다.

 

그리고 m, n 사이즈 배열의 값을 m+n 사이즈 배열에 복사해서 새로운 배열을 만들어야 하므로, 데이터를 옮기는 데 걸리는 시간복잡도는 O(m + n) 이다.

배열 대신 연결 리스트를 사용하는 경우

merge를 구현할 때, 배열대신 연결 리스트를 이용하여 구현할 수도 있다.

연결리스트를 이용하더라도 비교는 똑같이 최적의 경우, min(m, n) 만큼, 최악의 경우 m+n -1 만큼 하게 된다.

그러나 새 정렬된 연결 리스트를 만드는 과정이 min(m ,n) 시간에 일어날 수 있다.

 

한번 최악의 경우를 보자.

2 4 6 / 1 3 5 7 로 정렬된 연결 리스트가 있다.

 

처음에 1과 2를 비교한다.

2가 1보다 크니, 2를 1의 다음 노드로 연결한다.

 

4 6 / 1 2 3 5 7 이 된다.

2를 집어넣으면서 자연스럽게 2의 Link 를 3으로 설정하였을테니 이제 3으로 넘어간다.

3과 4를 비교하면 4가 더 크니까 4를 3의 오른쪽에 넣어준다.

 

6 / 1 2 3 4 5 7 이된다.

4를 넣으면서 자연스럽게 4의 link 를 5로 설정하였을테니 5의 주소로 넘어간다.

5와 6을 비교하면 5보다 6이 크니 6을 5의 Link 로 넣어준다.

/ 1 2 3 4 5 6 7 이 된다.

 

이렇게 min (n, m) 시간에 새로운 정렬된 연결 리스트를 만들 수 있다.

각 비교를 하여 데이터를 집어 넣는 과정에서 이미 정렬된 나머지들의 순서관계가 같이 유지되기 때문에 아주 아주 빠르게 될 수 있는 것이다.

 

게다가 연결 리스트를 이용하면 버퍼 (중간 데이터를 저장하기 위한 여분 메모리 공간) 도 필요하지 않다.

 

그러나 이상적으로 보이는 이론과는 달리 연결 리스트를 이용한 merge sort는 구현할 때 재귀를 사용하므로 더 많은 작업이 필요하다는 문제도 있다.

(mergesort 자체도 이미 재귀인데, 그 안에서 merge 할 때 재귀를 추가적으로 사용해야한다.)

병합 정렬의 재귀 횟수

N 개의 데이터를 병합정렬로 정렬한다면 총 몇번의 재귀함수를 호출하게 될까?

바로 정확하게 2N - 1 번 호출한다.

 

이는 재귀 트리 (The Recursion Tree) 가 Extended Binary Tree 이기 때문인데, Extended Binary Tree 는 노드가 N-1개 이면, 그 leaf node (null node) 가 N 개이므로 N + N-1 = 2N - 1 개의 노드를 가진다.

재귀 트리로 보면 leaf node 는 자식 함수를 더 이상 호출하지 않는 말단 함수로 보면 된다. (즉, 비어있는 이진 트리이다. 이진트리는 빈 노드를 허용한다!)

 

먼저 일반화하기 전에 위에서 들었던 7개 원소 정렬을 예시로 보자.

 

위 그림에서 주황색으로 표시한 노드는 internal node 이고, 노란색으로 표시한 노드가 leaf node 이다.

더이상 재귀를 호출하지 않을 때까지 부르는 마지막 함수는 원소의 갯수인 N 번 호출될 것이다.

그리고 그 n번의 함수가 호출되기 위해 어떤 과정을 거쳤을지 따라 올라가도록 트리를 그리면 이렇게 extended binary tree가 그려질 수 밖에 없다.

 

따라서 merge sort 과정에서 호출되는 merge_sort() 함수의 호출 횟수는 정확하게 2N - 1 이다.

그리고 이를 일반화 하면 아래와 같이 나타낼 수 있게 되는데, 이를 통해 merge sort 의 시간 복잡도도 계산할 수 있다.

이렇게 N 개의 노드를 계속 반씩 분할하면서 정렬하게 되면 위와 같은 방식이 된다.

이때 결국 N/2^k = 1 이 될 때까지 계속 반으로 나누게 되는데, 그때까지 나눈 과정을 모두 tree 로 나타내면 tree 의 높이는 Log(N) 이 된다.

 

그리고 재귀를 통한 분할이 끝난 뒤, 각 level 에서 merge를 통해 정렬하는 데이터의 개수는 항상 N 개이다.

이 과정은 역시 Log(N) 만큼 반복된다.

 

따라서 N 개의 데이터를 정렬하는 level 이 Log(N)번 반복되므로 정렬에는 총 O(N log N) 의 시간이 걸리게 된다.

---

퀵 소트

퀵 소트는 정렬 알고리즘 중 가장 흔하게 사용되는 알고리즘인데 그 이유가 뭘까?

퀵 소트는 최악의 경우 O(N^2) 의 시간복잡도를 가지고, 주로 O(N log N) 의 시간 복잡도를 가진다.

그럼에도 이름에 나와있듯 대부분의 다른 정렬 알고리즘보다 빠르다.

 

머지소트와 같이 정렬할 파트를 겹치는 부분이나 버리는 부분없이 나눈 뒤, 작게 나눠진 조각을 처리해 다시 합쳐서 원래의 문제를 해결하는 알고리즘을 '분할정복' 알고리즘이라고 한다.

 

퀵 소트도 머지소트와 같은 분할정복 알고리즘을 사용하며, 아래와 같은 방식으로 작동한다.

quicksort(A(l..r)) {
    if (l < r) {
        p <- partition(A(l..r))
        quicksort(A(l..p-1))
        quicksort(A(p+1..r))
    }
}

 

머지소트와 달리 정확히 절반은 아니지만, 일단 어떤 p 값을 기준으로 배열을 쪼개서 정렬을 수행하고 있다.

이 p 는 pivot 이라고 부르는 값으로, 배열을 몇개로 나누었는지 정보를 제공해준다.

 

머지 소트에서 merge 함수가 실질적으로 정렬을 수행했던 것처럼, 퀵소트에서는 저 partition 함수가 정렬을 실질적으로 수행하는 중요한 코드다.

partition 함수는 list 내의 원소에 random access를 할 수 있어야 해서, 머지소트와 달리 퀵소트는 연결리스트로 구현하기에 적합하지 않다. 하지만 random access 를 비용으로 사용하였기에 in-place 로 정렬이 가능하다는 장점도 있다.

과연 partition 함수는 어떻게 구현할 수 있는지 살펴보자.

partition(A(l, r)) {
    x = A(l) // pivot
    i <- l+1, j <- r
    
    while (1) {
        while (A(i) <= x) i++
        while (A(j) > x ) j--
        if (i < j) swap(A(i), A(j))
        else break
    }
    swap(A(l), A(j))
    return j
}

 

코드만 보면 이게 무슨 일을 하는지 이해하기 어려우니 그림으로 작동 과정을 이해해보자.

한번 3 9 1 6 5 2 7 이 들어있는 배열을 정렬한다고 해보자.

 

처음에는 이렇게 값이 세팅되어 있다.

 

먼저 i 부터 시작해서 비교하려는 값인 x( = 3)와 arr[i] 를 비교하면서 x (= 3) 이하라면 i를 쭉쭉 증가시킨다.

이 과정을 통해 i 가 가리키는 위치의 왼쪽에는 모두 x 보다 작은 값이 위치하게 된다.

 

당므으로 j 부터시작하여 비교하려는 값인 x 와 arr[j] 를 비교하면서, x (= 3) 초과라면, j 를 쭉쭉 감소시킨다.

이 과정을 통해 j 가 가리키는 위치의 오른쪽에는 모두 x 보다 큰 값이 위치하게 된다.

 

중요한점은 i, j 가 가리키고 있는 '그 위치' 는 포함이 안된다는 점을 기억하자.

 

그럼 i, j 는 위 그림처럼 바뀐다.

이렇게 i, j 의 위치를 x 의 기준에 맞게 설정한 뒤, 만약 i < j 라면 i 와 j 의 값을 서로 swap 한다.

i = 1, j = 5 이므로 swap을 진행한다.

아까와 달리 x (= 3)을 기준으로 작은 값이 왼쪽에 있고, 큰 값이 오른쪽에 위치하기 시작한 것이 보인다.

위 과정을 i < j 가 아닐 때까지 반복한다.

그러면 다음에는 이 상태에서 멈춘다.

이제 i, j 가 역전되었는데, i, j 가 역전되어있다는 뜻은 x (= 3)을 기준으로 작은 값은 모두 왼쪽에 있고, 큰 값은 모두 오른쪽에 있다는 의미로 볼 수 있다.

 

이제 이 상황이라면 x (=3)의 위치가 정렬이 된 배열에서 어디에 위치해야 하는지 정확하게 알 수 있다.

바로 j 가 가리키고 있는 곳에 x 의 값이 들어가고, 기존 x 가 가리키는 곳에 j 가 들어가면된다.

이 둘을 swap 해준다.

이제 3을 기준으로 왼쪽에는 작은값, 오른쪽에는 큰 값이 들어있음이 보장되었고, x (= 3)의 위치도 정확하게 특정하였다.

partition 함수는 위치가 정확하게 특정된 x 의 위치인 j 를 반환하는 것으로 역할을 끝낸다.

---

이것으로 quicksort 알고리즘도 간단하게 정리하였다.

 

퀵소트의 시간복잡도는 partition 함수에서 얼마나 시간이 걸리는지, 그리고 partiion 함수가 얼마나 많이 호출되는지에 달려있다.

 

우선 partition 함수는 중복되지 않은 N개의 데이터가 들어있는 배열에 대해 항상 N-1 번의 비교를 수행한다.

N 개의 데이터 중 제일 왼쪽의 데이터 하나를 기준으로, 다른 값들이 왼쪽, 오른쪽에 나눠져 위치하도록 하려면 모든 데이터를 한번씩은 탐색해야 하기 때문이다.

 

그러나 swap 이 발생하는 횟수는 0번 ~ 최악의 경우 (N-1)/2 번까지 발생할 수 있다.

왼쪽에는 모두 x 보다 큰 데이터가 들어있고, 오른쪽에는 모두 x 보다 작은 데이터가 들어있는 경우가 그렇다.

위 예제로 따지면 3, 9, 7, 6, 5, 2, 1 와 같은 상황이 그렇다.

9, 1 을 비교해서 swap, 7, 2 를 비교해서 swap 할 수 있다.

만약 처음 잡은 피벗이 배열 값을 정렬했을 때 정확히 중간 값이고, 피벗을 제외한 나머지 데이터가 역순 정렬되어있다면 최대 (N-1) / 2 번의 교환이 일어날 수도 있다.

 

결론적으로 비교횟수와 데이터 읽고 쓰는 시간을 고려하면 partition 함수에서는 O(n) 의 시간이 소요된다.

 

partition 함수의 호출은 몇 번이나 일어날까?

최적의 경우엔 partition 함수의 실행 결과로 pivot 이 중간 값으로 설정되는 것이 반복되어 Log(N) 번 호출 될 수도 있으나,

최악의 경우엔 partition 함수의 실행 결과로 pivot 이 계속 양끝단 값중 하나로 나와서 N 번 호출 될 수도 있다.

 

따라서 퀵소트의 시간복잡도는 최적일 때 O(N log N) 이고, 최악일 땐 (N^2) 이다.

 

merge sort가 최악의 경우에도 O( n log n ) 시간이 걸리는 것과 비교했을 때,

quick sort 는 최악의 경우 O( n ^ 2) 의 시간이 걸리는데, 왜 merge sort 보다 일반적으로 빠르다고 하는걸까?

 

그 이유는 비교횟수가 아니라 데이터를 읽고 쓰는 횟수에 있다.

mergsort 는 그 과정에서 배열에 값을 복사해서 옮겨 넣는 과정을 언제나 거쳐야 한다.

그러나 quick sort 는 partition 함수에서 값을 서로 swap 할 때만 읽고 쓰기를 거치며, 최악의 경우가 아니라면 모든 값을 읽고 쓰기 하지 않는다.

---

기수 정렬 (Radix Sort)

마지막으로 기수 정렬에 대해 정리해보고자 한다.

기수정렬은 bucket sort, counting sort, distribution sort 과 비슷한 '키값 비교' 기반 정렬이 아닌 정렬 방식이다.

 

한번 아래와 같이 3자리 숫자로 이루어진 수열이 있다고 해보자.

 

먼저 각 자리의 수를 위한 bucket을 설정하고, 맨 마지막 숫자를 기준으로 bucket 에 숫자를 넣는다.

 

그러면 순서대로 왼쪽부터 보았을 때 이렇게 값을 담을 수 있다.

 

다음으로 기존 bucket에 잇는 값을 bucket을 따라서, 그리고 한 bucket 안에서는 위에서 아래로 순회하며

두번째 자리수를 기준으로 버킷에 다시 채워넣는다.

 

230은 3이니까 3에 채워넣고, 571은 7이니까 7에 넣고, 501은 0 이니까 0에 넣고... 이 순서로 순회한다.

이 결과에서 눈치를 챌 수도 있지만, 자세히보면 현재 한 bucket 안에서 1의 자리 수에 대해 정렬이 완료되어 있음을 알 수 있다.

그 이유는 두번째로 데이터를 넣을 때 기존의 0번째 버킷부터 시작해서 데이터를 담았기 때문에, 1의자리 수가 작은 값이 버킷에 먼저 담기기 때문이다.

 

이제 이 결과에서 한번더 첫번째 자릿수 (100의 자리) 를 보고 다시 한번 더 순회하며 버킷에 값을 담는다.

그 결과 위와 같이 데이터가 담기게 되며, 100의 자리 숫자는 같은 상태에서 10의 자리, 1의 자리 숫자는 위에서 아래로 볼 때 정렬이 되어있음을 알 수 있다.

 

이 알고리즘은 동일한 M 자리 숫자 N 개에 대해 정렬을 수행하는데 O(N*M) 의 시간이 걸린다는 것을 알 수 있다.

그런데 M 의 값은 이미 정해진 상수이고, 변할 수 있는 값은 데이터의 개수인 N 이므로, 사실상 O(N) 시간에 정렬을 수행할 수 있다.

 

이 알고리즘은 10진수가 아닌 문자열에 대해서도 사용이 가능하다.

보통 '정렬은 O(N log N) 시간이 걸린다' 라고 하는 내용도 이걸 보면 해당 사항이 없는 것 같지만, 이에 대해서는 다음에 더 자세하게 정리해보고 이번 글에서는 Radix Sort 의 방법에 대해서만 정리하였다.

---

이것으로 5가지 종류의 정렬 알고리즘을 정리하였다.

다음 글에서는 각 정렬 알고리즘을 실제 코드로 구현해보고, 각 정렬 알고리즘 별, 비교횟수와 데이터 읽고쓰기 횟수를 카운팅할 것이다.

그리고 각 정렬 알고리즘 별 카운팅 횟수를 비교하며 왜 퀵소트가 머지소트보다 일반적으로 빠른지 숫자로 확인해볼 것이다.