جاوا میں ترتیب کو ضم کریں۔

انضمام کی ترتیب کیا ہے؟

مرج ترتیب " تقسیم اور فتح " تکنیک کا استعمال کرتے ہوئے ڈیٹا کو چھانٹنے کے لیے سب سے عام الگورتھم ہے۔ اس الگورتھم میں مسئلہ کو ذیلی مسائل میں تقسیم کیا جاتا ہے اور پھر چھانٹنے کے بعد ان کو ایک ساتھ ملا دیا جاتا ہے۔ ہم کہتے ہیں کہ ہمارے پاس غیر ترتیب شدہ نمبروں کی ایک فہرست ہے، جو کسی خاص مضمون کے لیے کلاس کا نتیجہ ہے۔ ان کو صعودی ترتیب سے ترتیب دینے کے لیے ہمیں انہیں نیچے سے بلندی تک ایک فہرست میں رکھنا ہوگا۔ اس مرج سورٹ الگورتھم میں، فہرست کو صعودی ترتیب میں ترتیب دینے کے لیے چھوٹی فہرستوں میں تقسیم کیا جائے گا اور پھر یہ نتائج کو بہتر طور پر سمجھنے کے لیے ضم کر دے گا۔ جاوا میں ضم کریں ترتیب کو ایک صف {6,9,8,2,4,1} کی ایک مثال کے ذریعے سمجھایا جا سکتا ہے، اسے 10 میں سے کلاس ٹیسٹ کے نتیجے کے طور پر سمجھیں۔ سرنی (نتائج کی) کو بار بار تقسیم کیا جائے گا۔ چھوٹے ٹکڑوں میں جب تک کہ ان کا سائز 1 نہ ہوجائے۔ پھر انضمام کا عمل ایک ساتھ نمبروں کو ترتیب دیتے ہوئے ہوتا ہے۔ یہ ہمیں ایک ایسا نتیجہ فراہم کرے گا جو سب سے کم نمبروں سے لے کر سب سے زیادہ نمبروں تک حاصل ہوتا ہے۔ اس صف کو دو صفوں میں تقسیم کیا جائے گا جس میں 3 عناصر شامل ہوں گے جیسا کہ ذیل میں مرحلہ 2 میں دکھایا گیا ہے اور یہ اس وقت تک تقسیم ہوتی رہتی ہے جب تک کہ مرحلہ 4 میں اتحاد نہ ہو جائے ۔ پھر مرج سورٹ الگورتھم نمبروں کو ایک وقت میں ایک قدم ( مرحلہ 5 ) کو ترتیب دینا شروع کرتا ہے اور پھر نمبروں کو 6 اور 7 مرحلے میں ایک بڑی صف میں ضم کرتا ہے ۔

نفاذ

نفاذ میں ہم جاوا میں ضم ہونے والے الگورتھم کے لیے کوڈ لکھیں گے۔ متغیر مطلوبہ ان پٹ سرنی اور سرنی کی لمبائی ہو گی۔ ان دو پیرامیٹرز کو مزید پیرامیٹرز متعارف کرانے کے لیے استعمال کیا جائے گا تاکہ انضمام کی ترتیب کا فنکشن بنایا جا سکے۔ آئیے جاوا میں مرج سورٹ الگورتھم کے عمومی کام کو سمجھنے کے لیے ذیل کے ٹکڑوں پر ایک نظر ڈالیں۔

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

سب سے پہلے اگر شرط کے ذریعے شروع اور اختتام درمیانی کا تعین کرنے کے لیے استعمال کیا جاتا ہے۔ پھر اگلے مرحلے میں، 2 نئے ذیلی دائرے بنائے جاتے ہیں جو شروع سے مشرق تک شروع ہوتے ہیں اور دوسرے درمیانی +1 سے شروع ہوتے ہوئے اختتام تک۔ یہ صفوں کو اس وقت تک تقسیم کیا جاتا ہے جب تک کہ ان کی لمبائی 1 نہ ہو جائے اور پھر مرج فنکشن کے ذریعے ترتیب شدہ ذیلی ریز شروع، مڈل، مڈل+1 اور اینڈ سب کو دوبارہ ضم کر دیا جاتا ہے تاکہ حل حاصل کیا جا سکے۔

مثال

جاوا میں درج ذیل کوڈ انضمام کے الگورتھم کی وضاحت کرتا ہے:

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

آؤٹ پٹ

نتیجہ

جاوا میں ضم کریں ترتیب نمبروں کی غیر ترتیب شدہ فہرست سے ترتیب شدہ فہرست حاصل کرنے کے لیے ایک سادہ الگورتھم ہے۔ ' تقسیم اور فتح ' کا بنیادی طریقہ غیر ترتیب شدہ صف سے ترتیب شدہ صف تک رسائی کے لیے لاگو ہوتا ہے۔