인트로 정렬
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
인트로 정렬은 퀵 정렬의 성능 저하 문제를 해결하기 위해 데이비드 머서가 제안한 하이브리드 정렬 알고리즘이다. 퀵 정렬의 재귀 깊이가 특정 임계값을 초과하면 힙 정렬로 전환하여 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다. 퀵 정렬의 피벗 선택 전략, 특히 중간값-3 피벗 선택의 취약점을 보완하여 DoS 공격을 방지하는 데 기여하며, 다양한 프로그래밍 언어와 라이브러리에서 사용된다. 인트로 정렬의 변형으로는 pdqsort, fluxsort 등이 있다.
더 읽어볼만한 페이지
| 인트로 정렬 | |
|---|---|
| 일반 정보 | |
| 종류 | 정렬 알고리즘 |
| 자료 구조 | 배열 |
| 최악 시간 복잡도 | O(n log n) |
| 평균 시간 복잡도 | O(n log n) |
| 최적 시간 복잡도 | 예 |
| 개발자 | |
| 개발자 | 데비드 무서 |
| 최초 개발 | 1997년 |
| 설명 | |
| 개요 | 하이브리드 정렬 알고리즘 |
2. 역사적 배경
퀵 정렬은 피벗(데이터 열을 분할하는 경계값) 선택에 따라 성능이 크게 달라지는 단점이 있었다. 예를 들어 데이터 열의 선두나 꼬리를 피벗으로 선택하면, 거의 정렬된 입력에 대해 최악의 성능을 보인다. 니클라우스 비르트는 이를 피하기 위해 데이터 열의 중앙 요소를 피벗으로 선택하도록 했지만, 고안된 정렬에 대해서는 최악의 경우 O(n2)가 된다.
인트로 정렬은 기본적으로 퀵 정렬을 사용하지만, 재귀 깊이가 특정 임계값(보통 2 * log2(n))을 초과하면 힙 정렬로 전환하는 알고리즘이다. 퀵 정렬은 피벗을 기준으로 데이터를 두 부분으로 나누고, 각 부분을 재귀적으로 정렬한다. 힙 정렬은 힙 자료 구조를 사용하여 데이터를 정렬하며, 최악의 경우에도 O(n log n)의 시간 복잡도를 보장한다.[1]
퀵 정렬의 성능 저하를 어렵게 하는 방법으로는 선두, 꼬리, 중앙값의 중앙값을 피벗으로 선택하는 알고리즘(median-of-3 pivot|미디언 오브 3 피벗영어)이 있다. 이 방법으로 대부분의 데이터 열 정렬은 거의 잘 되지만, 데이터 열을 고안하여 성능을 대폭 저하시킬 수 있으며, DoS 공격에 이용될 수 있다는 약점이 있다. 즉, 사용자의 입력 데이터에 대해 정렬 처리를 수행하는 경우, 악의적인 입력으로 의도적으로 부하를 증가시키는 공격이 가능하다는 취약성을 안게 된다.
3. 알고리즘
퀵 정렬은 피벗(데이터 열을 분할하는 경계값) 선택에 따라 성능이 크게 달라진다.[1] 데이터 열의 처음이나 끝을 피벗으로 선택하면 거의 정렬된 입력에 대해 최악의 성능을 보일 수 있다. 니클라우스 비르트는 이를 피하기 위해 데이터 열의 중앙 요소를 피벗으로 선택하는 방법을 고안했지만, 특정 입력에 대해서는 최악의 경우가 될 수 있다.
퀵 정렬의 성능 저하를 막기 위해 데이터 열의 처음, 끝, 중앙값의 중앙값을 피벗으로 선택하는 알고리즘(median-of-3 pivot)이 있다. 이 방법은 대부분의 경우 잘 작동하지만, 의도적으로 성능을 저하시키는 데이터 열을 만들 수 있으며, DoS 공격에 이용될 수 있다는 약점이 있다.[17]
3. 1. 의사 코드
다음은 인트로 정렬의 의사 코드이다. `partition` 함수는 피벗을 선택하고, 피벗보다 작은 요소는 왼쪽, 큰 요소는 오른쪽에 위치하도록 배열을 재배치한다. `insertionsort`는 삽입 정렬, `heapsort`는 힙 정렬을 나타낸다.[1]
```
procedure sort(A : 배열):
let 최대깊이 = ⌊log₂(길이(A))⌋ × 2
introsort(A, 최대깊이)
procedure introsort(A, 최대깊이):
n ← 길이(A)
if n < 16:
삽입정렬(A)
else if 최대깊이 = 0:
힙정렬(A)
else:
p ← 분할(A) // 이 함수가 피벗 선택을 수행한다고 가정하고, p는 피벗의 최종 위치이다
인트로정렬(A[1:p-1], 최대깊이 - 1)
인트로정렬(A[p+1:n], 최대깊이 - 1)
```
최대 깊이의 계수 2는 임의의 값이며 실제 성능에 맞게 조정될 수 있다. A[i:j]영어는 i에서 j까지의 항목에 대한 배열 슬라이스를 나타내며, A[i]영어와 A[j]영어를 모두 포함한다. 인덱스는 1부터 시작하는 것으로 가정한다(배열 A영어의 첫 번째 요소는 A[1]영어이다).[1]
3. 2. 피벗 선택 전략
퀵 정렬의 성능은 피벗(리스트 분할 기준 요소) 선택에 크게 의존한다. 가장 단순한 방법(리스트의 첫 번째 또는 마지막 요소 선택)은 정렬되었거나 거의 정렬된 입력에서 성능이 좋지 않다. 니클라우스 비르트는 중간 요소를 피벗으로 사용하여 이를 방지했지만, 의도적으로 만들어진 시퀀스에서는 성능이 O(''n''2)으로 저하될 수 있다.
중간값-3(median-of-3) 피벗 선택 알고리즘은 리스트의 첫 번째, 중간, 마지막 요소의 중간값을 사용한다. 이 방법은 많은 실제 입력에서 좋은 성능을 보이지만, '중간값-3 킬러' 리스트를 만들어 퀵 정렬 속도를 현저히 늦출 수 있다. 이러한 '중간값-3 킬러'는 DoS 공격에 이용될 수 있다는 약점이 있다.[17] 무서(Musser)는 100,000개 요소의 중간값-3 킬러 시퀀스에서 인트로 정렬의 실행 시간이 중간값-3 퀵 정렬의 1/200 수준이라고 보고했다.[17]
4. 성능 및 구현
무서(Musser)는 중간값-3 퀵 정렬보다 인트로 정렬이 특정 입력에서 훨씬 빠르다고 보고했다. 그는 100,000개 요소의 중간값-3 킬러 시퀀스에서 인트로 정렬의 실행 시간이 중간값-3 퀵 정렬의 1/200 수준이었다고 밝혔다.[2] 무서는 로버트 세지윅(컴퓨터 과학자)가 제안한 작은 범위에 대한 정렬을 지연시키는 방식이 CPU 캐시에 미치는 영향도 고려했는데, 캐시 미스 횟수가 두 배로 늘어날 수 있지만, 양방향 큐를 사용하면 성능이 훨씬 더 좋다고 언급했다.
SGI C++ 표준 템플릿 라이브러리(STL)의 2000년 6월 구현[17]은 무서의 인트로 정렬 방식을 사용했다. 재귀 깊이가 매개변수로 전달되어 힙 정렬로 전환하고, 중앙값-3 피벗 선택과 16보다 작은 파티션에 대한 삽입 정렬을 사용했다. GNU 표준 C++ 라이브러리도 유사하게 최대 깊이 2×log2 ''n''의 인트로 정렬을 사용하고, 16보다 작은 파티션에 대해 삽입 정렬을 수행한다.[2]
LLVM libc++는 2×log2 ''n''의 최대 깊이로 인트로 정렬을 사용하며, 삽입 정렬의 크기 제한은 데이터 유형에 따라 다르다(교환이 사소한 경우 30, 그렇지 않은 경우 6). 크기가 5 이하인 배열은 별도로 처리된다.[3] Microsoft .NET Framework 클래스 라이브러리는 버전 4.5(2012)부터 퀵 정렬 대신 인트로 정렬을 사용한다.[5]
Go는 인트로 정렬의 변형을 사용한다. 12개 이하의 요소 슬라이스에는 삽입 정렬을 사용하고, 더 큰 슬라이스에는 패턴 방지 퀵 정렬과 중앙값 3개 중간값을 사용한 피벗 선택을 사용한다.[6] Java는 버전 14(2020)부터 고도로 구조화된 배열에는 병합 정렬을 사용하고, 그렇지 않은 경우 인트로 정렬을 사용하는 하이브리드 정렬 알고리즘을 사용한다.[7]
5. 변형
인트로 정렬에는 여러 가지 개선 및 변형이 있다. 대표적으로 pdqsort와 fluxsort가 있다. pdqsort는 러스트, GAP,[9] 부스트[10] 등에서 사용된다. fluxsort는 안정적인 정렬 방식이며, crumsort-rs, glidesort, ipnsort, driftsort 등에서 fluxsort의 개선 사항을 채택했다.[12][13][14][15][16]
5. 1. pdqsort
패턴 회피 퀵 정렬(pdqsort)은 인트로 정렬의 변형으로, 다음과 같은 개선 사항을 포함한다.[8]- 중간값-3 피벗
- 분기 예측 오류 페널티를 완화하기 위한 "블록퀵정렬" 분할 기법
- 특정 입력 패턴에 대한 선형 시간 성능 (적응형 정렬)
- 더 느린 힙 정렬을 시도하기 전에 불량한 경우에 요소 섞기 사용
- 낮은 기수 입력에 대한 적응성 향상
pdqsort는 러스트, GAP,[9] 부스트(C++ 라이브러리)에서 사용된다.[10]
5. 2. fluxsort
fluxsort는 인트로 정렬의 안정적인 변형으로, 다음과 같은 개선 사항을 포함한다.[11]- 분기 없는 sqrt(n) 피벗
- 안정적인 부분 제자리 분할을 위한 플럭스 분할 기술
- 분기 없는 양방향 패리티 병합을 활용하여 소형 정렬을 대폭 개선
- 정렬된 입력을 위한 적응성을 크게 향상시키는 분기 없는 양방향 병합 정렬인 quadsort로의 폴백
fluxsort 및 불안정한 변형인 crumsort에서 도입된 개선 사항은 crumsort-rs, glidesort, ipnsort 및 driftsort에서 채택되었다. 무작위 입력에 대한 전반적인 성능 향상은 pdqsort에 비해 약 50%이다.[12][13][14][15][16]
참조
[1]
웹사이트
Generic Algorithms
http://www.cs.rpi.ed[...]
[2]
웹사이트
libstdc++ Documentation: Sorting Algorithms
https://gcc.gnu.org/[...]
[3]
웹사이트
libc++ source code: sort
https://github.com/l[...]
[4]
웹사이트
Changing std::sort at Google’s Scale and Beyond
https://danlark.org/[...]
2022-04-20
[5]
웹사이트
Array.Sort Method (Array)
http://msdn.microsof[...]
[6]
웹사이트
Go 1.20.3 source code
https://github.com/g[...]
[7]
웹사이트
Java 14 source code
https://github.com/o[...]
[8]
웹사이트
orlp/pdqsort: Pattern-defeating quicksort.
https://github.com/o[...]
[9]
웹사이트
slice.sort_unstable(&mut self)
https://doc.rust-lan[...]
[10]
간행물
Efficient Verified Implementation of Introsort and Pdqsort
2020
[11]
웹사이트
fluxsort
https://github.com/s[...]
[12]
웹사이트
crumsort
https://github.com/s[...]
[13]
웹사이트
crumsort-rs
https://github.com/g[...]
[14]
웹사이트
Glidesort: Efficient In-Memory Adaptive Stable Sorting on Modern Hardware
https://archive.fosd[...]
[15]
웹사이트
ipnsort: an efficient, generic and robust unstable sort implementation.
https://github.com/V[...]
[16]
웹사이트
driftsort: an efficient, generic and robust stable sort implementation.
https://github.com/V[...]
[17]
웹사이트
stl_algo.h
http://www.sgi.com/t[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com