在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, 18 }。這樣，數組的每個元素將至少被比較一次，從而導致最大比較次數。現在我們對左子數組和右子數組也實作相同的邏輯。對於數組{11, 13, 15, 17}，最壞情況發生在其左子數組為{11, 15}，右子數組為{13, 17}，對於數組{12, 14, 16, 18}，最壞情況發生在{12, 14} 和{16, 18}。

完整演算法

GenerateWorstCase(arr[])

• 現在我們建立兩個輔助數組left 和right，並將交替的數組元素儲存在它們中。

• 我們對左子數組呼叫GenerateWorstCase - GenerateWorstCase (left)

• ##我們對右子數組呼叫GenerateWorstCase - GenerateWorstCase (right)

• 現在我們將左子數組和右子數組的所有元素複製回原始數組。

範例

 示範

// 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中文網其他相關文章！