적응형 정렬

적응형 정렬 또는 어댑티브 소트(adaptive sort)는 정렬 알고리즘의 일종으로, 입력의 기존 순서를 활용하는 경우이다. 입력 순서의 사전 정렬 또는 다양한 장애 측정 정의에 대한 제한된 양의 장애로부터 이점을 얻고 더 빠르게 정렬된다. 적응형 정렬은 일반적으로 기존 정렬 알고리즘을 수정하여 수행된다.

동기

비교 기반 정렬 알고리즘은 전통적으로 시간 복잡도를 처리할 때 O(n log n)의 최적 경계를 달성하는 것을 처리해 왔다. 적응형 정렬은 더 나은 시간을 얻기 위해 입력의 기존 순서를 활용하므로 알고리즘이 정렬하는 데 걸리는 시간은 시퀀스의 크기와 시퀀스의 무질서에 따라 원활하게 증가하는 함수이다. 즉, 입력이 미리 정렬되어 있을수록 더 빨리 정렬되어야 한다.

실제로는 대부분 정렬된 시퀀스가 일반적이기 때문에 이는 정렬 알고리즘의 매력적인 기능으로 비쳐진다. 따라서 입력의 기존 순서를 고려하면 기존 정렬 알고리즘의 성능이 향상될 수 있다.

최악의 경우에 가장 잘 작동하는 대부분의 최악의 경우 정렬 알고리즘, 특히 힙 정렬 및 병합 정렬은 입력 내의 기존 순서를 고려하지 않는다. 그러나 이러한 결함은 병합 정렬의 경우 검사를 통해 쉽게 수정된다. 왼쪽 그룹의 마지막 요소가 오른쪽 그룹의 첫 번째 요소보다 작거나 같은 경우 병합 작업은 간단한 연결로 대체될 수 있다. 이는 알고리즘을 적응형으로 만드는 범위 내에 있는 수정이다.

같이 보기

• 정렬 알고리즘