정렬 알고리즘 (sorting algorithm) 정리

순차탐색(sequential search)

- 시간복잡도 : O(n)

- 데이터가 정렬되어 있지 않아도 사용할 수 있다.

이진탐색(binary search)

- 시간복잡도 : O(logn)

- 데이터가 순서에 맞게 정렬되어 있어야 한다.

알고리즘	Best	Average	Worst	Stable	Memory
버블 정렬	(n^2)	(n^2)	(n^2)	True
선택 정렬	(n^2)	(n^2)	(n^2)	False
삽입 정렬	(n)	(n^2)	(n^2)	True
셸 정렬	(nlog_2n)	(n^{1.5})	(n^2\)	False
퀵 정렬	(nlog_2n)	(nlog_2n)	(n^2\)	False
히프 정렬	(nlog_2n)	(nlog_2n)	(nlog_2n)	False
합병정렬	(nlog_2n)	(nlog_2n)	(nlog_2n)	True	(n)
퀵 정렬	(nlog_2n)	(n^2)	(n^2)	True / False	X / (n)

---

Bubble Sort (버블 정렬)

 이웃한 두 값을 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 이러한 리스트의 비교-교환 과정(스캔)이 한 번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 이러한 레코드의 이동 과정이 마치 물속에서 거품이 보글보글 떠오르는 것과 유사하여 버블정렬이라 부른다. 

def bubbleSort(x):
    # 맨 뒤에서부터 정렬할 범위를 좁혀나감.
    for passnum in range(len(x)-1, 0,-1):        
        for i in range(passnum):
            # 앞 뒤 레코드 비교 후 교체.
            if x[i] > x[i+1] :
                x[i], x[i+1] = x[i+1], x[i]

복잡도 분석

1. 비교 횟수

- 최상, 평균, 최악의 어떠한 경우에도 항상 일정하고 다음과 같다.

$$ \sum_{i=1}^{n-1} i = {n(n-1)\ \over 2} = O(n^2) $$

2. 이동 횟수

- 최악의 이동 횟수는 입력 자료가 역순으로 정렬되어 있는 경우에 발생하고 그 횟수는 비교 연산의 횟수에 3을 곱한 값이다. 왜냐하면 하나의 SWAP 함수가 3개의 이동을 포함하고 있기 때문이다.

- 최상의 경우는 입력 자료가 이미 정렬이 되어 있는 경우이다.  이런 경우는 당연하게도 자료 이동이 한번도 발생하지 않는다.

- 평균적인 경우에는 자료 이동이 0번에서 i번까지 같은 확률로 일어날 것이다.

따라서 이를 기반으로 계산하여 보면 \(O(n^2)\) 의 알고리즘임을 알 수 있다.

문제점

- 순서에 맞지 않은 요소를 인접한 요소와 교환한다는 것. 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다. 특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.

 일반적으로 자료의 교환(swap) 작업이 자료의 이동(move) 작업보다 더 복잡하기 때문에 버블 정렬은 그 단순성에도 불구하고 거의 쓰이지 않고 있다.

---

Selection Sort (선택 정렬)

 주어진 배열에서 최솟값을 발견한 다음, 이 값을 배열의 첫 번째 요소와 교환한다. 다음에는 첫 번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두 번째 요소와 교환한다. 이 절차를 (숫자 개수-1)만큼 되풀이하면 된다.

def selectionSort(x) :
    for size in range(len(x)-1, 0, -1) :
        _max = 0
        for i in range(1, 1+size):
            if x[i] > x[_max] :
                _max = i        
        if i != _max : # 불필요한 교환을 막기 위함.
            x[i], x[_max] = x[_max], x[i]

복잡도 분석

1. 비교 횟수

- 외부 루프는 n-1번 실행될 것이며 내부 루프는 (n-1)-i번 반복될 것이다.

- 따라서 키 값들의 비교가 내부 루프 안에서 이루어지므로 전체 비교 횟수는 다음과 같이 된다.

$$ \sum_{i=1}^{n-1} i = {n(n-1)\ \over 2} = O(n^2) $$

2. 교환 횟수

- 외부 루프의 실행 횟수와 같으며 한 번 교환하기 위하여 3번의 이동이 필요하므로 전체 이동횟수는 \(3(n-1)\)이 된다.

- 일반적으로 비교 연산 1개가 이동 연산 3개보다 시간이 적게 걸리므로 같은 원소인 경우를 체크 하는 것이 효과적이다.

 선택 정렬은 안정성을 만족하지 않는다. 즉, 값이 같은 레코드가 있는 경우에 상대적인 위치가 변경될 수 있다.

---

Insertion Sort (삽입 정렬)

 손 안의 카드를 정렬하는 방법과 유사하다. 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 한다.

def insertionSort(x) :
    for size in range(1, len(x)) :
        val = x[size]
        i = size
        while i > 0 and x[i-1] > val :
            x[i] = x[i-1]
            i -= 1
        x[i] = val

복잡도 분석

1. 최선

- 이미 정렬 되어 있는 경우 가장 빠르다. 이 경우 삽입 정렬의 외부 루프는 n-1번 실행되고 각 단계에서 이동없이 1번의 비교만 이루어지므로 총 비교 횟수는 n-1번이 되어 알고리즘의 시간 복잡도는 \(O(n)\) 이다.

2. 최악

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

$$ \sum_{i=1}^{n-1} i = {n(n-1)\ \over 2} = O(n^2) $$

 삽입 정렬은 비교적 많은 레코드들의 이동을 포함한다. 결과적으로 레코드 수가 많고 레코드 크기가 클 경우에 적합하지 않음을 알 수 있다. 반면에 안정한 정렬 방법으로서 레코드의 수가 적을 경우 알고리즘 자체가 매우 간단하므로 다른 복잡한 정렬 방법보다 유리할 수 있다. 또한 삽입 정렬은 대부분의 레코드가 이미 정렬되어 있는 경우에 매우 효율적일 수 있다.

---

Shell Sort (셸 정렬)

 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법이다. 셸 정렬은 삽입 정렬보다 빠르다.

 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동한다는 것이다. 만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야만 제자리로 갈 수 있다. 셸 정렬에서는 요소들이 멀리 떨어진 위치로도 이동할 수 있다.

 삽입 정렬과는 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않는다. 대신에 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이한다. (부분 리스트의 개수가 1이 될 때까지 되풀이된다.)

 부분 리스트를 구성할 때는 주어진 리스트의 각 k번째 요소를 추출하여 만든다. 이 k를 간격(gap)이라고 한다. 셸 정렬에서는 각 스텝마다 간격 k를 줄여가므로 수행 과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다. 마지막 스텝에서는 간격의 값이 1이 된다. 처음 간격은 n/2로 하고 각 패스마다 간격을 절반으로 줄이는 방식을 사용한다.

def gapInsertionSort(x, start, gap):
    for target in range(start+gap, len(x), gap):
        val = x[target]
        i = target
        while i > start and x[i-gap] > val :            
            x[i] = x[i-gap]            
            i -= gap
        x[i] = val
 
def shellSort(x):
    gap = len(x) // 2
    while gap > 0 :
        for start in range(gap) :
            gapInsertionSort(x, start, gap)
        gap = gap // 2

분석

 삽입 정렬에 비하여 셸 정렬은 2가지의 장점이 있다.

- 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동한다. 따라서 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.

- 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되게 되면 셸 정렬은 기본적으로 삽입 정렬을 수행하는 것이지만 더욱 빠르게 수행된다. 삽입 정렬이 거의 정렬된 파일에 대해서는 빠르게 수행되기 때문이다.

최악의 경우에는 \(O(n^2)\) 이지만 평균적인 경우에는 \(O(n^{1.5})\)로 나타난다.

 비효율적이지만 간단한 정렬 방법들은 입력 데이터가 많지 않을 때는 충분한 방법이다. 그러나 입력 데이터가 많으면서 자주 정렬해야 할 필요가 있으면 이들 방법은 충분하지 못하다.

---

Merge Sort (합병 정렬)

 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 분할 정복(divide and conquer)방법에 바탕을 두고 있다. 

합병 정렬의 단계

1. 분할(Divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.

2. 정복(Conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

3. 결합(Combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

def mergeSort(x):
 
    if len(x) > 1 :
 
        mid = len(x) // 2
 
        left, right = x[:mid], x[mid:]
 
        mergeSort(left)
        mergeSort(right)
 
        li, ri, ti = 0, 0, 0
 
        while li < len(left) and ri < len(right) :
 
            if left[li] < right[ri] :
                x[ti] = left[li]
                li += 1
            else :
                x[ti] = right[ri]
                ri += 1
 
            ti += 1
        
        x[ti:] = left[li:] if li != len(left) else right[ri:]

복잡도 분석

- 합병 정렬은 순환 호출 구조로 되어있다. 따라서 레코드의 개수 n이 \(2^k\) 라고 하면 순환 호출의 깊이 k는 \(log_2n\)이다.

- 배열이 부분 배열로 나누어지는 단계에서는 비교 연산이나 이동 연산은 수행되지 않는다.

- 부분 배열이 합쳐지는 부분에서 비교 연산 & 이동 연산이 수행된다.

1. 비교 연산

- 일반적인 경우를 유추해보면 하나의 합병 단계에서는 최대 n번의 비교 연산이 필요함을 알 수 있다. 그러한 합병 단계가 \(k=log_2n\)번만큼 있으므로 총 비교 연산은 최대 \(nlog_2n\)번 필요하다.

2. 이동 연산

- 하나의 합병 단계에서 보면 임시 배열에 복사했다가 다시 가져와야 하므로 이동 연산은 \(2n\)번이 발생한다. 총 \(log_2n\)개의 합병 단계가 필요하므로 총 \(2nlog_2n\)개의 이동 연산이 필요하다.

- 결론적으로 합병정렬은 비교 연산과 이동 연산의 경우 \(O(nlog_2n)\)의 복잡도를 가지는 알고리즘이다.

- 안정적인 정렬 방법으로 데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. 최악, 평균, 최선의 경우가 다 같이 \(O(nlog_2n)\)인 정렬 방법이다.

- 단점은 임시 배열이 필요하다는 것과 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래한다는 것이다. 그러나 만약 레코드를 연결 리스트로 구성하여 합병 정렬할 경우, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다. 따라서, 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 정렬 방법보다 효율적일 수 있다.

---

Quick sort (퀵 정렬)

 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법이다. 퀵 정렬도 분할 정복(divide and conquer) 방법에 근거한다. 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 전형적인 분할 정복 방법을 사용한다.

 합병 정렬과는 달리 퀵 정렬은 리스트를 다음과 같은 방법에 의해 비균등하게 분할한다. 리스트 안에 있는 한 요소를 pivot으로 선택한다. pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮겨진다. 이 상태에서 pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

def partition(x, left, right) :       val = x[left]     i = left # pivot index. 변경 가능.       while left <= right:           while left <= right and x[left] <= val:             left += 1           while left <= right and x[right] >= val:             right -= 1           if left <= right :             x[left], x[right] = x[right], x[left]             left += 1             right -= 1          x[i], x[right] = x[right], x[i]       return right   def quickSort(x) :       def _qsort(x, first, last) :          if first < last :             pivot = partition(x, first, last)             _qsort(x, first, pivot-1)             _qsort(x, pivot+1, last)          _qsort(x, 0, len(x)-1)

cs

복잡도 분석

- 크기가 1이 될 때까지 나누어지므로 \(n/{2^k}=1\)일 때까지 나누어질 것이고, \(k=log_2n\)개의 패스가 필요하게 된다.

- 각각의 패스에서는 전체 리스트의 대부분의 레코드를 비교해야 하므로 평균 n번 정도의 비교가 이루어지므로 퀵 정렬은 비교 연산을 총 \(nlog_2n\)번 실행하게 되어 \(O(nlog_2n)\)의 복잡도를 가지는 알고리즘이 된다. 여기서 레코드의 이동 횟수는 비교 횟수보다 적으므로 무시할 수 있다.

- 퀵 정렬에서의 최악의 경우는 리스트가 계속 불균형하게 나누어지는 경우이다.

(1 2 3 4 5 6 7 8)

1 (2 3 4 5 6 7 8)

1 2 (3 4 5 6 7 8)

...

1 2 3 4 5 6 7 8

 이 경우 레코드의 수만큼 총 n번의 패스가 실행되고, 각 패스에서 n번의 비교가 이루어지게 되므로 비교 연산을 \(n^2\)번 실행하게 된다. 즉, 퀵 정렬은 최악의 경우 \(O(n^2)\)의 시간 복잡도를 가지게 된다.

 그럼에도 불구하고 퀵 정렬은 평균적인 경우 시간 복잡도가 \(O(nlog_2n)\)으로 나타난다. 다른 정렬 알고리즘과 비교하였을 때도 가장 빠른 것으로 나타났다. 이는 퀵정렬이 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 pivot들이 추후 연산에서 제외되는 특성 등에 기인한다고 보인다.

장점

1. 속도가 빠르다.

2. 추가 메모리 공간을 필요로 하지 않는다.

단점

1. 정렬된 리스트에 대해서는 오히려 수행시간이 더 많이 걸린다.

* 이러한 불균형 분할을 방지하기 위하여 pivot을 선택할 때 단순히 리스트의 왼쪽 데이터를 사용하는 대신에 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택하곤 한다. 많이 사용되는 방법은 리스트 내의 몇 개의 데이터 중에서 크기 순으로 중간 값(median)을 pivot으로 선택하는 것이다. 일반적으로 리스트의 왼쪽, 오른쪽, 중간의 3개의 데이터 중에서 크기순으로 중간 값을 선택하는 방법(median of three)이 많이 사용된다.

---

Heap sort (히프 정렬)

 히프는 우선순위 큐를 완전 이진 트리로 구현하는 방법으로 히프는 최댓값이나 최솟값을 쉽게 추출할 수 있는 자료 구조이다. 히프에는 최소 히프와 최대 히프가 있고 정렬에서는 최소 히프를 사용하는 것이 프로그래밍하기 더 쉬워진다.

 최소 히프는 부모 노드의 값이 자식 노드의 값보다 작다. 따라서 최소 히프의 루트 노드는 가장 작은 값을 가지게 된다. 최소 히프의 이러한 특성을 이용하여 정렬할 배열을 먼저 최소 히프로 변환한 다음, 가장 작은 원소부터 차례대로 추출하여 정렬하는 방법을 히프 정렬(heap sort)이라 한다.

이 정렬은 다음 포스팅에서 자세히 다루도록 하겠다.

참고:

천인국, 공용해, 하상호, (2014). C언어로 쉽게 풀어쓴 자료구조.

http://ejklike.github.io/2017/03/04/sorting-algorithms-with-python.html