이번 글에서는 여러 가지 정렬 알고리즘을 간략하게 정리하고자 한다.
알고리즘을 4가지 특징에 따라 비교한 표는 아래와 같다.
| Algorithm | In-Place | Stable | Comparison | Complexity |
| Bubble | O | O | O | O(n^2) |
| Selection | O | X | O | O(n^2) |
| Insertion | O | O | O | O(n^2) |
| Shell | O | X | O | O(n^2) |
| Merge | X | O | O | O(nlogn) |
| Quick | O | X | O | O(nlogn) |
| Heap | O | X | O | O(nlogn) |
| Counting | X | O | X | O(n + k) |
| Radix | X | O | X | d x O(n) |
버블 정렬(Bubble Sort)
인접한 두 개의 원소를 비교하여 자리를 교환하는 방식이다.
첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서, 맨 마지막 자리로 이동하는 모습이 물속에서 물 위로 올라오는 물방울 모양과 비슷하여 버블 정렬이라고 한다.
선택 정렬(Selection Sort)
전체 원소들 중에서 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식이다.
1. 전체 원소 중에서 가장 작은 원소(or 가장 큰 원소)를 찾아 선택하여 첫 번째 원소와 자리 교환한다.
2. 두 번째로 작은 원소를 찾은 후 두 번째 자리에 위치한 원소와 교환한다.
3. 제일 마지막 원소까지 위 과정을 진행한다.
삽입 정렬(Insertion Sort)
정렬되어 있는 부분집합에 정렬할 새로운 원소의 위치를 삽입하는 방식이다.
1. 정렬할 자료를 두 개의 부분집합 S와 U로 가정한다.
2. 부분집합 S: 정렬된 앞부분의 원소들, 부분집합 U: 아직 정렬되지 않은 나머지 원소들
3. 정렬되지 않은 부분집합 U의 원소를 하나씩 꺼내서 이미 정렬되어 있는 부분집합 S의 마지막 원소부터 비교하면서 위치를 찾아 삽입한다.
4. 부분집합 U가 공집합이 되면 정렬이 완성된다.
셸 정렬(Shell Sort)
삽입 정렬을 보완한 알고리즘이며, 삽입 정렬이 어느 정도 정렬된 배열에 대해서 빠른 것에 착안하였다. 일정한 간격으로 떨어져 있는 자료들끼리 부분집합을 구성하고 각 부분집합에 있는 원소들에 대해서 삽입 정렬을 수행하는 작업을 반복하면서 전체 원소들을 정렬하는 방법이다. 전체 원소에 대해서 삽입 정렬을 수행하는 것보다 부분집합으로 나누어 정렬하게 되면 비교 연산과 교환 연산이 감소한다.
1. 부분집합의 기준이 되는 간격을 변수 interval에 저장
2. 한 단계가 수행될 때마다 interval의 값을 감소시키고 셸 정렬을 순환 호출한다.
3. interval이 1일 때까지 반복한다.
셸 정렬의 성능은 interval의 값에 따라 달라진다. 일반적으로 사용하는 interval의 값은 원소 개수의 1/2를 사용하고 한 단계 수행될 때마다 interval의 값을 반으로 감소시키면서 반복 수행한다.
합병 정렬(Merge Sort)
여러 개의 정렬된 자료의 집합을 병합하여 한 개의 집합으로 만드는 정렬하는 방법이다. 분할 정복 알고리즘을 활용하였으며 자료를 최소 단위의 문제까지 나눈 후에 차례대로 정렬하여 최종 결과를 도출한다.
분할
- 전체 자료 집합에 대하여 최소 크기의 부분 집합이 될 때까지 분할 작업을 계속한다.
병합
- 2개의 부분집합을 정렬하면서 하나의 집합으로 병합한다.
퀵 정렬(Quick Sort)
기준 값(pivot)을 중심으로 왼쪽 부분 집합과 오른쪽 부분 집합으로 분할하여 정렬하는 방법이다. 값을 비교하는 비교 정렬이며 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행 속도를 보인다.(최악의 경우 시간 복잡도 n^2이다) 합병 정렬과 달리 퀵 정렬은 리스트를 비 균등하게 분할한다.
분할
1. 기준 값을 기준으로 작은 값은 왼쪽으로 큰 값은 오른쪽으로 분할한다.
2. 기준 값을 제외한 왼쪽과 오른쪽 리스트에 대하여 순환 호출을 한다.
3. 더 이상 분할이 불가능할 때까지 반복한다.
정복
- 부분 배열을 정렬한다.
결합
- 정렬된 부분 배열들을 하나의 배열에 결합한다.
힙 정렬(Heap Sort)
완전 이진트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다. 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조이다. 내림차순 정렬을 위해서는 최대 힙을 구성하고, 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 다시 말해서 최대 힙은 부모 노드의 키값이 자식 노드의 키값보다 항상 크고, 최소 힙은 부모 노드의 키 값이 자식 노드의 키값보다 항상 작은 값을 가진다.
힙은 두 가지 조건을 만족하는 자료구조이다.
1. 구조 조건 - 완전 이진트리
2. 순서 조건 - Partial Order(Total Order의 반대말, 데이터의 일부분에 대해서 어떠한 특성을 만족하는 것)
3. 정렬해야 할 n 개의 요소들에 대한 완전 이진트리를 구성한다.
4. 최대 힙/최소 힙으로 만든다.(왼쪽 밑에서부터 조건에 맞는 값으로 변경하면 된다.)
5. delete를 통해 정렬을 한다.
- 맨 마지막 노드와 루트 노드를 교환한다.
- 현재 루트 노드에 대해 다운 힙을 진행한다.
힙 트리의 높이는 logn이며, 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비하는 시간이 logn 만큼 소요된다. 요소의 개수가 n개이므로 전체적으로 O(nlogn)의 시간이 걸린다. 이처럼 시간 복잡도가 좋다는 장점이 있으며, 전체 자료를 정렬하는 것이 아니라 가장 큰 값 몇 개만 필요할 때 아주 유용하다.
카운팅 정렬(Countjing Sort)
Counting Sort는 가장 궁금했던 정렬 방법이다. 일반적으로 가장 빠르다고 알려진 Quick Sort의 평균 시간 복잡도는 O(nlogn)인데 왜 더 빠른 Counting Sort를 이용하지 않는 것일까? 이번에 블로그를 정리하면서 해답을 알게 되었다.
Counting Sort에 대한 요약은 아래와 같다.
1. 원소 간에 비교를 하지 않으며, 각 원소가 몇 번 등장하는지 개수를 세서 정렬하는 방법이다.
2. 1번에서 구한 개수를 활용하여 누적합 배열을 구현한다.
3. 정렬을 위한 길이 n의 배열과 계수를 위한 길이 k의 배열 즉 O(n + k)의 공간 복잡도를 가진다.
3번에 대해서 주의 깊게 살펴보면 0, 0, 0, 100, 2, 0 같은 배열을 정렬할 때 의미 없는 3-99 과정을 순회해야 한다. Counting Sort의 시간 복잡도는 Quick Sort보다 훨씬 좋지만 대부분의 상황에서 엄청난 메모리 낭비를 야기할 수 있기 때문에 일정한 범위의 수가 주어진 경우 사용하는 것이 좋다고 생각한다.
기수 정렬(Radix Sort)
낮은 자리 숫자부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘이다. 비교 연산을 하지 않으며 정렬 속도가 빠르지만 메모리가 많이 필요하다는 단점이 있다.
요약
1. 0 - 9까지의 Bucket을 준비한다.
2. 모든 데이터에 대하여 가장 낮은 자리 수에 해당하는 Bucket에 차례대로 데이터를 둔다.
3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다.
4. 다음 자릿수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다.
In - Place
입력 리스트 내부에서 정렬이 이루어지는 경우를 말한다. 정렬 도중에 별도의 저장 공간을 필요로 하지 않는 알고리즘을 말한다. 위 알고리즘에서는 Counting Sort와 Radix Sort는 별도의 공간이 필요했기 때문에 In-Place 하지 않다고 말한다.
Stable
같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 말한다. UnStable과 Stable의 결괏값이 동일하게 보일 수도 있지만 문자열 혹은 주소 값을 통해서 다른 값으로 연결되어야 하는 경우에서는 Stable이 매우 중요하다.