دمج الفرز في جافا

ما هو دمج الفرز؟

تعد عملية فرز الدمج هي الخوارزمية الأكثر شيوعًا لفرز البيانات باستخدام تقنية " فرق تسد ". في هذه الخوارزمية، يتم تقسيم المشكلة إلى مشاكل فرعية ثم بعد فرزها يتم دمجها معًا. لنفترض أن لدينا قائمة بالأرقام غير المصنفة، نتيجة فصل دراسي لمادة معينة. لفرزها بترتيب تصاعدي، سنحتاج إلى وضعها في قائمة تبدأ من الأقل إلى الأعلى. في خوارزمية فرز الدمج هذه، سيتم تقسيم القائمة إلى قوائم أصغر لفرزها بترتيب تصاعدي ثم سيتم دمج النتائج لفهم أفضل. يمكن شرح دمج الفرز في Java من خلال مثال لمصفوفة {6,9,8,2,4,1}، اعتبرها نتيجة اختبار فئة من 10. سيتم تقسيم المصفوفة (النتائج) بشكل متكرر إلى قطع أصغر حتى يصبح حجمها 1. ثم تتم عملية الدمج أثناء فرز الأرقام في وقت واحد. سيوفر لنا هذا نتيجة تبدأ من أدنى الدرجات إلى أعلى الدرجات التي تم الحصول عليها. سيتم تقسيم هذه المصفوفة إلى مصفوفتين تحتوي كل منهما على 3 عناصر كما هو موضح أدناه في الخطوة 2 وتستمر في الانقسام حتى يتم الوصول إلى الوحدة في الخطوة 4 . ثم تبدأ خوارزمية فرز الدمج في فرز الأرقام خطوة بخطوة ( الخطوة 5 ) ثم تقوم بدمج الأرقام في مصفوفة أكبر في الخطوتين 6 و7 .

تطبيق

في التنفيذ، سنكتب رمزًا لخوارزمية فرز الدمج في Java. المتغيرات المطلوبة ستكون مصفوفة الإدخال وطول المصفوفة. سيتم استخدام هاتين المعلمتين أيضًا لتقديم معلمات إضافية لإنشاء وظيفة فرز الدمج. دعونا نلقي نظرة على المقتطف أدناه لفهم العمل العام لخوارزمية فرز الدمج في 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، يتم استخدام البداية والنهاية لتحديد الوسط. ثم في الخطوة التالية، يتم إنشاء مصفوفتين فرعيتين جديدتين تبدأ من البداية إلى المنتصف والأخرى تبدأ من المنتصف +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 in Java خوارزمية بسيطة للحصول على قائمة مرتبة من قائمة أرقام غير مصنفة. يتم تطبيق الطريقة الأساسية " فرق تسد " للوصول إلى المصفوفة المصنفة من مصفوفة غير مصنفة.