แนวคิด
เกี่ยวกับชุดองค์ประกอบที่กำหนด ให้กำหนดว่าการเรียงสับเปลี่ยน (permutation) ใดขององค์ประกอบเหล่านี้จะทำให้ Merge Sort ทำงานในกรณีแย่ที่สุด (worst case)
เรารู้ว่า แบบอะซิมปโตติก (asymptotically) merge sort ใช้เวลา O(n log n) เสมอ แต่กรณีที่ต้องการการเปรียบเทียบมากกว่าจะใช้เวลามากกว่าในทางปฏิบัติ ตอนนี้เราต้องการกำหนดการเรียงสับเปลี่ยนของอินพุตที่จะนำไปสู่จำนวนการเปรียบเทียบมากที่สุดเมื่อจัดเรียงด้วยอัลกอริทึม Merge Scan แบบปกติ
ตัวอย่าง
พิจารณาชุดองค์ประกอบด้านล่างเป็นอาร์เรย์ที่เรียงแล้ว: 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
อินพุทอาร์เรย์ที่ทำให้ merge sort ทำงานแย่ที่สุดคือ: 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
วิธีการ
เราสำรวจวิธีได้อินพุทกรณีแย่ที่สุดสำหรับ merge sort สำหรับชุดอินพุท?
ตอนนี้เราลองสร้างอาร์เรย์แบบบอตอมอัพ (bottom-up)
ให้อาร์เรย์ที่เรียงแล้วเป็น {11, 12, 13, 14, 15, 16, 17, 18}
ตอนนี้เพื่อสร้างกรณีแย่ที่สุดของ merge sort การดำเนินการ merge ที่ทำให้ได้อาร์เรย์ที่เรียงแล้วข้างต้น ควรทำให้เกิดการเปรียบเทียบมากที่สุด ผลลัพธ์คือ ซับอาร์เรย์ซ้ายและขวาที่เกี่ยวข้องใน merge operation ควรเก็บองค์ประกอบสลับกันของ sorted array โดยที่ ซับอาร์เรย์ซ้ายควรเป็น {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)
- คัดลอกองค์ประกอบทั้งหมดของซับอาร์เรย์ซ้ายและขวากลับไปที่อาร์เรย์ต้นฉบับ
ตัวอย่างโค้ด
#include <stdlib.h>
#include <stdio.h>
// ฟังก์ชันพิมพ์อาร์เรย์
void printArray(int A1[], int size1) {
for (int i = 0; i < size1; i++)
printf("%d ", A1[i]);
printf("\n");
}
// ฟังก์ชันรวมซับอาร์เรย์ซ้ายและขวา
int join(int arr1[], int left1[], int right1[], int l1, int m1, int r1) {
int i; // ใช้ในลูปที่สอง
for (i = 0; i <= m1 - l1; i++)
arr1[i] = left1[i];
for (int j = 0; j < r1 - m1; j++)
arr1[i + j] = right1[j];
}
// ฟังก์ชันเก็บองค์ประกอบสลับกันในซับอาร์เรย์ซ้ายและขวา
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];
}
// ฟังก์ชันสร้างกรณีแย่ที่สุดของ Merge Sort
int generateWorstCase(int arr1[], int l1, int r1) {
if (l1 < r1) {
int m1 = l1 + (r1 - l1) / 2;
// สร้างอาร์เรย์ช่วยสองตัว
int left1[m1 - l1 + 1];
int right1[r1 - m1];
// เก็บองค์ประกอบสลับกันในซับอาร์เรย์ซ้ายและขวา
split(arr1, left1, right1, l1, m1, r1);
// เรียกซ้ำครึ่งแรกและครึ่งหลัง
generateWorstCase(left1, l1, m1);
generateWorstCase(right1, m1 + 1, r1);
// รวมซับอาร์เรย์ซ้ายและขวา
join(arr1, left1, right1, l1, m1, r1);
}
}
// โค้ดหลัก
int main() {
// เริ่มต้นอาร์เรย์ที่เรียงแล้ว
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("อาร์เรย์ที่เรียงแล้วคือ \n");
printArray(arr1, n1);
// สร้างกรณีแย่ที่สุดของ Merge Sort
generateWorstCase(arr1, 0, n1 - 1);
printf("\nอินพุทอาร์เรย์ที่จะทำให้เกิด worst case ของ merge sort คือ \n");
printArray(arr1, n1);
return 0;
}
ผลลัพธ์
อาร์เรย์ที่เรียงแล้วคือ 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 อินพุทอาร์เรย์ที่จะทำให้เกิด worst case ของ merge sort คือ 11 19 15 23 13 21 17 25 12 20 16 24 14 22 18 26
