แนวคิด
ในส่วนที่เกี่ยวกับชุดขององค์ประกอบที่กำหนด ให้พิจารณาว่าการเรียงสับเปลี่ยนขององค์ประกอบใดจะส่งผลให้เกิดกรณีที่เลวร้ายที่สุดของ Merge Sort
เราทราบดีว่าการเรียงลำดับการผสานโดยไม่แสดงอาการนั้นกินเวลา O(n บันทึก n) เสมอ แต่กรณีและปัญหาที่ต้องการการเปรียบเทียบมากกว่านั้นมักใช้เวลาในทางปฏิบัติมากกว่า ตอนนี้ เราจำเป็นต้องกำหนดการเปลี่ยนแปลงขององค์ประกอบอินพุตที่จะนำไปสู่การเปรียบเทียบจำนวนมากที่สุดเมื่อทำการจัดเรียงโดยใช้อัลกอริทึม Merge Sort ทั่วไป
ตัวอย่าง
พิจารณาชุดขององค์ประกอบด้านล่างเป็นอาร์เรย์ที่เรียงลำดับ 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}
ในตอนนี้ เพื่อสร้างกรณีที่เลวร้ายที่สุดของการเรียงลำดับการผสาน การดำเนินการผสานที่ส่งผลให้อาร์เรย์ที่เรียงลำดับข้างต้นควรส่งผลให้เกิดการเปรียบเทียบมากที่สุด ด้วยเหตุนี้ อาร์เรย์ย่อยด้านซ้ายและขวาที่เกี่ยวข้องกับการดำเนินการผสานควรเก็บองค์ประกอบสำรองของ sortedarray ดังกล่าว ซึ่งอาร์เรย์ย่อยด้านซ้ายควรเป็น {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[])
-
ตอนนี้เราสร้างอาร์เรย์เสริมสองชุดด้านซ้ายและขวาและเก็บองค์ประกอบอาร์เรย์สำรองไว้
-
เราเรียก 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
