적응 정렬

정렬 알고리즘은 입력에서 기존 순서를 활용할 경우 적응형 정렬 패밀리에 속한다.입력 순서의 사전 편중성(또는 무질서의 다양한 정의에 대한 제한된 무질서의 양)으로부터 이익을 얻고 더 빨리 분류한다.적응 정렬은 일반적으로 기존 정렬 알고리즘을 수정하여 수행된다.

동기

비교 기반 정렬 알고리즘은 전통적으로 시간 복잡성을 처리할 때 O(n log n)의 최적 경계 달성을 다루었다.적응 정렬은 입력의 기존 순서를 이용하여 더 나은 시간을 달성하려고 시도하므로, 정렬 알고리즘이 정렬하는 데 걸리는 시간은 순서의 크기와 시퀀스 내의 무질서의 크기를 원활하게 증가시키는 기능이다.즉, 입력을 미리 정렬할수록 빨리 정렬해야 한다.

거의 정렬된 시퀀스가 실제로 일반적이기 때문에 이것은 매력적인 알고리즘이다.따라서 입력의 기존 순서를 고려하여 기존 정렬 알고리즘의 성능을 향상시킬 수 있다.

가장 최악의 경우, 특히 힙 정렬 및 병합 정렬에서 최적으로 잘 수행되는 대부분의 최악의 경우 정렬 알고리즘은, 비록 이 결핍은 병합 정렬의 경우, 첫 번째 요소보다 작거나 같은지 확인함으로써 쉽게 수정되지만, 입력 내 기존 순서를 고려하지 않는다.8번째 그룹의 경우, 이 경우 병합 연산은 단순한 연결로 대체될 수 있다. 즉 알고리즘을 적응시키는 범위 내에 잘 들어 있는 수정이다.

예

적응형 정렬 알고리즘의 대표적인 예는 직선 삽입 정렬이다.이 정렬 알고리즘에서는 입력을 왼쪽에서 오른쪽으로 스캔하여 현재 항목의 위치를 반복적으로 찾아내고, 이전에 정렬된 항목의 배열로 삽입한다.

유사 코드 형식에서 직선 삽입 정렬 알고리즘은 이와 유사할 수 있다(어레이 X는 0 기반).

프로시저 직선 삽입 정렬(X): j := 1 길이(X) - 1 do t :=X[j] i := j do := X[j] i := j do i > 0 및 X[i - 1] > do X[i] := X[i - 1] i := i - 1 end X := t end X := t end

The performance of this algorithm can be described in terms of the number of inversions in the input, and then ${\displaystyle T(n)}$ will be roughly equal to ${\displaystyle I(A)+(n-1)}$, where ${\displaystyle I(A)}$ is the number of Inversions.이러한 사전 정렬 방법(반복 횟수에 상대적임)을 사용하면 정렬에 가까울수록 정렬하는 데 시간이 덜 걸린다.

적응형 정렬 알고리즘의 다른 예로는 적응형 힙 정렬, 적응형 병합 정렬, 인내 정렬,^[1] 쉘포트, 스무드 정렬, splaysort, Timsort 및 데카르트 트리 정렬이 있다.^[2]

참고 항목

• 정렬 알고리즘
• 스무스소트

참조

• Hagerup, Torben; Jyrki Katjainen (2004). Algorithm Theory – SWAT 2004. Berlin Heidelberg: Springer-Verlag. pp. 221–222. ISBN 3-540-22339-8.
• Mehta, Dinesh P.; Sartaj Sahni (2005). Data Structures and Applications. USA: Chapman & Hall/CRC. pp. 11‑8–11‑9. ISBN 1-58488-435-5.
• Estivill-Castro, Vladmir; Wood, Derick (December 1992). "A survey of adaptive sorting algorithms". ACM. New York, NY, USA. 24 (4): 441–476. CiteSeerX 10.1.1.45.8017. doi:10.1145/146370.146381. ISSN 0360-0300. S2CID 1540978.
• Petersson, Ola; Alistair Moffat (1992). "A framework for adaptive sorting". Lecture Notes in Computer Science. 621. Berlin: Springer Berlin / Heidelberg: 422–433. doi:10.1007/3-540-55706-7_38. ISBN 978-3-540-55706-7. ISSN 1611-3349. {{cite journal}}:Cite 저널은 필요로 한다. journal=(도움말)