Stable Sort와 다양한 정렬 알고리즘

Stable Sort

정의

Stable Sort는 동일한 키 값을 가진 요소의 상대적인 순서가 정렬 후에도 유지되는 정렬 알고리즘이다.

예시

• Merge Sort
• Insertion Sort
• Bubble Sort

Merge Sort 비재귀 구현

Merge Sort는 재귀를 사용하지 않고 반복문을 이용한 바텀업(bottom-up) 방식으로 구현할 수 있다. 이 방식에서는 배열을 1개, 2개, 4개, ... 의 단위로 나눈 다음 순차적으로 병합해 나간다.

Radix Sort

Radix Sort는 비교 기반 정렬 알고리즘이 아니라, 정수나 문자열 같은 키를 기준으로 요소를 정렬하는 알고리즘이다. 시간 복잡도는 (O(nk))로, (n)은 요소의 개수, (k)는 키의 최대 길이이다. LSD (Least Significant Digit) 또는 MSD (Most Significant Digit) 방식으로 구현할 수 있다. 큰 데이터를 효율적으로 처리할 수 있으며, 추가 메모리를 사용한다.

Bubble, Selection, Insertion Sort 속도 비교

Bubble Sort와 Selection Sort의 시간 복잡도는 모든 경우에 (O(n^2))이다. Insertion Sort는 최선의 경우 (O(n)), 평균 및 최악의 경우 (O(n^2))의 시간 복잡도를 가진다. 데이터가 거의 정렬되어 있을 경우, Insertion Sort가 상대적으로 매우 빠르게 동작한다.

거의 정렬된 데이터의 성능

거의 정렬된 데이터에서는 Insertion Sort가 Bubble Sort와 Selection Sort보다 훨씬 빠르게 동작한다. 이는 Insertion Sort가 이미 정렬된 데이터에 대해 최소한의 작업만 수행하기 때문이다.

사용 언어별 정렬 함수

대부분의 프로그래밍 언어는 표준 라이브러리에서 (O(n \log n))의 시간 복잡도를 가진 효율적인 정렬 함수를 제공한다.

• Java: Arrays.sort() (프리미티브 타입은 Dual-Pivot Quick Sort, 객체는 Tim Sort)
• Python: list.sort() 또는 sorted() (Tim Sort)
• C++: std::sort() (퀵소트 변형, 경우에 따라 힙 정렬이나 삽입 정렬과 결합)

50G 데이터, 4G 메모리 정렬

외부 정렬 (External Sort)을 사용한다. 메모리 크기에 제한이 있는 경우, 데이터를 여러 개의 작은 블록으로 나누고, 각 블록을 메모리에 로드하여 정렬한 후 외부 저장소에 저장한다. 이후 병합 정렬과 유사한 방식으로 정렬된 블록들을 순차적으로 병합한다. K-way 병합 정렬을 사용하여 여러 개의 정렬된 블록을 동시에 병합하며, 병합 과정에서 사용할 수 있는 메모리의 크기에 맞춰 효율적으로 데이터를 처리한다.