شرح خوارزمية الترتيب بالدمج Merge Sort

خوارزمية الترتيب بالدمج Merge Sort هى طريقة قوية، متعددة الإستخدام، مبنية على المقارنة. طريقة قوية؟ نعم قوية ﻷنها تأخذ وقت قليل مقارنةً بباقى أنواع خوارزميات الترتيب وفى نفس الوقت نتائجها مُستقرة.

متعددة الإستخدام؟ تعدد الإستخدام يعنى أن هذه الخوارزمية تستطيع ترتيب أى نوع من البيانات الرقمية التى يُمكن مقارنتها. مبنية على المقارنة؟ نعم، فكرة خوارزمية الترتيب merge sort تعتمد على المقارنة لكى تحدد القيمة الأكبر والقيمة الأصغر. وإليك الشرح بالخطوات.

صورة توضح خطوات خوارزمية الترتيب merge sort بشكل متحرك

خطوات عمل خوارزمية الترتيب Merge Sort :

مخطط يوضح خطوات خوارزمية الترتيب merge sort

1. تقسيم المصفوفة (array) إلى مصفوفتين
2. تقسيم كل مصفوفة إلى مصفوفتين، حتى الوصول إلى مصفوفات بها عنصر واحد فقط
3. دمج كل مصفوفة مع المجاورة لها بالترتيب بناءاً على المقارنة (merge arrays)
4. إنشاء مصفوفة جديدة من كل مصفوفتين سابقتين بناءاً على مقارنة أول عنصر فى مصفوفة بأول عنصر فى المصفوفة الأخرى وهكذا حتى الحصول على مصفوفة مرتبه من مصفوفتين مرتبتين
5. إنشاء مصفوفة جديدة من كل مصفوفتين سابقتين حسب الترتيب. يتم ذلك بمقارنة العنصر الأول من كلا المصفوفتين وأخذ الأصغر، ثم المقارنة من جديد وأخذ الأصغر،.. وهكذا حتى الوصول إلى مرحلة تكون فيها مصفوفة واحدة مُرتبة!

تطبيق خوارزمية الترتيب بالدمج فى لغة جو:

package main
import "fmt"
func merge(a []int, b []int) []int {
  var r = make([]int, len(a) + len(b))
  var i = 0
  var j = 0
  for i < len(a) && j < len(b) {

    if a[i] <= b[j] {
      r[i+j] = a[i]
      i++
    } else {
      r[i+j] = b[j]
      j++
    }
 
  }
  for i < len(a) { r[i+j] = a[i]; i++ }
  for j < len(b) { r[i+j] = b[j]; j++ }
  return r

}
func Mergesort(items []int) []int {
  if len(items) < 2 {
    return items
 
  }
  var middle = len(items) / 2
  var a = Mergesort(items[:middle])
  var b = Mergesort(items[middle:])
  return merge(a, b)

}
func main () {
  fmt.Print(Mergesort([]int{ 10, 9, 8, 4, 5, 6, 13, 55, 72, 86, 100, 123, 7, 3, 2, 1 }), "\n")

}
مصدر كود خوارزمية الترتيب بالدمج فى لغة جو : Github

تطبيق خوارزمية الترتيب بالدمج فى لغة جافا :

package Sorts;
import static Sorts.SortUtils.print;
class MergeSort implements SortAlgorithm {
    @Override
    @SuppressWarnings("unchecked")
    public <T extends Comparable<T>> T[] sort(T[] unsorted) {
        T[] tmp = (T[]) new Comparable[unsorted.length];
        doSort(unsorted, tmp, 0, unsorted.length - 1);
        return unsorted;
    }
    private  static <T extends Comparable<T>> void doSort(T[] arr, T[] temp, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            doSort(arr, temp, left, mid);
            doSort(arr,  temp,mid + 1, right);
            merge(arr, temp, left, mid, right);
        }
   }
    private static <T extends Comparable<T>> void merge(T[] arr, T[] temp, int left, int mid, int right) {
        System.arraycopy(arr, left, temp, left, right - left + 1);
        int i= left;
        int j = mid + 1;
        int k = left;
        while (i <= mid && j <= right) {
            if (temp[i].compareTo(temp[j]) <= 0) {
                arr[k++] = temp[i++];
            }
            else {
                arr[k++] = temp[j++];
            }
        }
        while (i <= mid) {
            arr[k++] = temp[i++];
        }
while (j <= right) {
    arr[k++] = temp[j++];
}
    }
    // Driver program
    public static void main(String[] args) {
        // Integer Input
        Integer[] arr = {10, 9, 8, 4, 5, 6, 13, 55, 72, 86, 100, 123, 7, 3, 2, 1};
        MergeSort mergeSort = new MergeSort();
        mergeSort.sort(arr);
        // Output => 1    4  6 9 12 23 54 78 231
        print(arr);
        // String Inpu
//        String[] stringArray = {"c", "a", "e", "b","d"};
//        mergeSort.sort(stringArray);
        //Output => a b c d e
//        print(stringArray);
    }
}
مصدر كود خوارزمية الترتيب بالدمج فى لغة جافا : Github.

تطبيق خوارزمية الترتيب بالدمج فى لغة بايثون:

def merge_sort(LIST):
    start = []
    end = []
    while len(LIST) > 1:
        a = min(LIST)
        b = max(LIST)
        start.append(a)
        end.append(b)
        LIST.remove(a)
        LIST.remove(b)
    if LIST: start.append(LIST[0])
    end.reverse()
    return (start + end)
print(merge_sort({10, 9, 8, 4, 5, 6, 13, 55, 72, 86, 100, 123, 7, 3, 2, 1}))
مصدر كود خوارزمية الترتيب بالدمج فى لغة بايثون : Github.

إن كان لديك أى استفسار، أكتبه فى تعليق وسأقوم بالرد عليك إن شاء الله. أما إن أردت الوصول لنا بسرعة أكتب على جوجل استفسارك وبعده كلمة "موقع أبانوب" مثل "خوارزميات الترتيب موقع ابانوب".
تعليقات الفيسبوك
0 تعليقات جوجل

0 تعليقات:

إرسال تعليق

اقرأ أيضاً