C에서 Merge Sort의 최악의 경우를 일으키는 순열 찾기

컨셉

주어진 요소 집합과 관련하여 이러한 요소의 어떤 순열이 병합 정렬의 최악의 경우를 초래하는지 결정하십시오.

우리는 점근적으로 병합 정렬이 항상 O(n log n) 시간을 소비한다는 것을 알고 있지만 더 많은 비교가 필요한 경우에는 일반적으로 실제로 더 많은 시간을 소비합니다. 이제 우리는 기본적으로 일반적인 병합 정렬 알고리즘을 구현하여 정렬할 때 가장 많은 비교를 유도하는 입력 요소의 순열을 결정해야 합니다.

예

아래 요소 집합을 Sorted 배열 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

병합 정렬의 최악의 경우가 되는 결과 입력 배열은 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26

방법

입력 세트에 대한 병합 정렬에 대한 최악의 경우 입력을 얻는 방법을 조사합니다.

이제 상향식으로 어레이를 구축하려고 합니다.

이제 정렬된 배열을 {11, 12, 13, 14, 15, 16, 17, 18}로 지정합니다.

이제 병합 정렬의 최악의 경우를 작성하려면 위의 정렬된 배열을 초래한 병합 작업이 가장 큰 비교 결과를 가져와야 합니다. 결과적으로 병합 작업에 관련된 왼쪽 및 오른쪽 하위 배열은 왼쪽 하위 배열이 {11, 13, 15, 17}이고 오른쪽 하위 배열이 {12, 14가 되도록 sortedarray의 대체 요소를 저장해야 합니다. , 16, 18}. 따라서 배열의 모든 요소는 최소 한 번만 비교되며 결과적으로 최대 비교가 됩니다. 이제 왼쪽 및 오른쪽 하위 배열에도 동일한 논리를 구현합니다. 배열 {11, 13, 15, 17}과 관련하여 최악의 경우는 왼쪽 및 오른쪽 하위 배열이 각각{11, 15} 및 {13, 17}이고 배열 {12, 14, 16, 18} 최악의 경우는 {12, 14} 및 {16, 18}에 대해 발생합니다.

완전한 알고리즘

최악의 경우 생성(arr[])

• 이제 왼쪽과 오른쪽에 두 개의 보조 배열을 만들고 여기에 대체 배열 요소를 저장합니다.

• 왼쪽 하위 배열에 대해 GenerateWorstCase를 호출합니다. - GenerateWorstCase(왼쪽)

• 오른쪽 하위 배열에 대해 GenerateWorstCase를 호출합니다. GenerateWorstCase(오른쪽)

• 이제 왼쪽 및 오른쪽 하위 배열의 모든 요소를 ​​원래 배열로 다시 복사합니다.

예시

// Worst Case of Merge를 생성하는 C 프로그램 Sort#include #include // array를 출력하는 함수를 나타냅니다. printArray(int A1[], int size1){ for (int i =0; i  
출력
 
정렬된 배열은 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26최악의 병합 정렬이 되는 입력 배열은 11 19 15 23 13 21 17 25 1462입니다.>