1. บทนำ
ในการกวดวิชานี้เราจะต้องดูที่ขั้นตอนวิธีการผสานการเรียงลำดับและการดำเนินการใน Java
การเรียงลำดับการผสานเป็นหนึ่งในเทคนิคการเรียงลำดับที่มีประสิทธิภาพมากที่สุดและเป็นไปตามกระบวนทัศน์ "แบ่งและพิชิต"
2. อัลกอริทึม
Merge sort คืออัลกอริทึม "หารและพิชิต" โดยเราแบ่งปัญหาออกเป็นปัญหาย่อยก่อน เมื่อแนวทางแก้ไขสำหรับปัญหาย่อยพร้อมแล้วเราจะรวมเข้าด้วยกันเพื่อหาแนวทางแก้ไขปัญหาขั้นสุดท้าย
นี่เป็นหนึ่งในอัลกอริทึมที่สามารถใช้งานได้อย่างง่ายดายโดยใช้การเรียกซ้ำขณะที่เราจัดการกับปัญหาย่อยมากกว่าปัญหาหลัก
อัลกอริทึมสามารถอธิบายได้เป็นกระบวนการ 2 ขั้นตอนต่อไปนี้:
- Divide: ในขั้นตอนนี้เราแบ่งอาร์เรย์อินพุตออกเป็น 2 ส่วนโดยเดือยเป็นจุดกึ่งกลางของอาร์เรย์ ขั้นตอนนี้จะดำเนินการแบบวนซ้ำสำหรับอาร์เรย์ครึ่งหนึ่งทั้งหมดจนกว่าจะไม่มีครึ่งอาร์เรย์ให้หารอีก
- พิชิต: ในขั้นตอนนี้เราจัดเรียงและรวมอาร์เรย์ที่แบ่งจากล่างขึ้นบนและรับอาร์เรย์ที่เรียงลำดับ
แผนภาพต่อไปนี้แสดงกระบวนการจัดเรียงการผสานที่สมบูรณ์สำหรับอาร์เรย์ตัวอย่าง {10, 6, 8, 5, 7, 3, 4}
หากเราพิจารณาแผนภาพอย่างละเอียดเราจะเห็นว่าอาร์เรย์ถูกแบ่งออกเป็นสองส่วนซ้ำ ๆ จนกว่าขนาดจะกลายเป็น 1 เมื่อขนาดกลายเป็น 1 กระบวนการผสานจะเข้าสู่การปฏิบัติและเริ่มรวมอาร์เรย์กลับในขณะที่เรียงลำดับ:
3. การนำไปใช้
สำหรับการนำไปใช้งานเราจะเขียนฟังก์ชันmergeSortซึ่งใช้เวลาในอาร์เรย์อินพุตและความยาวเป็นพารามิเตอร์ นี่จะเป็นฟังก์ชันวนซ้ำดังนั้นเราจึงต้องการฐานและเงื่อนไขการเรียกซ้ำ
เงื่อนไขพื้นฐานจะตรวจสอบว่าความยาวอาร์เรย์เป็น 1 หรือไม่และจะกลับมา สำหรับกรณีที่เหลือการเรียกซ้ำจะดำเนินการ
สำหรับกรณี recursive เราได้รับดัชนีกลางและสร้างสองอาร์เรย์ชั่วคราวลิตร []และR [] mergesortฟังก์ชั่นจากนั้นจะเรียกว่าซ้ำสำหรับทั้งอาร์เรย์ย่อย:
public static void mergeSort(int[] a, int n) { if (n < 2) { return; } int mid = n / 2; int[] l = new int[mid]; int[] r = new int[n - mid]; for (int i = 0; i < mid; i++) { l[i] = a[i]; } for (int i = mid; i < n; i++) { r[i - mid] = a[i]; } mergeSort(l, mid); mergeSort(r, n - mid); merge(a, l, r, mid, n - mid); }จากนั้นเราจะเรียกผสานฟังก์ชั่นซึ่งจะใช้เวลาในการป้อนข้อมูลและทั้งสองย่อยอาร์เรย์และเริ่มต้นและจุดสิ้นสุดของดัชนีทั้งอาร์เรย์ย่อย
ผสานฟังก์ชั่นเปรียบเทียบองค์ประกอบของทั้งอาร์เรย์ย่อยหนึ่งโดยหนึ่งและวางองค์ประกอบที่มีขนาดเล็กลงในอาร์เรย์การป้อนข้อมูล
เมื่อเราไปถึงจุดสิ้นสุดของหนึ่งในอาร์เรย์ย่อยองค์ประกอบที่เหลือจากอาร์เรย์อื่นจะถูกคัดลอกไปยังอาร์เรย์อินพุตดังนั้นจึงทำให้เรามีอาร์เรย์ที่เรียงลำดับสุดท้าย:
public static void merge( int[] a, int[] l, int[] r, int left, int right) { int i = 0, j = 0, k = 0; while (i < left && j < right) { if (l[i] <= r[j]) { a[k++] = l[i++]; } else { a[k++] = r[j++]; } } while (i < left) { a[k++] = l[i++]; } while (j < right) { a[k++] = r[j++]; } } การทดสอบหน่วยสำหรับโปรแกรม:
@Test public void positiveTest() { int[] actual = { 5, 1, 6, 2, 3, 4 }; int[] expected = { 1, 2, 3, 4, 5, 6 }; MergeSort.mergeSort(actual, actual.length); assertArrayEquals(expected, actual); }4. ความซับซ้อน
เนื่องจากการเรียงลำดับการผสานเป็นอัลกอริธึมแบบวนซ้ำความซับซ้อนของเวลาสามารถแสดงเป็นความสัมพันธ์แบบวนซ้ำต่อไปนี้:
T(n) = 2T(n/2) + O(n)2T (n / 2)ตรงกับเวลาที่ต้องใช้ในการจัดเรียงอาร์เรย์ย่อยและเวลาO (n)ในการรวมอาร์เรย์ทั้งหมด
เมื่อแก้ไขแล้วความซับซ้อนของเวลาจะมาถึงO (nLogn)
นี่เป็นเรื่องจริงสำหรับกรณีที่แย่ที่สุดค่าเฉลี่ยและดีที่สุดเนื่องจากจะแบ่งอาร์เรย์ออกเป็นสองส่วนแล้วรวมเข้าด้วยกัน
ความซับซ้อนของพื้นที่ของอัลกอริทึมคือO (n)เนื่องจากเรากำลังสร้างอาร์เรย์ชั่วคราวในการเรียกซ้ำทุกครั้ง
5. สรุป
ในบทช่วยสอนฉบับย่อนี้เราได้เห็นการทำงานของอัลกอริธึมการเรียงลำดับการผสานและวิธีการนำไปใช้ใน Java
รหัสการทำงานทั้งหมดมีอยู่บน GitHub