資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝學
法學查詢導致 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("
");
}
// 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
");
printArray(arr1, n1);
// generating worst Case of Merge Sort
generateWorstCase(arr1, 0, n1 - 1);
printf("
Input array that will result in " "worst case of merge sort is
");
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
249 次瀏覽
