การเรียงลำดับแบบผสานคืออะไร?
Merge Sort เป็นอัลกอริทึมที่ใช้กันทั่วไปในการจัดเรียงข้อมูลโดยใช้เทคนิค " หารแล้วพิชิต " ในอัลกอริธึมนี้ ปัญหาจะถูกแบ่งออกเป็นปัญหาย่อย จากนั้นหลังจากการเรียงลำดับ ปัญหาก็จะรวมเข้าด้วยกัน สมมติว่าเรามีรายการตัวเลขที่ไม่ได้เรียงลำดับซึ่งเป็นผลลัพธ์ของคลาสสำหรับวิชาใดวิชาหนึ่ง หากต้องการเรียงลำดับจากน้อยไปหามาก เราจะต้องเรียงลำดับจากต่ำไปสูง ในอัลกอริธึม Merge Sort นี้ รายการจะถูกแบ่งออกเป็นรายการเล็กๆ เพื่อเรียงลำดับจากน้อยไปมาก จากนั้นจะรวมผลลัพธ์เพื่อความเข้าใจที่ดีขึ้น Merge Sort ใน Java สามารถอธิบายได้ผ่านตัวอย่างของอาเรย์ {6,9,8,2,4,1} ลองพิจารณาว่าเป็นผลจากการทดสอบคลาสเต็ม 10 อาเรย์ (ของผลลัพธ์) จะถูกแบ่งซ้ำๆ ให้เป็นชิ้นเล็กๆ จนมีขนาด 1 จากนั้นจึงเกิดกระบวนการรวมพร้อมเรียงตัวเลขพร้อมกัน สิ่งนี้จะให้ผลลัพธ์ที่เริ่มต้นด้วยคะแนนต่ำสุดไปจนถึงคะแนนสูงสุดที่ได้รับ
การนำไปปฏิบัติ
ในการใช้งานเราจะเขียนโค้ดสำหรับอัลกอริทึมการเรียงลำดับแบบผสานใน Java ตัวแปรที่ต้องการจะเป็นอาร์เรย์อินพุตและความยาวของอาร์เรย์ พารามิเตอร์ทั้งสองนี้จะถูกนำมาใช้เพิ่มเติมเพื่อแนะนำพารามิเตอร์เพิ่มเติมเพื่อสร้างฟังก์ชันการเรียงลำดับแบบผสาน มาดูตัวอย่างด้านล่างเพื่อทำความเข้าใจการทำงานทั่วไปของ Merge Sort Algorithm ใน JavaMerge_Sort_Algo (Array, Beginning, End)
/** Three parameters required for the Merge Sort Algorithm
* Array = values of the array
* Beginning = the starting element of the array
* End = the ending element of the array*/
if (Beginning < End) // condition check Beginning must be less than End
set Middle = (Beginning + End) / 2 // Assigning Middle to the array
Merge_Sort_Algo (Array, Beginning, Middle) /** Sorting and merging of elements from Beginning to the Middle */
Merge_Sort_Algo (Array, Middle +1, End) /** Sorting and merging of elements from Middle to the End */
Merge (Array, Beginning, Middle, End) // Merging both the sorted arrays
end of if
End Merge_Sort_Algo
ขั้นแรกผ่านเงื่อนไข if Beginning และ End ใช้เพื่อกำหนดตรงกลาง จากนั้นในขั้นตอนถัดไป จะมีการสร้างอาร์เรย์ย่อยใหม่ 2 อาร์เรย์โดยเริ่มจากจุดเริ่มต้นถึงตรงกลาง และอีก 2 อาร์เรย์เริ่มต้นจาก +1 ตรงกลางไปยังจุดสิ้นสุด อาร์เรย์เหล่านี้จะถูกแบ่งจนกระทั่งความยาวกลายเป็น 1 จากนั้นผ่านฟังก์ชันผสาน อาร์เรย์ย่อยที่เรียงลำดับเริ่มต้น กลาง กลาง+1 และสิ้นสุดทั้งหมดจะถูกรวมกลับเพื่อรับโซลูชัน
ตัวอย่าง
รหัสต่อไปนี้ใน Java อธิบายอัลกอริทึมการเรียงลำดับแบบผสาน:import java.util.Arrays;
class HelloWorld {
public static void merge(
int[] array, int[] new_array_1, int[] new_array_2, int left, int right) {
// defining parameters
int i = 0, j = 0, k = 0;
while (i < left && j < right) { // conditions for merging
if (new_array_1[i] <= new_array_2[j]) {
array[k++] = new_array_1[i++];
}
else {
array[k++] = new_array_2[j++];
}
}
while (i < left) {
array[k++] = new_array_1[i++];
}
while (j < right) {
array[k++] = new_array_2[j++];
}
}
public static void mergeSort(int[] array, int length) { /** required parameters */
if (length < 2) { //condition for the length of array
return;
}
int middle = length / 2; // defining new parameter middle
int [ ] new_array_1 = new int [middle]; /** defining the new first array after division */
int [ ] new_array_2 = new int [length - middle]; /** defining the new second array */
for (int i = 0; i < middle; i++) { /**applying condition for sorting of new array 1 */
new_array_1 [ i ] = array [ i ];
}
for (int i = middle; i < length ; i++) { /**applying condition for sorting of new array 2 */
new_array_2 [ i - middle] = array [ i ];
}
mergeSort (new_array_1, middle); /** calling merge sort function for new array 1 */
mergeSort (new_array_2, length - middle); /** calling merge sort function for new array 2 */
merge(array, new_array_1, new_array_2, middle, length - middle); /** calling function for merging of new array 1 and new array 2 */
}
public static void main(String[] args) {
int [ ] testScores = {6,9,8,2,4,1};
int size = testScores.length;
System.out.println("Original Array " + Arrays.toString(testScores) + "\n");
mergeSort(testScores, size);
System.out.println("After Merge Sort " + Arrays.toString(testScores) + "\n");
}
}
เอาท์พุต
อาร์เรย์ดั้งเดิม [6, 9, 8, 2, 4, 1] หลังจากผสาน เรียงลำดับ [1, 2, 4, 6, 8, 9]
GO TO FULL VERSION