적응형 정렬

1. 개요

적응형 정렬은 입력 데이터의 기존 순서를 활용하여 정렬 속도를 향상시키는 정렬 알고리즘을 의미한다. 입력 데이터가 미리 정렬되어 있을수록 더 빠르게 정렬된다는 특징을 가진다. 실제 데이터가 부분적으로 정렬된 경우가 많기 때문에 기존 정렬 알고리즘의 성능을 향상시킬 수 있다. 삽입 정렬, 적응형 힙 정렬, 적응형 병합 정렬 등이 적응형 정렬 알고리즘의 예시이다. 삽입 정렬은 대표적인 적응형 정렬 알고리즘으로, 입력 데이터의 전위 수에 따라 성능이 달라진다.

2. 동기

비교 기반 정렬 알고리즘은 전통적으로 시간 복잡도와 관련하여 최적의 O(n log n) 경계를 달성하는 데 주력해 왔다. 적응형 정렬은 입력의 기존 순서를 활용하여 더 나은 시간을 달성하려 시도한다. 따라서 정렬에 걸리는 시간은 시퀀스 크기 및 시퀀스의 무질서에 대한 부드럽게 증가하는 함수이다. 즉, 입력이 사전 정렬된 정도가 클수록 더 빨리 정렬되어야 한다.

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

대부분의 최악의 경우 정렬 알고리즘은 최악의 경우에 최적으로 잘 수행하며, 특히 힙 정렬 및 병합 정렬은 입력 내의 기존 순서를 고려하지 않는다. 그러나 병합 정렬의 경우 왼손 그룹의 마지막 요소가 오른손 그룹의 첫 번째 요소보다 작은지(또는 같은지) 확인하여 이러한 결함을 쉽게 수정할 수 있다. 이 경우 병합 작업을 단순한 연결로 대체할 수 있다. 이는 알고리즘을 적응형으로 만드는 범위 내에 있는 수정 사항이다.

3. 예시

삽입 정렬은 적응형 정렬 알고리즘의 한 예시이다. 삽입 정렬은 데이터가 정렬에 가까울수록 정렬 시간이 줄어드는 특징을 가지며, 수행 시간은 입력 데이터의 전위 수에 따라 달라진다.

다른 적응형 정렬 알고리즘으로는 적응형 힙 정렬, 적응형 합병 정렬, 인내 정렬, 셸 정렬, 스무스 정렬, 스플레이 정렬, 팀소트, 데카르트 트리 정렬 등이 있다.

3.1. 삽입 정렬

삽입 정렬은 적응형 정렬 알고리즘의 대표적인 예이다. 이 알고리즘은 입력을 왼쪽에서 오른쪽으로 훑어가면서 현재 항목의 위치를 반복적으로 찾아 이전에 정렬된 항목들의 배열에 삽입하는 방식으로 작동한다.

삽입 정렬 알고리즘의 의사 코드는 다음과 같다(배열 X는 0부터 시작한다):

for j = 1 to 길이(X) - 1 do
:t ← X[j]
:i ← j
:while i > 0 and X[i - 1] > t do
::X[i] ← X[i - 1]
::i ← i - 1
:end
:X[i] ← t
end

삽입 정렬은 데이터 배열이 정렬에 가까울수록 정렬하는 데 시간이 덜 걸린다. 이 알고리즘의 성능은 입력의 전위 수로 설명할 수 있으며, T(n)은 I(A) + (n - 1)과 거의 같다. 여기서 I(A)는 전위의 수이다.