적응형 병합 정렬
적응형 병합 정렬은 정렬된 하위 목록 병합 정렬이 수행하는 병합을 수행합니다. 그러나 초기 하위 목록의 크기는 크기가 1인 하위 목록을 가지지 않고 요소 목록 사이에 순서가 있는지 여부에 따라 다릅니다. 예를 들어 그림의 목록을 고려하십시오.
2개의 정렬된 하위 목록으로 구성됩니다.
- 요소가 16,15,14,13인 하위 목록 1.
- 9,10,11,12 요소가 있는 하위 목록 2.
하위 목록 1은 정렬되지만 역순입니다. 따라서 하위 목록 1은 그림과 같이 반전됩니다.
하위 목록이 발견되면 병합 프로세스가 시작됩니다. 적응형 병합 정렬은 하위 목록 병합을 시작합니다. 적응형 병합 정렬은 하위 목록이 2개뿐이므로 병합 단계가 하나만 필요합니다. 병합 결과는 그림과 같습니다.
디자인 아이디어
- 이미 필수 또는 역순으로 정렬된 하위 목록을 찾는 것부터 시작하십시오.
- 요소를 역순으로 포함하는 하위 목록이 있는 경우 첫 번째 요소를 마지막 요소로, 두 번째 요소를 마지막 두 번째 요소와 교환하여 하위 목록을 반전시키면 계속됩니다.
- 하위 목록을 계속 병합하여 하위 목록이 1개만 남을 때까지 새로운 하위 목록을 생성합니다.
적응형 병합 정렬 분석
크기가 1인 하위 목록으로 시작하는 대신 적응형 병합 정렬은 이미 필수 또는 역순으로 정렬된 하위 목록을 찾습니다. 초기에 발견되는 하위 목록의 크기는 최소 2개에서 최대 m(m은 요소 수)입니다.
그러나 하위 목록에 요소가 역순으로 포함되어 있으면 병합 작업을 시작하기 전에 목록을 뒤집습니다. 목록을 뒤집으려면 (m/2) 교환 작업이 필요합니다.
최상의 사례
목록이 이미 정렬된 순서 또는 역순인 경우 적응형 병합 정렬에는 목록이 하나만 있고 병합 작업이 필요하지 않습니다. 그러나 목록이 이미 정렬되어 있음을 확인하려면 목록이 역순으로 정렬된 경우 O(m) 비교 연산과 (m/2) 교환 연산이 필요합니다. 이렇게 하면 목록이 역순으로 정렬된 경우에도 적응형 병합 정렬이 적응형이 됩니다.
따라서 최상의 경우에 대한 시간 복잡도는 다음과 같이 계산됩니다. -
T(m) = (m-1)+(m/2) T(m) = (2m-2+m)/2 T(m) = O(m).
그러나 적응형 병합 정렬은 병합 정렬에 비해 O(m)의 추가 공간을 구현합니다.
최악의 경우
적응형 병합 정렬은 필수 또는 역순으로 이미 정렬된 하위 목록을 찾습니다. 그러나 최악의 경우에는 부분 또는 전체 순서 요소가 없습니다. 따라서 처음에 찾은 하위 목록의 크기는 2가 됩니다. 하위 목록을 찾으면 병합 프로세스가 시작됩니다.
- 크기 2의 하위 목록을 병합하면 크기가 4인 정렬된 하위 목록이 생성됩니다.
- 크기 4의 하위 목록을 병합하면 크기가 8인 정렬된 하위 목록이 생성됩니다.
- 병합 프로세스는 2k
적응형 병합 정렬의 최악의 경우 병합 단계는 병합 정렬과 동일하기 때문입니다. 따라서 적응형 병합 정렬의 최악의 경우에 대한 시간 복잡도는 병합 정렬과 유사합니다 -
T(m) = O(m log m).