주어진 요소 집합에 대해 어떤 배열이 병합 정렬의 최악의 경우로 이어질지 결정합니까?
점근적으로 병합 정렬은 항상 O(n log n) 시간이 걸리지만 실제로는 더 많은 비교가 필요한 경우에는 일반적으로 더 많은 시간이 걸립니다. 이제 기본적으로 일반적인 병합 정렬 알고리즘을 구현할 때 비교 횟수를 최대화하는 입력 요소 배열을 결정해야 합니다.
예
다음 요소 집합을 정렬된 배열로 간주합니다. 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, 16이어야 합니다. , 18 }. 이렇게 하면 배열의 각 요소가 최소한 한 번 비교되어 최대 비교 횟수가 발생합니다. 이제 왼쪽 하위 배열과 오른쪽 하위 배열에도 동일한 논리를 구현합니다. 배열 {11, 13, 15, 17}의 경우 왼쪽 하위 배열이 {11, 15}이고 오른쪽 하위 배열이 {12, 14, 16, 18}인 경우 최악의 경우가 발생합니다. , 최악의 경우는 {12, 14} 및 {16, 18}에서 발생합니다.
GenerateWorstCase(arr[])
이제 왼쪽과 오른쪽에 두 개의 보조 배열을 만들고 그 안에 교대로 배열 요소를 저장합니다.
GenerateWorstCase - 왼쪽 하위 배열을 호출합니다.
오른쪽 하위 배열에서 generateWorstCase - 생성WorstCase(오른쪽)를 호출합니다.
이제 왼쪽 하위 배열과 오른쪽 하위 배열의 모든 요소를 복사합니다. 원래 배열을 반환합니다.
데모
// C program to generate Worst Case of Merge Sort #include <stdlib.h> #include <stdio.h> // Indicates function to print an array void printArray(int A1[], int size1){ for (int i = 0; i < size1; i++) printf("%d ", A1[i]); printf("</p><p>"); } // Indicates function to join left and right subarray int join(int arr1[], int left1[], int right1[], int l1, int m1, int r1){ int i; // So used in second loop for (i = 0; i <= m1 - l1; i++) arr1[i] = left1[i]; for (int j = 0; j < r1 - m1; j++) arr1[i + j] = right1[j]; } // Indicates function to store alternate elemets in left // and right subarray int split(int arr1[], int left1[], int right1[], int l1, int m1, int r1){ for (int i = 0; i <= m1 - l1; i++) left1[i] = arr1[i * 2]; for (int i = 0; i < r1 - m1; i++) right1[i] = arr1[i * 2 + 1]; } // Indicates function to generate Worst Case of Merge Sort int generateWorstCase(int arr1[], int l1, int r1){ if (l1 < r1){ int m1 = l1 + (r1 - l1) / 2; // creating two auxillary arrays int left1[m1 - l1 + 1]; int right1[r1 - m1]; // Storing alternate array elements in left // and right subarray split(arr1, left1, right1, l1, m1, r1); // Recursing first and second halves generateWorstCase(left1, l1, m1); generateWorstCase(right1, m1 + 1, r1); // joining left and right subarray join(arr1, left1, right1, l1, m1, r1); } } // Driver code int main(){ // Initializes sorted array int arr1[] = { 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26 }; int n1 = sizeof(arr1) / sizeof(arr1[0]); printf("Sorted array is </p><p>"); printArray(arr1, n1); // generating worst Case of Merge Sort generateWorstCase(arr1, 0, n1 - 1); printf("</p><p>Input array that will result in " "worst case of merge sort is </p><p>"); printArray(arr1, n1); return 0; }
Sorted array is 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 Input array that will result in worst case of merge sort is 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
위 내용은 C에서 병합 정렬의 최악의 시나리오로 이어지는 순열을 찾으십시오.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!