C でのマージ ソートの最悪のシナリオにつながる順列を見つけます。

コンセプト

特定の要素セットについて、どの配置がマージ ソートの最悪のシナリオをもたらすかを判断します。

マージ ソートには漸近的に常に 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 である必要があります。 、１８｝。こうすることで、配列の各要素が少なくとも 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("</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 中国語 Web サイトの他の関連記事を参照してください。