تصنيف دمجي

مثال للتصنيف الدمجي.

تصنيف دمجي هي إحدى خوارزميات التصنيف أو ترتيب مجموعة من عناصر الرقمية تصاعديا، طورها العالم الألماني فون نيومان، تعتمد هذه الخوارزمية على مبدء "فرق تسد" (بالإنكليزية: divide and conquer)، عدد الخطوات اللازمة للخوارزمية لإنجاز المعالجة على مجموعة من مدخلات تقاس بـ N*Log N.

خطوات الخوارزمية مفهوم خوارزمية التصنيف الدمجي يقوم على خطوات التالية

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

تعتمد الخوارزمية بشكل أساسي على مفهومين رئيسيين :

1. المفهوم الأول : هو ان المصفوفات التي تحتوي على اقل عناصر يمكن ترتيبها بشكل اسرع وتحتاج إلى خطوات اقل.
2. الفهوم الثاني : هو عملية دمج المصفوفات الصغيرة التي تحتوي على عناصر قليلة المرتبة لتشكيل مصفوفات أكبر مرتبة أيضا

تطبيق من الأعلى إلى الأسفل (Top-down)

function merge_sort(list m)
    // if list size is 1, consider it sorted and return it
    if length(m) <= 1
        return m
    // else list size is > 1, so split the list into two sublists
    var list left, right
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after or equal middle
         add x to right
    // recursively call merge_sort() to further split each sublist
    // until sublist size is 1
    left = merge_sort(left)
    right = merge_sort(right)
    // merge the sublists returned from prior calls to merge_sort()
    // and return the resulting merged sublist
    return merge(left, right)

في هذا المثال، الدالة merge تدمج المجموعتين الجزئيتين اليسرى واليمنى

function merge(left, right)
    var list result
    while length(left) > 0 or length(right) > 0
        if length(left) > 0 and length(right) > 0
            if first(left) <= first(right)
                append first(left) to result
                left = rest(left)
            else
                append first(right) to result
                right = rest(right)
        else if length(left) > 0
            append first(left) to result
            left = rest(left)
        else if length(right) > 0
            append first(right) to result
            right = rest(right)
    end while
    return result

تطبيق من الأسفل إلى الأعلى (Bottom-up)

/* array A[] has the items to sort; array B[] is a work array */
BottomUpSort(int n, array A[n], array B[n])
{
  int width;
 
  /* each 1-element run in A is already "sorted". */
 
  /* Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted */
  for (width = 1; width < n; width = 2 * width)
    {
      int i;
 
      /* array A is full of runs of length width */
      for (i = 0; i < n; i = i + 2 * width)
        {
          /* merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[] */
          /*  or copy A[i:n-1] to B[] ( if(i+width >= n) ) */
          BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
        }
 
      /* now work array B is full of runs of length 2*width */
      /* copy array B to array A for next iteration */
      /*   a more efficient implementation would swap the roles of A and B */
      CopyArray(A, B, n);
      /* now array A is full of runs of length 2*width */
    }
}
 
BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[])
{
  int i0 = iLeft;
  int i1 = iRight;
  int j;
 
  /* while there are elements in the left or right lists */
  for (j = iLeft; j < iEnd; j++)
    {
      /* if left list head exists and is <= existing right list head */
      if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
        {
          B[j] = A[i0];
          i0 = i0 + 1;
        }
      else
        {
          B[j] = A[i1];
          i1 = i1 + 1;
        }
    }
}