정렬 알고리즘(Sorting Algorithm) 개념정리

개발자 강세영·2023년 10월 20일

알고리즘 자료구조 정렬 정렬 알고리즘

TIL

목록 보기

61/66

정렬 알고리즘이란?

정렬 알고리즘은 정해진 기준에 따라 데이터를 순서대로, 체계적으로 정리하는 알고리즘이다.
정렬의 목적은 탐색에 있다. 즉, 원하는 데이터를 빠르고 쉽게 찾는 것이다.
정렬 알고리즘은 시간 복잡도, 메모리 사용량(제자리 정렬), 재귀(recursion), 안정성(stability), 비교(comparison), 직렬(serial)과 병렬(parallel), 순응성(adaptability), 온라인(online) 등의 속성에 따라 분류된다.

정렬 알고리즘의 내부(internal)와 외부(external), 제자리(in-place) 정렬 개념

정렬을 수행하는 시점에 모든 데이터가 주기억장치에서 처리되면 내부 정렬, 보조기억장치에서 부분적으로 주기억장치로 옮기면서 처리되면 외부 정렬이라고 한다.
제자리 정렬은 정렬 수행 시 정렬 대상 데이터가 저장되는 공간 이외에 얼마나 많은 메모리가 필요한지를 나타내는 개념이다.
별도로 필요한 메모리가 상수 개를 넘지 않으면 제자리 정렬 알고리즘이라고 한다.
즉, 공간 복잡도가 $O(1)$ 이면 제자리 정렬 알고리즘이다.

정렬 알고리즘의 안정성(Stability) 개념

안정(stable) 정렬은 중복된 값을 입력 순서와 동일하게 정렬하는 알고리즘이다.
예를 들어 다음 그림과 같이 지역 별 발송 시각을 시간 순으로 정렬한 택배 발송 목록이 있다고 가정해보자.
안정 정렬은 기존의 시간 순으로 정렬했던 리스트를 지역명으로 재정렬 하더라도 기존 순서가 그대로 유지된 상태로 정렬이 이뤄진다.
그러나 불안정(unstable) 정렬은 시간 순으로 정렬한 리스트를 지역명으로 재정렬할 경우 기존의 정렬 순서가 무시되어 뒤섞이고 만다.
안정된 정렬 알고리즘으로는 삽입 정렬, 버블 정렬, 병합 정렬, 팀소트, 계수 정렬 등이 있다.
불안정 정렬 알고리즘으로는 선택 정렬, 퀵 정렬, 힙 정렬, 셸 정렬 등이 있다.
위의 분류는 가장 기본적인 방법으로 구현하는 경우의 분류이다. 구현을 수정하면 불안정한 정렬 알고리즘도 안정되도록 만들 수 있다.

정렬 알고리즘의 비교(Comparison) 개념

비교 정렬은 요소들을 정렬할 때 요소들의 순서에만 의존하는 알고리즘이다.
즉, 주어진 데이터들의 값을 서로 비교하여 순서에 맞게 자리를 바꿔주는 방식이다.
널리 알려진 정렬 알고리즘들은 대부분 비교 정렬이다.
수학적으로 정리된 비교 정렬의 최악의 시간 복잡도는 $O(n log n)$ 으로, 이보다 빠를 수 없다.
비교하지 않는(non-comparison) 정렬 알고리즘은 대표적으로 비둘기집 정렬(Pigeonhole sort), 버킷 정렬(Bucket sort), 계수 정렬(Counting sort), 기수 정렬(Radix sort) 등이 있다. 이러한 정렬 알고리즘은 데이터의 값을 직접적으로 비교하지 않고 데이터의 분포 등에 기반하여 정렬을 수행한다.
비교하지 않는 정렬은 비교 정렬 알고리즘이 가지는 시간 복잡도의 한계가 없지만 대신에 다른 제약조건이 있다.
예를 들어 기수 정렬은 사전 순으로 표기하고 분리하기 쉬운 숫자나 문자열에 대해서는 효율적이지만, 그렇지 않은 데이터에 대해서는 비교 정렬보다 느릴 수도 있다.

기초적인 비교 정렬 알고리즘

선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬 등이 있다.
모두 구현이 비교적 쉽고 메모리를 적게 사용하므로 제자리 정렬 알고리즘이며 공간 복잡도는 $O(1)$ 이다.
대부분의 경우 향상된 정렬 알고리즘에 비해서 비효율적이다.

선택 정렬(Selection sort)

선택 정렬은 정렬할 데이터의 요소 중 가장 작은 값을 찾아서 이동시키는 과정을 모든 요소에 대해 반복하는 정렬 알고리즘이다.
오름차순으로 정렬하는 경우, 처음엔 배열에서 가장 작은 값을 찾아서 배열의 맨 앞에 있는 요소와 교환하고 그 다음부터는 이미 정렬된 부분을 제외하고 나머지 부분에서 가장 작은 값을 찾아서 나머지 부분의 맨 앞으로 이동시키는 방식으로 배열의 끝까지 수행한다.
- 예시 데이터: [6, 3, 5, 4, 2, 1]
- 정렬 과정: 첫 요소(6)의 다음 요소부터 비교하여 제일 작은 값을 찾아서 서로 교환 -> [1 | 3, 5, 4, 2, 6]->[1, 2 | 5, 4, 3, 6] -> [1, 2, 3 | 4, 5, 6] -> 여기서 정렬된 상태가 됐지만 끝까지 진행 -> ... -> 정렬 완료.
버블 정렬이나 삽입 정렬과는 다르게 매 반복마다 요소의 교환 발생 여부로 정렬이 이미 완료됐는지 판단할 수 없다. 따라서 선택 정렬의 시간 복잡도는 모든 상황에서 동일하다.
선택 정렬의 비교 횟수는 항상 $n(n-1)/2$ 이므로 시간 복잡도는 항상 $O(n^2)$ 이 된다.
선택 정렬과 버블 정렬의 최악의 시간 복잡도는 같다. 하지만 선택 정렬은 버블 정렬보다 데이터 교환이 적게 발생하기 때문에 일반적으로 선택 정렬이 버블 정렬보다 빠르다.
일반적인 구현은 불안정 정렬이다.

버블 정렬(Bubble sort)

버블 정렬은 인접한 두 요소를 비교하면서 왼쪽 요소의 값이 더 크면 오른쪽 요소와 자리를 바꾸는 과정을 반복하는 정렬 알고리즘이다.
정렬 과정에서 큰 요소들이 뒤로 옮겨질 때 거품을 내며 물에 가라앉는 것 같은 모습이라 버블 정렬이라 부른다.
정렬을 수행하는 방향에 따라 왼쪽에서 오른쪽 또는 오른쪽에서 왼쪽으로 구분하며 어떻게 하던지 결과는 같다.
- 예시 데이터: [6, 3, 5, 4, 2, 1], 왼쪽에서 오른쪽 방향으로 오름차순 정렬.
- 정렬 과정: [(3, 6), 5, 4, 2, 1] -> [3, (5, 6), 4, 2, 1] -> [3, 5, (4, 6), 2, 1] -> [3, 5, 4, (2, 6), 1] -> [3, 5, 4, 2, (1, 6)] -> 첫번째 요소부터 다섯번째까지 비교 반복 -> ... -> 첫번째 요소부터 네번째까지 비교 반복 -> ... -> 첫번째 요소와 두번째 요소를 비교할 때까지 반복하거나 그 전에 정렬이 완료된 상태가 되면 종료.
버블 정렬의 비교 횟수를 정리하면 다음과 같다. $(n-1) + (n-2) + … + 3 + 2 + 1 = n(n-1)/2$
따라서 버블 정렬의 최악의 경우 시간 복잡도는 $O(n^2)$ 이 된다.
버블 정렬시 요소의 교환 여부를 확인하여 교환이 이루어지지 않았으면 이미 정렬이 안료된 것으로 판단할 수 있다.
보통 외부 반복문 시작 시 요소의 교환 여부를 판단하기 위한 플래그 변수를 True로 초기화하고 내부 반복문에서 요소간 교환이 이루어지면 플래그 변수를 False로 변경하는 방법으로 구현한다.
내부 반복문이 끝난 후 플래그 변수가 True이면 데이터 교환이 발생하지 않은 것이며 이는 정렬이 이미 완료된 상태를 의미하므로 연산을 조기에 종료할 수 있다.
대상 데이터가 버블 정렬 수행 전에 이미 정렬된 상태라면 1회차 반복에 정렬이 끝나기 때문에 최선의 경우 시간 복잡도는 $Ω(n)$ 이다.
선택 정렬 또는 삽입 정렬과 최악의 시간 복잡도는 동일하지만 대부분의 상황에서 버블 정렬은 선택 정렬이나 삽입 정렬보다 데이터의 교환이 더 많이 발생하므로 비효율적이다.
데이터가 이미 정렬된 상황은 드물기 때문에 실제로는 대부분의 경우 성능이 가장 나쁜 정렬 알고리즘이다.
안정 정렬이다.

삽입 정렬(Insertion sort)

삽입 정렬은 배열을 정렬된 부분과 미정렬 부분으로 구분하여 미정렬 부분의 첫 번째 요소를 정렬된 부분의 제자리에 삽입하는 방식으로 정렬하는 알고리즘이다.
보통 배열의 1번 인덱스부터 끝까지 반복하면서 현재 요소의 값을 저장해놓고, 현재 요소의 앞 요소([i - 1])가 현재 요소 보다 크다면 현재 요소보다 큰 값이 더 이상 나오지 않는 위치까지 해당 범위의 요소를 한 칸씩 이동시키는 방식으로 구현한다. 이 내부 반복문이 끝나면 현재 요소의 제 위치를 찾은 것이므로 그 위치의 값을 앞서 저장해놨던 현재 요소 값으로 바꾼다.
- 예시 데이터: [6, 3, 5, 4, 2, 1]
- 정렬 과정: 첫번째 요소는 앞 요소가 없으므로 두번째부터 시작 -> [3, 6 | 5, 4, 2, 1] -> [3, 5, 6 | 4, 2, 1] -> ... -> 정렬 완료
버블 정렬과 마찬가지로 요소의 이동 여부를 판단하여 정렬을 조기 종료시킬 수 있다.
이는 보통 외부 반복문에서 현재 요소가 앞 요소보다 크면 다음 반복으로 넘기는(continue) 방식으로 구현한다.
이렇게 하면 정렬 대상 데이터가 이미 정렬된 경우 각 요소의 제자리를 찾아 이동시키는 내부 반복문은 실행되지 않고, 데이터 전체를 순회하는 외부 반복문만 실행되고 끝나기 때문에 삽입 정렬의 최선의 시간 복잡도는 $Ω(n)$ 이 된다.
선택, 버블 정렬과 마찬가지로 최악의 시간 복잡도는 $O(n^2)$ 이다.
삽입 정렬과 버블 정렬의 최악의 시간 복잡도는 같지만, 대부분의 상황에서 버블 정렬보다 데이터의 교환 횟수가 적으므로 실제로는 삽입 정렬이 버블 정렬보다 빠르다.
삽입 정렬과 선택 정렬은 모두 k번째 정렬 후에 k번째 요소가 제자리에 배치된다는 점은 비슷하다. 그러나 선택 정렬은 정렬이 아직 완료되지 않은 모든 요소를 비교해서 최소값을 찾아야 하는데 반해 삽입 정렬은 나머지 전체 요소가 아닌 필요한 부분만 비교하면 되기 때문에 일반적으로 삽입 정렬이 더 효율적이다.
삽입 정렬은 데이터의 크기가 작은 경우 효율적인 정렬 방법이며 안정 정렬이다.
삽입 정렬을 보완한 정렬 알고리즘으로 셸 정렬이 있다.

셸 정렬(Shellsort)

셸 정렬은 도널드 셸이 개발한 정렬 알고리즘으로, 삽입 정렬을 보완한 알고리즘이다.
삽입 정렬과 비슷하지만 삽입 정렬과는 다르게 불안정 정렬이다.
오름차순 셸 정렬의 수행 과정은 다음과 같다.
1. 셸 정렬을 하기 위해서는 먼저 간격(gap)을 정해야 한다. 간격은 일반적으로 데이터의 크기를 2로 나눈 몫으로 정한다.
2. 데이터의 첫 요소부터 1번에서 정한 간격만큼 떨어진 데이터 요소의 값을 비교하여 뒤의 요소가 더 크면 서로 교환한다. 이런식으로 데이터의 끝까지 진행한다.
3. 더 이상 비교할 요소가 없으면 기존의 간격을 2로 나눈 몫으로 간격을 재설정하고 2번부터 다시 반복한다. 만약 간격이 0이 되면 정렬이 완료된 것이므로 연산을 종료한다.
셸 정렬은 간격 값에 따라 성능이 달라진다. 일반적으로 데이터의 크기를 2로 나눈 몫으로 정하지만 크기를 3으로 나눈 몫에 1을 더한 값을 사용하는 방법이 더 효율적이라고 알려져 있다.
셸 정렬에서 가장 효율적인 간격을 정하는 방법은 아직 알려져 있지 않다. 가장 효율적인 간격을 설정한 경우 셸 정렬의 시간 복잡도는 다음과 같다.
- 최악: $O(n(log(n))^2)$
- 평균: $Θ(n(log(n))^2)$
- 최선: $Ω(n log n)$

향상된 비교 정렬 알고리즘

퀵 정렬(Quicksort)

퀵 정렬은 토니 호어가 개발하였으며 분할 정복(divide and conquer)에 기반한 정렬 알고리즘이다.
퀵 정렬의 과정은 다음과 같다.
1. 기준 요소 선정 및 정렬 대상 분류: 기준이 될 요소를 선정하여 기준 요소(pivot)의 값 보다 작은 요소는 기준 요소의 왼쪽으로, 큰 요소는 오른쪽으로 옮긴다.
2. 정렬 대상 분할: 기준 요소의 왼쪽에는 기준 요소보다 작은 요소의 그룹, 오른쪽에는 큰 요소의 그룹이 생긴다. 여기에서 왼쪽과 오른쪽 그룹에 대해 1번을 반복한다.
3. 반복: 그룹의 크기가 1 이하가 되어 더 이상 분할할 수 없을 때까지 1과 2의 과정을 반복하면 정렬이 완료된다. 반복은 재귀적으로 구현할 수 있다.
퀵 정렬은 분할 과정(partition step)에서 기준 요소를 선정하는 방법에 따라 여러 가지의 변형이 있으며 이에 따라 성능도 달라진다.
퀵 정렬은 데이터가 이미 정렬되어 있거나 역순으로 정렬된 경우 최악의 성능을 보이지만 데이터가 무작위로 배치된 경우에는 성능이 우수한 알고리즘이다.
최선의 경우 퀵 정렬 비교 횟수는 재귀 호출의 깊이 X 각 재귀 호출 단계에서의 비교 횟수가 되므로 $n log n$ 이다. 따라서 최선의 시간 복잡도는 $Ω(n log n)$ 이다.
퀵 정렬의 평균적인 비교 횟수를 수학적으로 정리하면 $1.39 \times nlogn$ 이므로(출처: Algorithms, 4th Edition) 평균적인 시간 복잡도는 $Θ(n log n)$ 이 된다.
최악의 경우엔 매 재귀 호출마다 $1 : n-1$ 으로 분할해야 하므로 총 비교 횟수는 다음과 같이 정리된다.
$(n-1) + (n-2) + … + 3 + 2 + 1 = n(n-1)/2$
따라서 최악의 경우 시간 복잡도는 $O(n^2)$ 이다.
기준 요소(피벗)를 분할된 배열의 첫번째 요소로 정하는 경우 오름차순 또는 내림차순으로 이미 정렬된 배열을 퀵 정렬하면 최악의 성능이 나오게 된다.
퀵 정렬은 최악의 경우 $O(n^2)$ 이기 때문에 비효율적이라고 생각할 수 있지만 위에서 언급했듯이 분할 과정에서 피벗을 잘 고르면 똑같은 데이터라도 최악의 분할 케이스는 매우 드물게 된다. 그래서 실제로는 상당히 효율적인 정렬 알고리즘이다.
피벗 선택 방법으로는 매 분할마다 첫번째 요소를 선택(로무토 파티션), 마지막 요소를 선택(호어 파티션), 무작위로 선택, 가운데 위치한 요소를 선택, 3개나 9개의 요소를 고르고 이들의 중앙값을 선택 등 다양한 방법이 있다.
일반적인 퀵 정렬은 불안정 정렬이다.

병합 정렬(합병 정렬, Merge sort)

병합 정렬은 존 폰 노이만이 개발하였으며 퀵 정렬과 비슷하게 분할 정복에 기반한 정렬 알고리즘이다.
병합 정렬의 과정은 다음과 같다.
1. 정렬할 데이터를 반으로 나눈다. 나눈 데이터 집합의 크기가 2 이상이면 크기가 1이 될 때 까지 반복한다.
2. 하위 데이터 집합 둘을 정렬 순서대로 병합한다.
3. 2번에서 병합한 데이터들끼리 정렬 순서를 맞춰서 병합한다. 이런식으로 정렬이 끝날 때까지 반복한다.
병합 정렬의 시간 복잡도는 언제나 $O(n log n)$ 이다.
병합 정렬의 공간 복잡도는 $O(n)$ 이다.
일반적으로 병합 정렬의 실제 성능은 퀵 정렬보다 느리고 메모리가 더 필요하지만 언제나 동일한 시간 복잡도를 가지므로 데이터의 상태에 영향을 덜 받는다는 장점이 있다.
또한 병합 정렬은 안정 정렬이라는 장점도 있다.

팀소트(Timsort)

팀소트는 팀 피터스가 파이썬을 위해 개발한 정렬 알고리즘으로, 병합 정렬과 삽입 정렬을 기반으로 하는 하이브리드 정렬 알고리즘이다.
팀소트는 파이썬 뿐만 아니라 자바, 안드로이드, GNU 옥타브, V8 엔진, 스위프트, 러스트 등에서도 사용된다.
팀소트는 데이터가 뒤죽박죽 섞여 있는 일은 거의 일어나지 않으며, 실제로는 대부분의 데이터가 이미 정렬되어 있을 것이라고 가정하여 실제 데이터에 대해 고성능을 낼 수 있도록 설계한 알고리즘이다.
병합 정렬은 원소의 개수가 적을 때 오버헤드가 크기 때문에 파티션 크기가 특정 값 이하(보통 16 또는 32)가 되면 삽입 정렬을 사용한다. 이외에도 팀소트에는 어느 정도 정렬된 데이터에서 이득을 볼 수 있는 여러 가지의 휴리스틱 알고리즘이 포함돼있다.
팀소트는 안정 정렬이며 병합 정렬과 비슷한 특징을 가지지만 대부분의 경우 병합 정렬보다 더 빠르다.
팀소트의 시간 복잡도는 병합 정렬과 동일하게 최악과 평균이 $O(n log n)$ 이며 최선은 $Ω(n)$ 이다.
팀소트의 공간 복잡도는 $O(n)$ 이다.
파이썬 3.11 부터는 팀소트의 버그와 효율성을 개선한 파워소트(Powersort) 알고리즘이 사용되고 있다.

힙 정렬(Heapsort)

힙 정렬은 최대 힙 또는 최소 힙을 활용하여 정렬하는 알고리즘이다.
일반적으로 최대 힙을 사용하면 오름차순 정렬, 최소 힙을 사용하면 내림차순 정렬이 된다.
힙 정렬의 과정은 다음과 같다.
1. 데이터를 전부 힙에 삽입하여 힙 배열로 변환한다. 힙에서 요소를 삽입하는 과정과 같다.
2. 힙의 뿌리 노드는 항상 최소값 또는 최대값을 가지므로 뿌리 노드를 힙에서 제거하여 배열의 맨 뒤로 옮긴다. 힙에서 요소를 제거하는 과정과 같다.
3. 힙이 빈 상태가 될 때까지 2의 과정을 반복하면 힙 구조를 유지하는 배열은 없으지므로 남은 배열의 뒷부분은 정렬된 데이터만 남게 된다.
힙 정렬은 불안정 정렬이며 공간 복잡도는 $O(1)$ 이다.
힙 정렬의 시간 복잡도는 모든 경우에서 $O(n log n)$ 이다.

트리 정렬(Tree sort)

트리 정렬은 입력 데이터로부터 이진 탐색 트리를 만든 다음 그 트리를 순회하여 정렬된 데이터를 얻는 정렬 알고리즘 이다.
힙 정렬과 비슷해 보이지만 요소의 크기에 따라 부모 노드의 왼쪽 자식 또는 오른쪽 자식이 된다는 점이 다르다.
트리 정렬의 과정은 다음과 같다.
1. 정렬할 데이터를 이진 탐색 트리에 삽입한다. 이 과정에서 키(key)가 같은 요소들의 순서는 유지된다.
2. 정렬을 위해 만든 이진 탐색 트리를 중위 순회하여 요소들을 출력한다. 중위 순회는 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드 순으로 순회하는 방법이다.
트리 정렬의 시간 복잡도의 최선과 평균은 모두 $O(n log n)$ 이다.
자가 균형(self-balanced) 이진 탐색 트리를 사용할 경우 트리 정렬의 최선의 시간 복잡도는 $O(n log n)$ 이지만 오버헤드가 커진다.
균형이 잡히지 않은 트리를 사용할 경우엔 탐색 속도가 느려질 수 있기 때문에 최악의 시간 복잡도는 $O(n^2)$ 이 된다.
트리 정렬은 안정 정렬이다.
트리 정렬의 공간 복잡도는 $O(n)$ 이다.

비교하지 않는(non-comparison) 정렬 알고리즘

비교하지 않는 정렬 알고리즘은 대표적으로 계수 정렬, 기수 정렬, 버킷 정렬 등이 있다. 이 알고리즘들은 모두 데이터의 분포를 기반으로 정렬하는 알고리즘이다.
이러한 정렬 알고리즘은 데이터의 분포를 미리 알고 있고, 그 범위가 작은 경우 상당히 유용하지만 그렇지 않은 경우 비효율적일 수 있다. 또한 정수가 아닌 숫자(non-integers)에 대해선 정렬하지 못할 수도 있다.

계수 정렬(Counting sort)

계수 정렬은 입력 데이터의 값들이 어떤 범위 안에 존재할 때 적용할 수 있는 정렬 알고리즘이다.
계수 정렬은 입력 데이터의 각 요소들 중에서, 어떤 한 요소보다 작거나 같은 값을 갖는 데이터의 개수를 세어서 정렬할 위치를 찾는 방식으로 이루어진다.
자연수에 대한 오름차순 계수 정렬 과정을 설명하면 다음과 같다.
예시 데이터: [7, 5, 9, 8, 4, 5, 7, 5]
1. 입력 데이터에서 최소값과 최대값을 구한다. 예시 데이터에선 4와 9이다.
2. 입력값들의 출현횟수를 담기 위한 계수 배열을 만든다. 예시 데이터에선 최소값이 4이고 최대값이 9이므로 크기가 6인 배열을 만들고 값은 0으로 초기화한다.
3. 입력 데이터의 처음부터 끝까지 각 요소의 출현횟수를 2번에서 만든 계수 배열에 저장한다. 위의 예시에서 7이면 계수 배열의 네번째 값(4, 5, 6, 7 이므로)에 1을 더하는 식으로 하면된다. 예시 데이터에 대한 계수 배열의 값은 다음과 같다.
  [1, 3, 0, 2, 1, 1]
4. 3번에서 완성된 계수 배열을 누적합 배열로 바꾼다. 예시 데이터에선 다음과 같다.
  [1, 4, 4, 6, 7, 8]
5. 위에서 구한 누적합 배열로 실제 정렬을 수행한다. 이 과정은 입력 데이터의 마지막 요소부터 앞쪽으로 진행하면서 차례로 하나씩 뽑아서 누적합 배열의 값을 인덱스로 사용하고, 정렬을 위해 새롭게 생성한 배열에 배치하여 정렬하는 방식으로 이루어진다.
- 예시 데이터에서 마지막 요소는 5인데, 이는 누적합 배열에서 4라는 값을 가지므로 정렬된 배열의 3번 인덱스(인덱스가 0으로 시작할 경우)에 5를 넣고, 누적합 배열의 값은 1을 빼서 3으로 바꿔준다. 이런식으로 입력 데이터의 첫 요소까지 완료하면 정렬된 배열이 완성된다.
입력값의 범위를 $k$ 라고 할 때 계수 정렬의 시간 복잡도는 항상 $O(n+k)$ 이고 공간 복잡도는 $O(k)$ 이다.
계수 정렬은 별도의 메모리가 필요하므로 제자리 정렬은 아니다.
입력값의 범위가 입력 데이터의 개수보다 작거나 비례하는 경우, 시간 복잡도가 $O(n)$ 이 되므로 유용한 정렬 알고리즘이다.
일반적으로 계수 정렬은 안정적인 정렬이다.

기수 정렬(Radix sort)

기수 정렬은 주어진 데이터 요소의 기수를 기준으로 비교 없이 정렬하는 알고리즘이다. 입력 데이터의 값을 자릿수별로 나누고 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리즘을 적용하는 방법이다.
기수 정렬은 정수, 단어, 천공 카드, 플레잉 카드 등 사전순으로 정렬할 수 있는 데이터에 적용할 수 있다.
낮은 자리에서 높은 자리로 정렬하면 LSD(Least Significant Digit, Right-to-Left) 기수 정렬, 높은 자리에서 낮은 자리로 정렬하면 MSD(Most Significant Digit, Left-to-Right) 기수 정렬이라고 부른다.
예를 들어 1234라는 수에 대해 1부터 정렬하면 MSD고, 4부터 정렬하면 LSD이다.
기수 정렬은 자릿수가 적은 데이터를 정렬할 때 상당히 효율적인 알고리즘이다. 그러나 실수나 문자열 같이 자릿수가 큰 데이터에 대해서는 비효율적이다.
데이터의 최대 자릿수를 $k$ 라고 할 때 기수 정렬의 시간 복잡도는 항상 $O(nk)$ 이며, 공간 복잡도는 $O(n+k)$ 이다.
입력 데이터의 자릿수가 상수인 경우, 시간 복잡도가 $O(n)$ 이 되므로 유용한 정렬 알고리즘이다.
일반적인 기수 정렬은 요소의 순서가 유지되므로 안정 정렬이지만, 구현 방법에 따라 불안정 정렬이 될 수도 있다.
기수 정렬은 별도의 버킷을 만들어서 정렬하는 방식이므로 제자리 정렬은 아니다.
십진수 자연수에 대한 오름차순 LSD 기수 정렬 과정은 다음과 같다.
1. 정렬 대상 데이터 요소의 최대값을 구한다.
2. 정렬할 요소를 기수(1로 시작) 별로 나누어 별도의 버킷에 삽입한다.
  요소를 기수로 나눈 몫에 10의 나머지 연산을 하면 자릿수를 알 수 있다.
  예를 들면 100은 일의 자릿수가 0이므로 0번 버킷에, 23은 3번 버킷에 삽입된다.
  기수가 요소보다 크면 해당 자릿수를 0으로 취급한다.
3. 버킷에 저장된 데이터를 0번부터 9번까지 순서대로 꺼내고 이를 새로운 정렬 대상 데이터로 삼는다.
4. 기수에 10을 곱하여(일의 자리 -> 십의 자리 -> 백의 자리 ...) 증가시키고 2번부터 다시 반복한다. 기수가 1번에서 구한 최대값보다 커지면 연산을 종료한다.
입력 데이터: {170, 45, 75, 90, 2, 802, 2, 66}, 최대값: 802
1. 1의 자리에 대해 정렬: 0:{170, 90}, 2:{2, 802, 2}, 5:{45, 75}, 6:{66}
2. 10의 자리에 대해 정렬: 0:{02, 802, 02}, 4:{45}, 6:{66}, 7:{170, 75}, 9:{90}
3. 100의 자리에 대해 정렬: 0:{002, 002, 045, 066, 075, 090}, 1:{170}, 8:{802}
4. 1000은 최대값을 초과하므로 정렬을 종료한다. 마지막 정렬 결과를 0번 버킷부터 9번 버킷까지 순서대로 모두 합치면 정렬된 데이터가 나오게 된다.

버킷 정렬(Bucket sort)

버킷 정렬은 입력 데이터 값의 범위에 따라 균등한 버킷들을 만들고, 각 요소를 해당하는 버킷에 넣고 정렬을 수행하는 알고리즘이다.
버킷의 개수를 $k$ 라고 할 때 버킷 정렬의 시간 복잡도는 최선과 평균의 경우 $O(n+k)$ , 최악의 경우 $O(n^2)$ 이다.
버킷 정렬의 공간 복잡도는 $O(n)$ 이다.
입력 데이터의 값이 특정 범위 안에서 확률적으로 균등하게 분포되고, 버킷의 개수가 입력 데이터의 개수에 비례할 경우, 버킷 정렬의 시간 복잡도가 선형시간이 되기 때문에 유용하다.
계수 정렬이나 기수 정렬과 마찬가지로 안정적이며, 제자리 정렬이 아니다.
버킷 정렬의 수행 과정을 예를 들어 설명하면 다음과 같다.
- 예시 데이터: [85, 68, 65, 100, 88, 61, 82, 95]
1. 입력값의 범위를 계산한다. 위 데이터의 최소값은 61, 최대값은 100이므로 범위는 61~100이다.
2. 각 구간의 크기를 정하고 이를 이용하여 버킷을 만든다. 만약 크기가 5라면 8개의 버킷이 생성된다(61~65, 66~70, ..., 96~100)
3. 입력 데이터의 각 요소를 해당하는 버킷에 삽입한다. 버킷은 배열이나 연결 리스트 같은 자료구조로 나타낼 수 있다.
4. 각 버킷별로 삽입 정렬이나 병합 정렬 등의 정렬을 수행한다.
5. 모든 버킷을 순서대로 합치면 정렬된 배열이 완성된다.

정렬 알고리즘별 시간 복잡도와 공간 복잡도 정리

정렬 알고리즘의 실제 성능은 이론적인 시간 복잡도와는 다르게 나올 수 있다.
특히 퀵 정렬은 최악의 경우에서도 다른 정렬보다 정렬이 빠르게 완료되는 경우가 많다.
이러한 현상의 원인으로는 하드웨어 입출력 시간, CPU와 메모리의 작동 방식, 컴파일러의 최적화 작업 등이 있다.

그 외의 정렬 알고리즘

보고소트(Bogosort)

보고소트는 bogus와 sort의 합성어로 멍청한 정렬이라는 뜻이다.
입력 데이터를 무작위로 섞어서 정렬이 됐는지 검사하여 정렬이 됐다면 종료하고 정렬이 안됐다면 다시 무작위로 섞는 것을 무한 반복하는 알고리즘이다.
최선의 경우 첫 반복에 정렬이 완료되므로 시간 복잡도는 $\Omega(n)$ 이다.
최악의 시간 복잡도는 무한대( $\infty$ ) 또는 $O(n\times n!)$ 이며 제자리 정렬이다.
매우 비효율적인 알고리즘이라 실제로 사용할 일은 없지만 특수한 문제에 대해 유전 알고리즘 등과 결합하여 사용하는 경우가 있다.
정렬 검사 시 보고소트를 재귀호출하여 더욱 비효율적으로 만든 보고보고소트(Bogobogosort)라는 변형이 있다.

바이토닉 정렬(Bitonic sorter)

바이토닉 정렬은 켄 배처가 개발한 병렬(parallel) 방식의 정렬 알고리즘이다.
이 알고리즘은 정렬 네트워크(sorting network)를 구축하여 정렬한다.
비교기 네트워크(comparator networks)는 고정된 수의 와이어(wire)와 비교기(comparator)로 구성된 추상 장치이다.
와이어는 값을 전달하는 역할을 하며 비교기는 와이어 쌍들을 연결하여 와이어의 값의 순서가 잘못된 경우 값을 교환하는 역할을 한다.
고정된 수의 값에 대해 정렬을 수행하도록 설계된 비교기 네트워크를 정렬 네트워크라고 한다.
정렬 네트워크는 임의로 큰 입력을 처리할 수 없으며 이전 비교 결과에 관계없이 비교 순서가 미리 설정된다. 따라서 더 많은 양의 입력 데이터를 정렬하려면 새로운 정렬 네트워크를 구축해야 한다. 이 부분이 일반적인 비교 정렬 알고리즘과의 가장 큰 차이점이다.
이처럼 비교 시퀀스가 독립적이므로 병렬성이 우수하여 GPU 같이 병렬 연산에 적합한 하드웨어 또는 아키텍처를 이용하여 정렬할 때 유용한 알고리즘이다.
이 알고리즘의 수행과정을 간단하게 나타내면 다음과 같다.
1. 입력 데이터를 바이토닉 수열(bitonic sequence)로 변환한다.
  바이토닉 수열은 k번째 요소 전 까지는 증가하는 순서로 정렬되고, k번째 요소 다음부터는 감소하는 순서로 정렬되는 수열이다. 반대방향(감소, k, 증가) 또한 가능하다.
2. 정렬 네트워크를 사용하여 바이토닉 수열을 정렬한다.
3. 정렬된 데이터를 반환한다.
이 알고리즘을 병렬 실행할 경우의 시간 복잡도는 모든 경우에서 $O(\log ^{2}(n))$ 으로 동일하며 공간 복잡도는 $O(n\log ^{2}(n))$ 이다.

참고자료

개발자 강세영

이전 포스트

힙(Heap) 개념정리

다음 포스트

정렬 알고리즘(Sorting Algorithm) 개념정리

TIL

정렬 알고리즘이란?

정렬 알고리즘의 내부(internal)와 외부(external), 제자리(in-place) 정렬 개념

정렬 알고리즘의 안정성(Stability) 개념

정렬 알고리즘의 비교(Comparison) 개념

기초적인 비교 정렬 알고리즘

선택 정렬(Selection sort)

버블 정렬(Bubble sort)

삽입 정렬(Insertion sort)

셸 정렬(Shellsort)

향상된 비교 정렬 알고리즘

퀵 정렬(Quicksort)

병합 정렬(합병 정렬, Merge sort)

팀소트(Timsort)

힙 정렬(Heapsort)

트리 정렬(Tree sort)

비교하지 않는(non-comparison) 정렬 알고리즘

계수 정렬(Counting sort)

기수 정렬(Radix sort)

버킷 정렬(Bucket sort)

정렬 알고리즘별 시간 복잡도와 공간 복잡도 정리

그 외의 정렬 알고리즘

보고소트(Bogosort)

바이토닉 정렬(Bitonic sorter)

참고자료

힙(Heap) 개념정리

탐색 알고리즘 & 이진 탐색 트리 개념정리

0개의 댓글