Khái niệm
Đối với một tập hợp các phần tử nhất định, hãy xác định hoán vị nào của các phần tử này sẽ dẫn đến trường hợp xấu nhất là Hợp nhất Sắp xếp?
Chúng ta biết, về mặt tiệm cận, sắp xếp hợp nhất luôn tiêu tốn O (n log n) thời gian, nhưng các trường hợp cần nhiều so sánh hơn thường tiêu tốn nhiều thời gian hơn trong thực tế. Bây giờ về cơ bản, chúng tôi yêu cầu xác định một hoán vị của các phần tử đầu vào sẽ dẫn đến số lượng so sánh lớn nhất khi được sắp xếp thực hiện thuật toán Sắp xếp Hợp nhất điển hình.
Ví dụ
Coi tập hợp các phần tử dưới đây là mảng đã sắp xếp 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
Mảng đầu vào kết quả sẽ dẫn đến trường hợp xấu nhất là sắp xếp hợp nhất là 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
Phương pháp
Chúng tôi kiểm tra cách lấy đầu vào trường hợp xấu nhất để sắp xếp hợp nhất cho một tập hợp đầu vào?
Bây giờ chúng tôi cố gắng xây dựng mảng theo cách từ dưới lên
Bây giờ, hãy đặt mảng đã sắp xếp là {11, 12, 13, 14, 15, 16, 17, 18}.
Bây giờ để xây dựng trường hợp xấu nhất của sắp xếp hợp nhất, hoạt động hợp nhất dẫn đến mảng được sắp xếp ở trên sẽ dẫn đến so sánh lớn nhất. Do đó, mảng con bên trái và bên phải tham gia vào hoạt động hợp nhất phải lưu trữ các phần tử thay thế của mảng đã sắp xếp sao cho mảng con bên trái phải là {11, 13, 15, 17} và mảng con bên phải là {12, 14 , 16, 18}. Vì vậy, mọi phần tử của mảng sẽ được so sánh tối thiểu một lần và điều đó sẽ dẫn đến so sánh tối đa. Bây giờ chúng ta thực hiện cùng một logic cho mảng con bên trái và bên phải. Đối với mảng {11, 13, 15, 17}, trường hợp xấu nhất sẽ là khi mảng con bên trái và bên phải của nó lần lượt là {11, 15} và {13, 17} và đối với mảng {12, 14, 16, 18} trường hợp xấu nhất sẽ xảy ra cho {12, 14} và {16, 18}.
Hoàn thành thuật toán
GenerateWorstCase (arr [])
-
Bây giờ chúng ta tạo hai mảng phụ trợ bên trái và bên phải và lưu trữ các phần tử mảng thay thế trong chúng.
-
Chúng tôi gọi GenerateWorstCase cho mảng con bên trái - GenerateWorstCase (trái)
-
Chúng tôi gọi GenerateWorstCase cho mảng con bên phải GenerateWorstCase (phải)
-
Bây giờ chúng ta sao chép tất cả các phần tử của mảng con bên trái và bên phải trở lại mảng ban đầu.
Ví dụ
// 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;
} Đầu ra
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