[DS] 11. 여러가지 정렬 방법
정렬의 개념과 복잡도, 여러 정렬들의 방식과 비교
정렬(Sort)?
데이터를 특정 기준에 따라, 오름차순이나 내림차순으로 재배열하는 것.
간단히 말하면, 레코드들을 키값의 순서로 재배열하는 작업이다.
예시로 학생 정보를 정렬한다면 학생 한 명의 정보 묶음이 레코드이고, 이 각각의 정보들(이름/학번/주소 등)이 필드에 해당한다. 이때 성적순으로 정렬한다면 성적 필드가 정렬의 기준점인 키가 된다.
대개 정렬 알고리즘의 효율성을 평가하는 기준은, 정렬을 위해 필요한 비교 연산과 이동 연산의 횟수가 기준이다. 그 외에도 추가적인 메모리 사용량과 안정성 등을 함께 고려할 수 있다.
정렬 알고리즘의 분류
구현 복잡도와 효율성
| 구현 복잡도 | (비교적) 효율성 | 종류 |
|---|---|---|
| 단순 | 비효율적 | 선택 정렬, 삽입 정렬, 버블 정렬 등 |
| 복잡 | 효율적 | 셸 정렬, 합병 정렬, 퀵 정렬, 힙 정렬, 기수 정렬 등 |
내/외부 정렬 여부
| 종류 | 설명 |
|---|---|
| 내부 정렬 | 정렬하기 전, 정렬할 모든 데이터를 메인 메모리에 올려놓고 수행하는 정렬. |
| 외부 정렬 | 외부 기억장치에 대부분의 데이터가 존재한 상태에서, , 일부만 메모리에 올려 수행하는 정렬. |
이 글에서는 내부 정렬만을 다룬다.
안정성 여부
안정성이란, 동일한 키를 가진 레코드들의 상대적인 순서가 정렬 후에도 유지됨이 보장되는 특성.
예를 들어 다음 레코드를 점수순으로 정렬한다고 가정한다.
1
(A, 80), (B, 90), (C, 80)
안정적인 정렬에서는 같은 점수 80을 가진 A와 C의 순서가 그대로 유지된다. (A가 C보다 앞에 존재한다.)
1
2
(A, 80), (C, 80), (B, 90) // 안정적 (A, C 순서유지가 항상 보장)
(C, 80), (A, 80), (B, 90) // 불안정적 (A, C 순서가 뒤바뀜 or 뒤바뀔 수 있음)
반대로 두 레코드의 상대적인 순서가 바뀔 가능성이 있다면 불안정한 정렬이다.
추가 메모리 사용 여부
제자리 정렬이란, 추가적인 메모리의 사용 없이 현재 저장된 공간 안에서 이뤄지는 정렬.
정렬 과정에서, 임시 저장용으로 별도의 컨테이너를 사용할 필요가 없는 정렬이 제자리 정렬이다.
정렬의 종류
선택 정렬(Selection Sort)
원리
선택 정렬은 단순하게, 제일 작은 것 부터 뽑아와서 앞과 교환하며 정렬하는 방식이다.
정확히는 아직 정렬되지 않은 구간에서 가장 작은 값을 선택해, 해당 구간의 첫 번째 값과 교환하는 과정을 반복한다.
분석
선택 정렬은 이미 정렬된 것을 제외하고는, 계속해서 남은 자료들을 탐색하는 과정이 추가된다. 때문에 정렬에 소요되는 시간은 다음과 같다.
\[(n - 1) + (n - 2) + \cdots + 1 = \frac{n(n - 1)}{2}\]이를 시간복잡도로 나타내면, 최선/평균/최악 모두 $O(n^2)$이다. 때문에 효율적인 편은 아니다.
대신 구현이 매우 간단하고, 이동 횟수가 미리 결정된다는 장점이 있다. 제자리 정렬이기에 추가 메모리를 사용하지 않으며, 멀리 떨어진 값을 교환하는 과정으로 인해 안정성은 보장되지 않는다. (불안정적이다.)
삽입 정렬(Insertion Sort)
원리
삽입 정렬은 단순하게, 맨 앞의 값부터 하나씩 확인해보며 앞으로 당겨오는 식으로 정렬하는 방식이다.
옮기는 과정에서 앞에 자리를 만들기 위해 뒤의 값들을 한칸씩 밀어내는 과정이 필요하다.
마치 사람이 손에 든 카드 순서를 앞에서부터 하나씩 정렬하는 것과 유사하다.
분석
이미 정렬된 데이터에서는 각 원소가 바로 제자리에 있으므로 이동은 일어나지 않고 비교만 한 번씩 돈다. 이때 시간복잡도는 $O(n)$이 된다.
그러나 최악의 경우(역순으로 정렬된 데이터)라면 각 값을 정렬된 구간의 맨 앞으로 이동해야 한다. 이 경우 과정에 소요되는 시간은 아래와 같다.
\[1 + 2 + \cdots + (n - 1) = \frac{n(n - 1)}{2}\]비교와 이동 횟수가 모두 증가하여 시간복잡도는 $O(n^2)$이 된다. 때문에 이 역시 그다지 효율적이지 않다.
추가적인 메모리를 쓰지 않기에 제자리 정렬이며, 같은 값을 서로 뛰어넘어 이동시키지 않으므로 안정적인 정렬이다.
버블 정렬(Bubble Sort)
원리
버블 정렬은 서로 인접한 두 값을 비교하고, 순서가 맞지 않으면 교환하는 과정을 반복한다.
처음부터 끝으로 진행하는 과정을 반복하며 가장 높은 수부터 뒤에 정렬되는 방식이다. (오름차순 기준)
큰 값이 수면 위로 떠오르는 모습과 비슷하여 버블 정렬이라 부른다.
분석
대부분의 경우 일정하게 비교연산을 수행한다. 때문에 $O(n^2)$의 시간복잡도를 가진다.
다만 이미 정렬되어있는 경우, 삽입 정렬과 마찬가지로 비교 연산만 한번 돈다. 이때 시간복잡도는 $O(n)$이다.
버블 정렬은 제자리 정렬이며, 같은 값을 직접 교환하지 않으므로 안정적인 정렬이다.
셸 정렬(Shell Sort)
원리
셸 정렬은, 삽입 정렬이 어느 정도 정렬된 데이터에서는 상당히 빠르다는 점에 착안한 정렬이다.
먼저 일정한 간격 gap으로 떨어진 원소들을 하나의 부분 배열로 보고 삽입 정렬한다. 이후 gap을 점차 줄여가며 같은 작업을 반복하고, 마지막에는 gap이 1이 되어 일반적인 삽입 정렬을 수행한다.
즉, 구간별로 쪼개서 삽입 정렬을 반복하며 점차 합쳐가는 셈이다. 사실상 삽입 정렬의 단점을 보완한 느낌.
분석
삽입 정렬에서는 멀리 떨어진 값을 제자리로 옮기기 위해 여러 번의 이동이 필요했다. 대신 셸 정렬은 큰 gap을 통해 한 번에 더 먼 거리로 값을 이동시킬 수 있다. 즉 삽입 정렬로써는 최악에 가까운 케이스의 경우, 이동에 드는 비용을 상당량 줄일 수 있다.
그렇다고 해도 최악의 시간복잡도는 $O(n^2)$이다. 그래도 평균 성능은 $O(n^{1.5})$ 정도로, 일반적인 삽입 정렬보다 좋은 경우가 많다.
셸 정렬은 제자리 정렬이지만, 멀리 떨어진 원소를 이동시키는 과정 상 같은 Key 값의 기존 순서가 보장되지 않는다. 때문에 불안정적이다.
합병 정렬(Merge Sort)
원리
셸 정렬은 일정 간격의 원소끼리 묶어서 처리했다면, 합병 정렬은 단순히 반씩 나눠가면서 잘개 쪼개서 처리하는 방식이다.
정확히는, 각 부분 리스트의 크기가 1이 될 때까지 분할한 뒤, 두 부분 리스트의 앞에서부터 값을 비교하며 작은 값을 임시 배열에 저장한다.
분석
리스트를 절반씩 분할하므로, 순환 호출의 깊이는 $O(\log n)$이다. 또한 각 깊이에서는 전체 원소를 비교하고 결합하므로 $O(n)$의 작업이 필요하다.
따라서 최종적인 시간복잡도는 두 복잡도를 곱한 $O(n \log n)$이다. 때문에 값들이 많더라도 상당히 빠른 성능을 낸다.
합치는 과정에서 원소 수에 비례하는 임시 배열을 사용하므로 추가 공간이 필요하다(제자리 정렬이 아니다).
퀵 정렬(Quick Sort)
원리
퀵 정렬은 기준점이 될 임의의 값을 피벗(Pivot)으로써 선택하고, 피벗보다 작은 값은 왼쪽에, 큰 값은 오른쪽에 모이도록 데이터를 분할한다.
분할이 끝나면 피벗은 최종 위치에 놓인다. 이후 피벗의 왼쪽과 오른쪽 부분에 같은 과정을 순환적으로 적용한다.
분할(Partition) 알고리즘
상기 영상에서는 첫 번째 값을 피벗으로 사용한다. 이는 자유롭게 선택해도 되나, 최소값/최대값에 가깝지 않은 경우가 이상적이다.
low는 왼쪽에서부터 이동하며 피벗보다 큰 값을 찾는다. 찾았다면, 다음으로 high로써 오른쪽에서부터 피벗보다 작은 값을 찾는다. 두 값의 순서가 잘못되어 있다면 서로 교환하며, 이를 반복한다.
이 과정 중 low와 high가 교차한다면(즉 high보다 low가 오른쪽에 있다면) 피벗과 high 위치의 값을 교환하고, 현재 깊이에서의 정렬을 중단한다. 이 시점에서 high 위치의 값은 정렬된 상태이며, 이를 기준으로 왼쪽은 피벗보다 작은 값이, 오른쪽은 피벗보다 큰 값이 모이게 된다.
이후 이 (구) 피벗을 기준으로 좌/우를 나누고, 여기서도 정렬을 진행한다. 이를 반복하면 최종적으로 정렬이 이루어지게 된다.
분석
피벗이 데이터를 비슷한 크기로 나눈다면(즉 중앙값에 가깝다면) 리스트의 크기는 다음과 같이 감소한다.
\[n,\ \frac{n}{2},\ \frac{n}{4},\ \ldots,\ 1\]이 때의 분할 깊이는 약 $\log_2 n$이고, 각 깊이에서 전체적으로 $O(n)$의 비교가 발생한다. 따라서 평균 시간복잡도는 $O(n \log n)$이다.
그러나 매 번 최소값이나 최대값이 피벗으로 선택되면, 한쪽에는 원소가 없고 다른 쪽에는 나머지 원소가 몰리게 된다. 이 경우 정렬 최적화를 위한 분할 알고리즘이 사실상 무의미해지게 되며, 이에 따른 최악의 시간복잡도는 $O(n^2)$이다.
이 때문에 이를 피하기 위해 피벗을 적절히 잡아줄 필요가 있다. 이를 위해 현대에서는 임의의 값을 그냥 피벗으로 잡는 게 아닌, 가장 왼쪽/오른쪽/중앙 값들을 먼저 뽑아보고, 이들 중 중간 값을 피벗으로 설정하는 방식을 많이 사용한다.
퀵 정렬은 일반적으로 제자리 정렬에 가까운 방식으로 구현할 수 있지만 순환 호출을 위해 추가적인 스택 공간이 필요하며, 동일 키 값의 데이터들의 순서가 보장되지 않는 불안정적 정렬이다.
대부분의 상황에서 안정적인 성능을 내주기에, C++ STL에서 제공하는 기본 정렬 함수인 std::sort 에서도 내부적으로 사용하는 정렬 방법이기도 하다. 다만 정확히는 이쪽은 퀵 정렬을 기반으로 하되, 최악의 경우에는 힙 정렬 / 적은 데이터의 경우에는 삽입 정렬을 대신 사용하는 등 성능을 위한 여러 대비책을 혼합한 형태이다.
힙 정렬(Heap Sort)
원리
힙 정렬은 최대 힙을 이용하여 가장 큰 값을 반복적으로 꺼내 이를 통해 정렬하는 방식이다.
우선순위 큐 기반 힙 정렬 : 최대 힙에 데이터들을 순서 상관 없이 삽입한 뒤, 값을 하나씩 반출하면 최대값부터 반출되기에 이를 순서대로 컨테이너에 넣으면 정렬되게 된다. (반대로 최소 힙을 사용할 수도 있다.) 이 경우 추가적인 공간이 필요하다.
제자리 힙 정렬 : 먼저 전체 데이터를 최대 힙으로 만들어, 최댓값을 루트로 가져온다. 이후 루트의 값(최댓값)을 마지막 값과 교환한 뒤, (이미 정렬되었으므로) 정렬 대상에서 제외시킨다. 이후 정렬되지 않은 구간에 대해 이 과정을 반복한다.
참고 : 힙 정렬
분석
최대 힙을 생성하는 데에는 $O(n)$이 필요하다.
이후 최댓값을 제거하고 힙을 복구하는 작업은 $O(\log n)$이며, 이를 n번 반복한다. 따라서 전체 시간복잡도는 $O(n \log n)$이다.
힙 정렬 (구현에 따라서는) $O(1)$의 추가 공간만 사용하는 제자리 정렬이지만, 멀리 떨어진 값이 교환되므로 안정적인 정렬은 아니다.
기수 정렬(Radix Sort)
원리
기수 정렬은 특이하게도 값의 대소를 직접 비교하지 않고, 각 자릿수를 기준으로 정렬한다.
십진수 자연수라면 0부터 9까지 열 개의 버킷을 준비하고, 가장 낮은 자릿수부터 각 값을 버킷에 넣는다. 이후 버킷의 순서대로 값을 꺼내는 과정을 모든 자릿수에 대해 반복한다.
분석
정수의 개수를 n, 최대 자릿수를 d, 사용하는 진법의 크기를 b라고 하면 시간복잡도는 다음과 같다.
십진수처럼 b가 고정되어 있고 최대 자릿수 d가 작다면 $O(n)$에 가까운 말도 안되는 성능을 보인다.
다만 적용할 수 있는 경우가 극히 한정적이다. 정렬할 값들이 자릿수 단위로 분해할 수 있어야 하며, 그 최댓값의 자릿수 또한 너무 커서는 안된다. (즉, 자릿수가 제한된 정수들과 같은 꼴이 이상적이다.)
또한 임시 배열을 위한 추가 메모리가 필요하다. 값의 순서는 보장되기에 안정된 정렬이다.
정렬 비교
| 알고리즘 | 최선 | 평균 | 최악 | 추가 공간1 | 안정성 | 실측값 |
|---|---|---|---|---|---|---|
| 선택 정렬 | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 불안정 | 2.433s |
| 삽입 정렬 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 안정 | 1.213s |
| 버블 정렬 | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | 안정 | 17.499s |
| 셸 정렬2 | $O(n \log n)$ | $O(n^{1.5})$ | $O(n^2)$ | $O(1)$ | 불안정 | 0.012s |
| 합병 정렬 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | 안정 | 0.007s |
| 퀵 정렬 | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | 3$O(\log n)$ | 불안정 | 0.007s |
| 힙 정렬 | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | 불안정 | 0.010s |
| 기수 정렬 | $O(d(n+b))$ | $O(d(n+b))$ | $O(d(n+b))$ | $O(n+b)$ | 안정 | 0.001s |
실측값은 1 ~ 100만 값 범위의 랜덤한 10만개 정수 데이터를 정렬했을 때 기준이다.
댓글
불러오는 중...