ما هو دمج الفرز؟
تعد عملية فرز الدمج هي الخوارزمية الأكثر شيوعًا لفرز البيانات باستخدام تقنية " فرق تسد ". في هذه الخوارزمية، يتم تقسيم المشكلة إلى مشاكل فرعية ثم بعد فرزها يتم دمجها معًا. لنفترض أن لدينا قائمة بالأرقام غير المصنفة، نتيجة فصل دراسي لمادة معينة. لفرزها بترتيب تصاعدي، سنحتاج إلى وضعها في قائمة تبدأ من الأقل إلى الأعلى. في خوارزمية فرز الدمج هذه، سيتم تقسيم القائمة إلى قوائم أصغر لفرزها بترتيب تصاعدي ثم سيتم دمج النتائج لفهم أفضل. يمكن شرح دمج الفرز في 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");
}
}
انتاج |
المصفوفة الأصلية [6، 9، 8، 2، 4، 1] بعد الفرز بالدمج [1، 2، 4، 6، 8، 9]
GO TO FULL VERSION