C에서 병합 정렬의 최악의 시나리오로 이어지는 순열을 찾으십시오.

Concept

주어진 요소 집합에 대해 어떤 배열이 병합 정렬의 최악의 경우로 이어질지 결정합니까?

점근적으로 병합 정렬은 항상 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

Method

병합 정렬을 위한 최악의 입력 집합을 구축하는 방법을 연구합니다.

이제 우리는 상향식 방식으로 배열을 구축하려고 합니다.

이제 정렬된 배열을 {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}에서 발생합니다.

Full Algorithm

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!