[알고리즘] 정렬(Sort) 알고리즘
[알고리즘] 정렬(Sort) 알고리즘
정렬 알고리즘에는 여러 종류가 있으며, 각기 다른 성능 특성과 활용 분야를 가진다. 주요 정렬 알고리즘들은 다음과 같다:
1. 비교 정렬 (Comparison Sorts)
비교 정렬은 입력 요소들 간의 비교를 통해서만 정렬 순서를 결정하는 알고리즘이다. 어떤 비교 정렬 알고리즘도 최악의 경우 Ω(n lg n) 시간보다 빠르게 n개의 요소를 정렬할 수 없음이 증명되었다.
- 삽입 정렬 (Insertion Sort)
- 설명: 증분 방식(incremental approach)을 사용하는 알고리즘이다. 즉, 처음 문제를 작은 크기에서 시작해서 해결하고 점점 쌓아 올리고 확장하며 전체 문제를 해결하는 방식이다. 카드를 정렬하는 방식과 유사하게, 배열의 한 부분을 이미 정렬된 상태로 유지하고, 나머지 요소를 하나씩 가져와 정렬된 부분에 올바른 위치에 삽입한다.
- 성능:
- 최악의 경우: Θ(n²) 시간이 소요된다. (예: 역순으로 정렬된 배열)
- 최선의 경우: Θ(n) 시간이 소요된다. (예: 이미 정렬된 배열)
- 특징: 작은 입력 크기(n)에 대해서는 병합 정렬(Merge Sort)보다 상수 인자가 작아 더 빠르게 작동할 수 있다. 또한, 제자리 정렬(in-place sort) 방식으로 작동하여 입력 배열 외에 추가적인 상수 메모리만 사용한다. 소스에 따르면 안정 정렬(stable sort)로 분류될 수 있다.
- 병합 정렬 (Merge Sort)
- 설명: 재귀적인 분할 정복(divide-and-conquer) 기법을 사용한다. 배열을 두 개의 하위 배열로 나눈 다음 각 하위 배열을 재귀적으로 정렬하고, 정렬된 두 하위 배열을 병합하여 최종 정렬된 배열을 만든다.
- 성능:
- 최악의 경우: Θ(n lg n) 시간이 소요된다.
- 특징: 삽입 정렬보다 점근적으로 더 빠르며, 비교 정렬 중 점근적으로 최적(asymptotically optimal) 이다. 하지만 MERGE 프로시저가 제자리 정렬 방식이 아니다. 안정 정렬(stable sort)입니다.
- 힙 정렬 (Heapsort)
- 설명: 힙(heap)이라는 자료 구조를 사용하여 n개의 숫자를 정렬한다. 먼저 입력 배열을 최대 힙(max-heap)으로 구성한 다음, 최대 힙 속성을 유지하면서 가장 큰 요소를 배열의 끝으로 이동시키는 과정을 반복한다.
- 성능:
- 최악의 경우: O(n lg n) 시간이 소요된다.
- 특징: 병합 정렬과 유사하게 O(n lg n)의 실행 시간을 가지지만, 삽입 정렬처럼 제자리 정렬 방식이다. 이 때문에 두 알고리즘의 장점을 결합한 것으로 평가된다. 비교 정렬 중 점근적으로 최적이다.
- 퀵 정렬 (Quicksort)
- 설명: 병합 정렬과 마찬가지로 분할 정복 방법을 사용한다. 배열을 피벗(pivot) 요소 주변으로 분할하여, 피벗보다 작거나 같은 요소들은 한쪽에, 피벗보다 크거나 같은 요소들은 다른 쪽에 놓이도록 재배열한다. 그 후 두 하위 배열을 재귀적으로 정렬한다.
- 성능:
- 최악의 경우: Θ(n²) 시간이 소요된다. (예: 이미 정렬되거나 역순으로 정렬된 배열)
- 기대 실행 시간 (Expected running time): Θ(n lg n) 입니다 (모든 요소가 고유할 경우).
- 특징: 최악의 경우 성능은 느리지만, 평균적으로 매우 효율적이어서 실용적인 정렬 방법으로 자주 선택된다. 힙 정렬보다 실제로는 더 좋은 성능을 보이는 경우가 많다. 또한 제자리 정렬 방식이다. 난수화된 버전인 RANDOMIZED-QUICKSORT는 특정 입력이 최악의 경우로 이어지지 않도록 한다. 안정 정렬이 아니다.
- 선택 정렬 (Selection Sort)
- 설명: 배열에서 가장 작은 요소를 찾아 첫 번째 요소와 교환하고, 다음으로 작은 요소를 찾아 두 번째 요소와 교환하는 과정을 n-1번 반복하는 알고리즘이다.
- 성능: 최악의 경우 Θ(n²) 시간이 소요되며, 최선의 경우에도 이보다 좋지 않다.
- 버블 정렬 (Bubblesort)
- 설명: 인접한 두 요소의 순서가 잘못되면 교환하는 작업을 반복하여 정렬하는 비효율적인 알고리즘이다.
- 성능: 최악의 경우 삽입 정렬과 유사하게 Θ(n²) 시간이 소요됩니다.
- 스투지 정렬 (Stooge Sort)
- 설명: 재귀적인 알고리즘으로, 배열 A[p…r]을 정렬하기 위해, A[p]와 A[r]을 비교하고, p+1 < r인 경우 배열을 3등분하여 앞쪽 2/3, 뒤쪽 2/3, 그리고 다시 앞쪽 2/3을 재귀적으로 정렬한다.
- 성능: 최악의 경우 Θ(n^(log₁․₅ 3)) 시간이 소요된다. 이는 대략 Θ(n^2.71)에 해당하여 다른 효율적인 정렬 알고리즘보다 느리다.
2. 선형 시간 정렬 (Linear-Time Sorts)
이 알고리즘들은 입력 요소들 간의 비교 이외의 연산을 사용하여 정렬 순서를 결정하기 때문에 비교 정렬의 Ω(n lg n) 하한에 영향을 받지 않고 특정 조건에서 선형 시간인 O(n)에 실행될 수 있다.
- 계수 정렬 (Counting Sort)
- 설명: n개의 입력 요소가 0부터 k까지의 정수 범위 내에 있을 때 사용된다. 각 입력 요소 x에 대해 x보다 작거나 같은 요소의 개수를 파악한 다음, 이 정보를 사용하여 x를 출력 배열의 올바른 위치에 직접 배치한다. 중복 값을 처리하기 위해 약간 수정된다.
- 성능: Θ(n + k) 시간이 소요된다. k가 O(n)일 경우, 실행 시간은 Θ(n)이 된다.
- 특징: 비교 정렬이 아니며, 요소의 실제 값을 배열의 인덱스로 사용한다. 안정 정렬이라는 중요한 속성을 가지며, 이는 기수 정렬의 서브루틴으로 사용될 때 필수적이다.
- 기수 정렬 (Radix Sort)
- 설명: 카드 정렬 기계에서 사용되던 알고리즘으로, d개의 자릿수를 가진 숫자를 가장 낮은 자릿수부터 (또는 가장 높은 자릿수부터) 안정 정렬 알고리즘을 사용하여 d번 정렬하는 방식이다.
- 성능: 각 자릿수가 k개의 값을 가질 수 있는 d자리 숫자의 경우 Θ(d(n + k)) 시간이 소요된다. b비트 숫자의 경우 Θ((b/r)(n + 2^r)) 시간이 소요될 수 있으며, 적절한 r 선택 시 Θ(n) 시간을 달성할 수 있다.
- 특징: 비교 정렬이 아니다. 올바르게 작동하려면 안정 정렬을 서브루틴으로 사용해야 한다. 계수 정렬과 달리 제자리 정렬이 아니다.
- 버킷 정렬 (Bucket Sort)
- 설명: 입력이 [0, 1) 구간에 균일하게 분포된 실수라고 가정합니다. 이 구간을 n개의 같은 크기의 하위 구간(버킷)으로 나누고, 입력 숫자를 해당 버킷에 배분한 다음, 각 버킷 내의 숫자를 정렬하고 마지막으로 버킷을 순서대로 연결하여 최종 정렬된 출력을 생성한다.
- 성능:
- 평균의 경우: O(n) 시간이 소요된다.
- 최악의 경우: Θ(n²) 시간이 소요된다. (모든 요소가 하나의 버킷에 들어갈 경우)
- 특징: 비교 정렬이 아니며, 입력 분포에 대한 가정을 사용한다.
3. 기타 정렬 관련 개념
- 쉘 정렬 (Shell’s Sort)
- 삽입 정렬의 변형으로, 입력 배열의 주기적인 하위 배열에 삽입 정렬을 적용하여 더 빠른 정렬 알고리즘을 만든다.
- 컬럼 정렬 (Columnsort)
- n개의 요소를 가진 직사각형 배열에 대해 작동하는 알고리즘으로, r행 s열로 구성됩니다. 특정 제약 조건(r은 짝수, s는 r의 약수, r ≥ 2s²) 하에 8단계의 고정된 연산을 통해 배열을 열 우선 순서로 정렬한다. 비교-교환(compare-exchange) 연산에만 의존하는 비맹목적(oblivious) 알고리즘으로 볼 수 있다.
각 알고리즘은 특정 상황과 입력 데이터의 특성에 따라 장단점을 가진다. 예를 들어, 삽입 정렬은 작은 입력에 빠르고 제자리 정렬이지만, 퀵 정렬은 큰 배열에 평균적으로 빠르고 제자리 정렬이다. 병합 정렬과 힙 정렬은 O(n lg n)의 최적 성능을 보장한다. 계수 정렬, 기수 정렬, 버킷 정렬은 비교 정렬의 하한을 깨고 선형 시간에 정렬할 수 있지만, 입력 데이터의 제약(범위, 분포 등)이 필요하다.
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.