Cでのマージソートの最悪のケースを引き起こす順列を見つけます

コンセプト

与えられた要素のセットに関して、これらの要素のどの順列がマージソートの最悪の場合になるかを決定しますか？

漸近的に、マージソートは常にO（n log n）時間を消費しますが、より多くの比較が必要な場合は、通常、実際にはより多くの時間を消費します。ここで、基本的に、典型的なマージソートアルゴリズムを実装してソートしたときに最大数の比較につながる入力要素の順列を決定する必要があります。

例

以下の要素のセットを並べ替えられた配列と見なします111213 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}。したがって、配列のすべての要素が最小で1回比較され、最大の比較になります。ここで、左右のサブ配列にも同じロジックを実装します。配列{11、13、15、17}に関しては、最悪のケースは、その左と右のサブ配列がそれぞれ{11、15}と{13、17}であり、配列{12、14、16の場合です。 18}最悪のケースは{12、14}と{16、18}で発生します。

完全なアルゴリズム

GenerateWorstCase（arr []）

• 次に、左右に2つの補助配列を作成し、それらに代替配列要素を格納します。

• 左側のサブアレイに対してGenerateWorstCaseと呼びます-GenerateWorstCase（左側）

• 右のサブ配列GenerateWorstCase（右）に対してGenerateWorstCaseと呼びます

• 次に、左右のサブ配列のすべての要素を元の配列にコピーします。

例

// 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("\n");
}
// 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 \n");
   printArray(arr1, n1);
   // generating worst Case of Merge Sort
   generateWorstCase(arr1, 0, n1 - 1);
   printf("\nInput array that will result in " "worst case of merge sort is \n");
   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