ผสานการเรียงลำดับใน Java

การเรียงลำดับแบบผสานคืออะไร?

Merge Sort เป็นอัลกอริทึมที่ใช้กันทั่วไปในการจัดเรียงข้อมูลโดยใช้เทคนิค " หารแล้วพิชิต " ในอัลกอริธึมนี้ ปัญหาจะถูกแบ่งออกเป็นปัญหาย่อย จากนั้นหลังจากการเรียงลำดับ ปัญหาก็จะรวมเข้าด้วยกัน สมมติว่าเรามีรายการตัวเลขที่ไม่ได้เรียงลำดับซึ่งเป็นผลลัพธ์ของคลาสสำหรับวิชาใดวิชาหนึ่ง หากต้องการเรียงลำดับจากน้อยไปหามาก เราจะต้องเรียงลำดับจากต่ำไปสูง ในอัลกอริธึม Merge Sort นี้ รายการจะถูกแบ่งออกเป็นรายการเล็กๆ เพื่อเรียงลำดับจากน้อยไปมาก จากนั้นจะรวมผลลัพธ์เพื่อความเข้าใจที่ดีขึ้น Merge Sort ใน Java สามารถอธิบายได้ผ่านตัวอย่างของอาเรย์ {6,9,8,2,4,1} ลองพิจารณาว่าเป็นผลจากการทดสอบคลาสเต็ม 10 อาเรย์ (ของผลลัพธ์) จะถูกแบ่งซ้ำๆ ให้เป็นชิ้นเล็กๆ จนมีขนาด 1 จากนั้นจึงเกิดกระบวนการรวมพร้อมเรียงตัวเลขพร้อมกัน สิ่งนี้จะให้ผลลัพธ์ที่เริ่มต้นด้วยคะแนนต่ำสุดไปจนถึงคะแนนสูงสุดที่ได้รับ อาร์เรย์นี้จะแบ่งออกเป็นสองอาร์เรย์ซึ่งแต่ละองค์ประกอบจะมี 3 องค์ประกอบดังแสดงด้านล่างใน ขั้นตอน ที่2และจะแบ่งไปเรื่อยๆ จนกว่าจะถึงความสามัคคีในขั้นตอนที่ 4 จากนั้นอัลกอริทึม Merge Sort จะเริ่มเรียงลำดับตัวเลขทีละขั้นตอน ( ขั้นตอนที่ 5 ) จากนั้นจึงรวมตัวเลขให้เป็นอาร์เรย์ที่ใหญ่กว่าในขั้น ตอนที่ 6 และ 7

การนำไปปฏิบัติ

ในการใช้งานเราจะเขียนโค้ดสำหรับอัลกอริทึมการเรียงลำดับแบบผสานใน Java ตัวแปรที่ต้องการจะเป็นอาร์เรย์อินพุตและความยาวของอาร์เรย์ พารามิเตอร์ทั้งสองนี้จะถูกนำมาใช้เพิ่มเติมเพื่อแนะนำพารามิเตอร์เพิ่มเติมเพื่อสร้างฟังก์ชันการเรียงลำดับแบบผสาน มาดูตัวอย่างด้านล่างเพื่อทำความเข้าใจการทำงานทั่วไปของ Merge Sort Algorithm ใน Java

Merge_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");
    }
}

เอาท์พุต

บทสรุป

Merge Sort ใน Java เป็นอัลกอริทึมง่ายๆ ในการรับรายการที่เรียงลำดับจากรายการตัวเลขที่ไม่ได้เรียงลำดับ วิธีการพื้นฐานของ 'การแบ่งและการพิชิต ' ถูกนำมาใช้เพื่อเข้าถึงอาร์เรย์ที่เรียงลำดับจากอาร์เรย์ที่ไม่ได้เรียงลำดับ