الخوارزميات للمحترفين خوارزميات الترتيب وأشهرها

سنتحدث في هذه المقالة عن بعض المفاهيم العامة المتعلقة بخوارزميات الترتيب، ثم نستعرض 10 من أشهر خوارزميات ترتيب المصفوفات.

قبل أن نواصل، سنعطي بعض التعاريف العامة.

• خوارزميات الترتيب المستقرة: تكون خوارزمية ترتيب ما مستقرةً stable إذا كانت تحافظ على الترتيب النسبي للعناصر التي لها نفس قيمة المفتاح الذي يُجرى الترتيب وفقًا له.
• خوارزميات الترتيب الموضعية In place algorithms: نقول أنّ خوارزمية ترتيب ما هي خوارزمية موضعية In place إذا كانت الذاكرة الإضافية التي تستخدمها أثناء الترتيب تساوي ‎O(1)‎ (دون احتساب المصفوفة المراد ترتيبها).
• أسوء حالة تعقيدية Worst case complexity: نقول أنّ أسوء حالة تعقيدية Worst case complexity لخوارزمية تساوي ‎O(T(n))‎ إذا كان وقت تشغيلها لا يزيد عن ‎T(n)‎ مهما كانت المدخلات.
• أفضل حالة تعقيدية Best case complexity: نقول أنّ أفضل حالة تعقيدية Best case complexity لخوارزمية ما تساوي ‎O(T(n))‎ إذا كان وقت تشغيلها لا يقل عن ‎T(n)‎ مهما كانت المدخلات.
• أوسط حالة تعقيدية Average case complexity: نقول أنّ أوسط حالة تعقيدية Average case complexity لخوارزمية ترتيب ما تساوي ‎O(T(n))‎ إذا كان متوسط أوقات تشغيلها بالنسبة لجميع المدخلات الممكنة يساوي ‎T(n)‎.

استقرار الترتيب Stability in Sorting

تكون خوارزمية الترتيب مستقرةً إذا كانت تحافظ على الترتيب النسبي للقيم ذات المفاتيح المتساوية في المصفوفة المُدخلة الأصلية بعد ترتيبها. أي إن كانت خوارزمية الترتيب مستقرةً وكان هناك كائنَان لهما مفاتيح متساوية، فسيكون ترتيبُهما في الخرج المُرتّب مماثلًا لتَرتيبهما في المصفوفة المدخلة غير المرتبة. انظر مصفوفة الأزواج التالية:

(1, 2) (9, 7) (3, 4) (8, 6) (9, 3)

سنحاول ترتيب المصفوفة حسب العنصر الأول في كل زوج. سيخرج الترتيب المستقر لهذه القائمة ما يلي:

(1, 2) (3, 4) (8, 6) (9, 7) (9, 3)

وهو ترتيبٌ مستقر لأنّ ‎(9, 3)‎ تظهر بعد ‎(9, 7)‎ في المصفوفة الأصلية أيضًا. أما الترتيب غير مستقر فيكون كما يلي:

(1, 2) (3, 4) (8, 6) (9, 3) (9, 7)

قد ينتج عن الترتيب غير المستقر الخرج نفسه الذي يٌنتجه الترتيب المستقر أحيانًا، لكن ليس دائمًا.

هذه بعض أشهر أنواع التراتيب المستقرة:

• الترتيب بالدمج Merge sort.
• الترتيب بالإدراج Insertion sort.
• ترتيب بالجذر Radix sort .
• ترتيب Tim.
• الترتيب بالفقاعات Bubble Sort.

هذه بعض أنواع التراتيب غير المستقرة:

• الترتيب بالكومة Heap sort.
• الترتيب السريع Quick sort.

سوف نستعرض في بقية هذه المقالة 10 خوارزميات ترتيب شهيرة.

الترتيب بالفقاعات Bubble Sort

توازن خوارزمية الفقاعات ‎BubbleSort‎ كل زوج متتالي من العناصر في المصفوفة غير المرتبة، ثمّ تبدل مواضعهما إن كان تَرتيبهما خاطئًا. ويوضّح المثال التالي كيفية عمل خوارزمية الفقاعات على المصفوفة ‎{6,5,3,1,8,7,2,4}‎ (تُحاط الأزواج قيد المقارنة في كل خطوة بالرمز "**"):

{6,5,3,1,8,7,2,4}
{**5,6**,3,1,8,7,2,4} -- 5 < 6 -> تبديل
{5,**3,6**,1,8,7,2,4} -- 3 < 6 -> تبديل
{5,3,**1,6**,8,7,2,4} -- 1 < 6 -> تبديل
{5,3,1,**6,8**,7,2,4} -- 8 > 6 -> لا تبديل
{5,3,1,6,**7,8**,2,4} -- 7 < 8 -> تبديل
{5,3,1,6,7,**2,8**,4} -- 2 < 8 -> تبديل
{5,3,1,6,7,2,**4,8**} -- 4 < 8 -> تبديل

نحصل بعد الدورة الأولى على المصفوفة ‎{5,3,1,6,7,2,4,8}‎، لاحظ أنّ أكبر قيمة غير مرتبة في المصفوفة (8 في هذه الحالة) ستصل دائمًا إلى موضعها النهائي. للتأكد من أنّ المصفوفة مرتّبة ترتيبًا صحيحًا وأنّ كل عناصرها في المواضع الصحيحة، سيكون علينا تكرار هذه العملية n-1 مرّة، حيث يمثّل n طول المصفوفة المراد ترتيبها.

خوارزمية الترتيب بالفقاعات التي تُعرف أيضًا باسم الترتيب المتدرّج Sinking Sort، هي خوارزمية ترتيب بسيطة تمرّ مرارًا وتكرارًا على المصفوفة حتى ترتّبها، وتوازن كل زوج متتال من العناصر، ثمّ تبدّلهما إن كان ترتيبهما خاطئًا.

الرسم البياني التالي يمثّل آلية عمل خوارزمية الترتيب بالفقاعات:

هذه تطبيقات لخوارزمية الترتيب بالفقاعات بعدة لغات برمجة.

• لغة C++‎:

void bubbleSort(vector<int>numbers)
  {
      for(int i = numbers.size() - 1; i >= 0; i--) {
          for(int j = 1; j <= i; j++) {
              if(numbers[j-1] > numbers[j]) {
                  swap(numbers[j-1],numbers(j));
              }
          }
      }
  }

• لغة C:

void bubble_sort(long list[], long n)
{
 long c, d, t;
 for (c = 0 ; c < ( n - 1 ); c++)
 {
   for (d = 0 ; d < n - c - 1; d++)
   {
     if (list[d] > list[d+1])
     {
       /* تبديل */
       t         = list[d];
       list[d]   = list[d+1];
       list[d+1] = t;
     }
   }
 }
}

• هذا تطبيق يستخدم المؤشرات:

void pointer_bubble_sort(long * list, long n)
{
 long c, d, t;
 for (c = 0 ; c < ( n - 1 ); c++)
 {
   for (d = 0 ; d < n - c - 1; d++)
   {
     if ( * (list + d ) > *(list+d+1))
     {
       /* تبديل */
       t         = * (list + d );
       * (list + d )   = * (list + d + 1 );
       * (list + d + 1) = t;
     }
   }
 }
}

• لغة C#‎‎:

public class BubbleSort
{
   public static void SortBubble(int[] input)
   {
       for (var i = input.Length - 1; i >= 0; i--)
       {
           for (var j = input.Length - 1 - 1; j >= 0; j--)
           {
               if (input[j] <= input[j + 1]) continue;
               var temp = input[j + 1];
               input[j + 1] = input[j];
               input[j] = temp;
           }
       }
   }
   public static int[] Main(int[] input)
   {
       SortBubble(input);
       return input;
   }
}

• بايثون:

#!/usr/bin/python
input_list = [10,1,2,11]
for i in range(len(input_list)):
 for j in range(i):
   if int(input_list[j]) > int(input_list[j+1]):
     input_list[j],input_list[j+1] = input_list[j+1],input_list[j]
print input_list

• جافا:

public class MyBubbleSort {
   public static void bubble_srt(int array[]) {//main logic
       int n = array.length;
       int k;
       for (int m = n; m >= 0; m--) {
           for (int i = 0; i < n - 1; i++) {
               k = i + 1;
               if (array[i] > array[k]) {
                   swapNumbers(i, k, array);
               }
           }
           printNumbers(array);
       }
   }
   private static void swapNumbers(int i, int j, int[] array) {
       int temp;
       temp = array[i];
       array[i] = array[j];
       array[j] = temp;
   }
   private static void printNumbers(int[] input) {

       for (int i = 0; i < input.length; i++) {
           System.out.print(input[i] + ", ");
       }
       System.out.println("\n");
   }
   public static void main(String[] args) {
       int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
       bubble_srt(input);
   }
}

• جافاسكربت:

       function bubbleSort(a)
         {
               var swapped;
               do {
                   swapped = false;
                   for (var i=0; i < a.length-1; i++) {
                       if (a[i] > a[i+1]) {
                           var temp = a[i];
                           a[i] = a[i+1];
                           a[i+1] = temp;
                           swapped = true;
                       }
                   }
               } while (swapped);
           }

  var a = [3, 203, 34, 746, 200, 984, 198, 764, 9];
  bubbleSort(a);
  console.log(a); // [ 3, 9, 34, 198, 200, 203, 746, 764, 984 ]

الترتيب بالدمج Merge Sort

الترتيب بالدمج هي خوارزمية تعتمد مبدأ فرّق تسد، إذ تقسم المصفوفةَ المدخلةَ إلى نصفين بشكل متتابع إلى أن تصبح لدينا n مصفوفة أحادية، حيث n يمثل حجم المصفوفة المُدخلة.

بعد ذلك، تُدمج المصفوفات الجزئية المرتبة مثنى مثنى، إذ يُضاف أصغر العنصرين المتقابلين في المصفوفتين المراد دمجهما في كل خطوة. تستمر هذه العملية إلى حين الانتهاء من بناء المصفوفة المُرتّبة. يوضح المثال التالي آلية عمل خوارزمية الترتيب بالدمج:

التعقيد الزمني للخوارزمية: ‎T(n) = 2T(n/2) + Θ(n)‎.

يمكن تطبيق التكرارية أعلاه إما باستخدام طريقة الشجرة التكرارية Recurrence Tree method أو الطريقة الرئيسية (Master method)، يمكنك معرفة تفاصيل هاتين الطريقتين من هنا.

تعقيد الطريقة الرئيسية يساوي ‎Θ(nLogn)‎ في جميع الحالات الثلاث (الأسوأ والمتوسطة والفضلى)، ذلك أنّ الترتيب بالدمج يقسّم المصفوفة تعاوديًا إلى أنصاف، ويستغرق وقتًا خطيًا لدمج نصفين، حيث لدينا:

• المساحة الإضافية: ‎O(n)‎.
• نموذج الخوارزمية: فرّق تسد.
• الموضعيّة: على العموم، التطبيقات الشائعة للخوارزمية لا تكون موضعية.
• مستقرة: نعم.

هذه بعض تطبيقات خوارزمية الدمج في بعض لغات البرمجة:

• لغة Go:

package main
import "fmt"
func mergeSort(a []int) []int {
   if len(a) < 2 {
       return a
   }
   m := (len(a)) / 2
   f := mergeSort(a[:m])
   s := mergeSort(a[m:])
   return merge(f, s)
}
func merge(f []int, s []int) []int {
   var i, j int
   size := len(f) + len(s)
   a := make([]int, size, size)
   for z := 0; z < size; z++ {
       lenF := len(f)
       lenS := len(s)
       if i > lenF-1 && j <= lenS-1 {
           a[z] = s[j]
           j++
       } else if j > lenS-1 && i <= lenF-1 {
           a[z] = f[i]
           i++
       } else if f[i] < s[j] {
           a[z] = f[i]
           i++
       } else {
           a[z] = s[j]
           j++
       }
   }
   return a
}
func main() {
   a := []int{75, 12, 34, 45, 0, 123, 32, 56, 32, 99, 123, 11, 86, 33}
   fmt.Println(a)
   fmt.Println(mergeSort(a))
}

• لغة C

int merge(int arr[],int l,int m,int h)
{
 int arr1[10],arr2[10];  // مصفوفتان مؤقتتان
 hold the two arrays to be merged
 int n1,n2,i,j,k;
 n1=m-l+1;
 n2=h-m;
 for(i=0; i<n1; i++)
   arr1[i]=arr[l+i];
 for(j=0; j<n2; j++)
   arr2[j]=arr[m+j+1];
 arr1[i]=9999;  // لتحديد نهاية كل مصفوفة مؤقتة
 arr2[j]=9999;
 i=0;
 j=0;
 for(k=l; k<=h; k++) { // دمج مصفوفتين مرتبتين
   if(arr1[i]<=arr2[j])
     arr[k]=arr1[i++];
   else
     arr[k]=arr2[j++];
 }
 return 0;
}
int merge_sort(int arr[],int low,int high)
{
 int mid;
 if(low<high) {
   mid=(low+high)/2;
   // فرق تسد
   merge_sort(arr,low,mid);
   merge_sort(arr,mid+1,high);
   // Combine
   merge(arr,low,mid,high);
 }
 return 0;
}

• ‎لغةC# ‎‎

public class MergeSort
   {
       static void Merge(int[] input, int l, int m, int r)
       {
           int i, j;
           var n1 = m - l + 1;
           var n2 = r - m;
           var left = new int[n1];
           var right = new int[n2];
           for (i = 0; i < n1; i++)
           {
               left[i] = input[l + i];
           }

           for (j = 0; j < n2; j++)
           {
               right[j] = input[m + j + 1];
           }
           i = 0;
           j = 0;
           var k = l;
           while (i < n1 && j < n2)
           {
               if (left[i] <= right[j])
               {
                   input[k] = left[i];
                   i++;
               }
               else
               {
                   input[k] = right[j];
                   j++;
               }
               k++;
           }
           while (i < n1)
           {
               input[k] = left[i];
               i++;
               k++;
           }
           while (j < n2)
           {
               input[k] = right[j];
               j++;
               k++;
           }
       }
       static void SortMerge(int[] input, int l, int r)
       {
           if (l < r)
           {
               int m = l + (r - l) / 2;
               SortMerge(input, l, m);
               SortMerge(input, m + 1, r);
               Merge(input, l, m, r);
           }
       }
       public static int[] Main(int[] input)
       {
           SortMerge(input, 0, input.Length - 1);
           return input;
       }
   }

• جافا: هذا تطبيق بلغة جافا يستخدم المقاربة العامة.

public interface InPlaceSort<T extends Comparable<T>> {
void sort(final T[] elements); }
public class MergeSort < T extends Comparable < T >> implements InPlaceSort < T > {
@Override
public void sort(T[] elements) {
   T[] arr = (T[]) new Comparable[elements.length];
   sort(elements, arr, 0, elements.length - 1);
}
// نتحقق من كلا الجانبين، ثم ندمجهما
private void sort(T[] elements, T[] arr, int low, int high) {
   if (low >= high) return;
   int mid = low + (high - low) / 2;
   sort(elements, arr, low, mid);
   sort(elements, arr, mid + 1, high);
   merge(elements, arr, low, high, mid);
}
private void merge(T[] a, T[] b, int low, int high, int mid) {
   int i = low;
   int j = mid + 1;
   // b نختار أصغر عنصر منهما، ثم نضعه في 
   for (int k = low; k <= high; k++) {
       if (i <= mid && j <= high) {
           if (a[i].compareTo(a[j]) >= 0) {
               b[k] = a[j++];
           } else {
               b[k] = a[i++];
           }
       } else if (j > high && i <= mid) {
           b[k] = a[i++];
       } else if (i > mid && j <= high) {
           b[k] = a[j++];
       }
   }
   for (int n = low; n <= high; n++) {
       a[n] = b[n];
   }}}

• Java: هذا تطبيق آخر للخوارزمية بلغة Java، ولكن وفق منظور تصاعدي (من الأسفل إلى الأعلى)

public class MergeSortBU {
   private static Integer[] array = { 4, 3, 1, 8, 9, 15, 20, 2, 5, 6, 30, 70,
60,80,0,9,67,54,51,52,24,54,7 };
   public MergeSortBU() {
   }
   private static void merge(Comparable[] arrayToSort, Comparable[] aux, int lo,int mid, int hi) {
       for (int index = 0; index < arrayToSort.length; index++) {
           aux[index] = arrayToSort[index];
       }
       int i = lo;
       int j = mid + 1;
       for (int k = lo; k <= hi; k++) {
           if (i > mid)
               arrayToSort[k] = aux[j++];
           else if (j > hi)
               arrayToSort[k] = aux[i++];
           else if (isLess(aux[i], aux[j])) {
               arrayToSort[k] = aux[i++];
           } else {
               arrayToSort[k] = aux[j++];
           }
       }
   }
   public static void sort(Comparable[] arrayToSort, Comparable[] aux, int lo, int hi) {
       int N = arrayToSort.length;
       for (int sz = 1; sz < N; sz = sz + sz) {
           for (int low = 0; low < N; low = low + sz + sz) {
               System.out.println("Size:"+ sz);
               merge(arrayToSort, aux, low, low + sz -1 ,Math.min(low + sz + sz - 1, N - 1));
               print(arrayToSort);
           }
       }
   }
   public static boolean isLess(Comparable a, Comparable b) {
       return a.compareTo(b) <= 0;

   }
   private static void print(Comparable[] array)
{http://stackoverflow.com/documentation/algorithm/5732/merge-sort#
       StringBuffer buffer = new
StringBuffer();http://stackoverflow.com/documentation/algorithm/5732/merge-sort#
       for (Comparable value : array) {
           buffer.append(value);
           buffer.append(' ');
       }
       System.out.println(buffer);
   }
   public static void main(String[] args) {
       Comparable[] aux = new Comparable[array.length];
       print(array);
       MergeSortBU.sort(array, aux, 0, array.length - 1);
   }
}

• بايثون

def merge(X, Y):
   " دمج مصفوفتين مرتبتين "
   p1 = p2 = 0
   out = []
   while p1 < len(X) and p2 < len(Y):
       if X[p1] < Y[p2]:
           out.append(X[p1])
           p1 += 1
       else:
           out.append(Y[p2])
           p2 += 1
   out += X[p1:] + Y[p2:]
   return out
def mergeSort(A):
   if len(A) <= 1:
       return A
   if len(A) == 2:
       return sorted(A)
   mid = len(A) / 2
   return merge(mergeSort(A[:mid]), mergeSort(A[mid:]))
if __name__ == "__main__":
   # Generate 20 random numbers and sort them
   A = [randint(1, 100) for i in xrange(20)]
   print mergeSort(A)

الترتيب بالإدراج

الترتيب بالإدراج هي إحدى خوارزميات الترتيب البسيطة، إذ ترتّب العناصر واحدًا تلو الآخر بنفس الطريقة التي ترتّب فيها أوراق اللعب يدويًّا.

الرسم البياني التالي يوضّح آلية عمل خوارزمية الترتيب بالإدراج:

المصدر: ويكيبديا

يمكنك معرفة المزيد من التفاصيل حول آلية عمل الخوارزمية من ويكي حسوب.

هذا تطبيق لخوارزمية الترتيب بالإدراج بلغة هاسكل Haskell:

insertSort :: Ord a => [a] -> [a]
insertSort [] = []
insertSort (x:xs) = insert x (insertSort xs)
insert :: Ord a => a-> [a] -> [a]
insert n [] = [n]
insert n (x:xs) | n <= x    = (n:x:xs)
 | otherwise = x:insert n xs

الترتيب بالدلو Bucket Sort

الترتيب بالدلو هي خوارزمية ترتيب توزّع عناصر المصفوفة المراد ترتيبها على عدد من الدلاء (مصفوفات)، ثمّ تُرتّب عناصر كل دلو على حدة باستخدام خوارزمية ترتيب مختلفة، أو بتطبيق خوارزمية الترتيب بالدلو تكراريًا، يمكنك معرفة المزيد من التفاصيل عن هذه الخوارزمية من موسوعة حسوب.

هذا تطبيق لخوارزمية الترتيب بالدلو بلغة C#‎‎

public class BucketSort
{
   public static void SortBucket(ref int[] input)
   {
       int minValue = input[0];
       int maxValue = input[0];
       int k = 0;
       for (int i = input.Length - 1; i >= 1; i--)
       {
           if (input[i] > maxValue) maxValue = input[i];
           if (input[i] < minValue) minValue = input[i];
       }
       List<int>[] bucket = new List<int>[maxValue - minValue + 1];
       for (int i = bucket.Length - 1; i >= 0; i--)
       {
           bucket[i] = new List<int>();
       }
       foreach (int i in input)
       {
           bucket[i - minValue].Add(i);
       }
       foreach (List<int> b in bucket)
       {
           if (b.Count > 0)
           {
               foreach (int t in b)
               {
                   input[k] = t;
                   k++;
               }
           }
       }
   }
   public static int[] Main(int[] input)
   {
       SortBucket(ref input);
       return input;
   }
}

الترتيب السريع Quicksort

خوارزمية الترتيب السريع هي خوارزمية ترتيب تنتقي عنصرًا من عناصر المصفوفة وتجعله محورًا، ثمّ تقسّم المصفوفة المعطاة حول ذلك العنصر، بحيث تأتي جميع العناصر الأصغر من المحور قبله، وجميع العناصر الأكبر منه تأتي بعده. تُطبّق الخوارزمية تكراريًا على الأقسام حتى تُرتّب المصفوفة بالكامل، وهناك طريقتان لتقديم هذه الخوارزمية.

طريقة لوموتو Lomuto

في هذه الطريقة يُنتقى أحد العناصر ليكون محور الترتيب، وغالبًا ما يكون العنصر الأخير من المصفوفة، ويُحفظ فهرس المحور ثم تُتعقّب المواقع التي تحتوي على العناصر التي تساوي قيمة المحور أو تصغُره، ويُجرى التبديل بين موقعي العنصرين إن عُثِر على عنصر أصغر من المحور، ويُزاد فهرس المحور بواحد. فيما يلي شيفرة عامة للخوارزمية:

partition(A, low, high) is
pivot := A[high]
i := low
for j := low to high – 1 do
 if A[j] ≤ pivot then
        swap A[i] with A[j]
        i := i + 1
swap A[i] with A[high]
return i

آلية الترتيب السريع:

quicksort(A, low, high) is
if low < high then
    p := partition(A, low, high)
    quicksort(A, low, p – 1)
    quicksort(A, p + 1, high)

يوضّح المثال التالي آلية عمل خوارزمية الترتيب السريع:

طريقة هور Hoare

تستخدم طريقة هور مؤشرين يبدآن بالإشارة إلى طرفي المصفوفة المُقسّمة، ثم يتحركان نحو بعضهمًا إلى أن يحصل انقلاب، أي تصبح القيمة الصغرى في الجانب الأيسر من المحور، والكبرى في الجانب الأيمن منه؛ وعند حصول الانقلاب تبدّل الخوارزمية بين موقعي القيمتين وتعاد العملية مرةً أخرى.

عندما تلتقي الفهارس، تتوقف الخوارزمية ويُعاد الفهرس النهائي. تُعد طريقة هور أكثر فعاليةً من طريقة Lomuto، لأنّ عدد التبديلات التي تجريها أقل بثلاث مرات في المتوسط من طريقة Lomuto، كما أنّها أكثر فعاليةً في إنشاء الأقسام حتى عندما تكون جميع القيم متساوية.

quicksort(A, lo, hi) is
if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p + 1, hi)

شيفرة عامة لتقسيم المصفوفة:

partition(A, lo, hi) is
pivot := A[lo]
i := lo - 1
j := hi + 1
loop forever
 do:
        i := i + 1
 while A[i] < pivot do

 do:
        j := j - 1
 while A[j] > pivot do

 if i >= j then
 return j

    swap A[i] with A[j]

هذا تطبيق لخوارزمية الترتيب السريع بلغة بايثون:

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) / 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quicksort(left) + middle + quicksort(right)
print quicksort([3,6,8,10,1,2,1])

الخرج الناتج:

 [1 ، 1 ، 2 ، 3 ، 6 ، 8 ، 10]

وهذا تطبيق لطريقة Lomuto بلغة جافا:

public class Solution {
public static void main(String[] args) {
   Scanner sc = new Scanner(System.in);
   int n = sc.nextInt();
   int[] ar = new int[n];
   for(int i=0; i<n; i++)
     ar[i] = sc.nextInt();
    quickSort(ar, 0, ar.length-1); 
}
public static void quickSort(int[] ar, int low, int high)
{
   if(low<high)
   {
       int p = partition(ar, low, high);
       quickSort(ar, 0 , p-1);
       quickSort(ar, p+1, high);
   }   
} 
public static int partition(int[] ar, int l, int r)
{
   int pivot = ar[r];
   int i =l;
   for(int j=l; j<r; j++)
    {
       if(ar[j] <= pivot)
        {
           int t = ar[j];
           ar[j] = ar[i];
           ar[i] = t;
           i++;
       }
   }
   int t = ar[i];
   ar[i] = ar[r];
   ar[r] = t;
   return i;
}

الترتيب بالعد Counting Sort

• المساحة الإضافية: ‎O(n+k)‎
• التعقيد الزمني:
• الحالة الأسوأ: ‎O(n+k)‎.
• الحالة الأفضل: ‎O(n)‎.
• الحالة المتوسطة ‎O(n+k)‎.

الترتيب بالعد Counting sort هي خوارزمية لترتيب الكائنات وفقًا لمفاتيحها.

خطوات الخوارزمية:

1. أنشئ مصفوفة C حجمها يساوي عدد العناصر الفريدة في المصفوفة المُدخلة A.
2. املأ المصفوفة ? لكل x عنصر فريد من المصفوفة المُدخلة، تحتوي C[x]‎‎ تردّد ذلك العنصر في المصفوفة المُدخلة A.
3. حوّل C إلى مصفوفة بحيث يشير C[x]‎‎ إلى عدد القيم التي تصغُر x عبر التكرار في المصفوفة، وعيّن مجموع القيمة السابقة لكل C [x]‎‎، وكذلك جميع القيم في C التي تظهر قبله.
4. كرِّر خلفيًا على المصفوفة A مع وضع كل قيمة في مصفوفة B جديدة مرتبة في الفهرس المسجّل في C. ولكل A [x]‎‎، نعيّن قيمة B [C [A [x]]]‎‎ إلى A [x]‎‎، مع إنقاص قيمة C [A [x]]‎‎ بمقدار واحد في حال وجود قيم مكرّرة في المصفوفة الأصلية غير المرتبة.

يوضّح المثال التالي آلية عمل خوارزمية الترتيب بالعد:

وفي ما يلي مثال توضيحي للخوارزمية:

for x in input:
   count[key(x)] += 1
total = 0
for i in range(k):
   oldCount = count[i]
   count[i] = total
   total += oldCount
for x in input:
   output[count[key(x)]] = x
   count[key(x)] += 1
return output

يمكنك الاطلاع على المزيد من التفاصيل والأمثلة التوضيحية عن خوارزمية الترتيب بالعدّ من موسوعة حسوب

الترتيب بالكومة Heap Sort

• المساحة الإضافية: ‎O(1)‎.
• التعقيد الزمني:O(nlogn)‎.

الترتيب بالكومة هي خوارزمية تستند على الكومة الثنائية Binary Heap، وهي مشابهة لخوارزمية الترتيب بالتحديد Selection Sort التي تعتمد على اختيار العنصر الأكبر في المصفوفة في البداية، ثمّ تضعه في نهاية المصفوفة، ثمّ تعيد العملية على بقية العناصر.

هذا مثال توضيحي لخوارزمية الترتيب بالكومة:

function heapsort(input, count)

   heapify(a,count)
   end <- count - 1
   while end -> 0 do
   swap(a[end],a[0])
   end<-end-1
   restore(a, 0, end)
function heapify(a, count)
   start <- parent(count - 1)
   while start >= 0 do
       restore(a, start, count - 1)
       start <- start - 1

وهذا مثال على آلية عمل خوارزمية الترتيب بالكومة على المصفوفة [2,3,7,1,8,5,6]:

هذا تطبيق لخوارزمية الترتيب بالكومة بلغة C#‎‎:

public class HeapSort
{
   public static void Heapify(int[] input, int n, int i)
   {
       int largest = i;
       int l = i + 1;
       int r = i + 2;
       if (l < n && input[l] > input[largest])
           largest = l;
       if (r < n && input[r] > input[largest])
           largest = r;
       if (largest != i)
       {
           var temp = input[i];
           input[i] = input[largest];
           input[largest] = temp;
           Heapify(input, n, largest);
       }
   }
   public static void SortHeap(int[] input, int n)
   {
       for (var i = n - 1; i >= 0; i--)
       {
           Heapify(input, n, i);
       }
       for (int j = n - 1; j >= 0; j--)
       {
           var temp = input[0];
           input[0] = input[j];
           input[j] = temp;
           Heapify(input, j, 0);
       }
   }
   public static int[] Main(int[] input)
   {
       SortHeap(input, input.Length);
       return input;
   }
}

الترتيب بالتدوير Cycle Sort

الترتيب بالتدوير هي خوارزمية موضعية غير مستقرة، وتُعدّ مثاليةً من حيث عدد مرات الكتابة في المصفوفة الأصلية وعدد مرات الكتابة في الذاكرة، فكل عنصر يُكتب إمّا مرةً واحدةً إن لم يكن في موضعه الصحيح، أو لا يُكتب على الإطلاق.

يمكنك معرفة المزيد من التفاصيل والأمثلة التوضيحية عن خوارزمية الترتيب بالتدوير من موسوعة حسوب

هذا مثال توضيحي عن تطبيق على الخوارزمية:

(input)
output = 0
for cycleStart from 0 to length(array) - 2
   item = array[cycleStart]
   pos = cycleStart
   for i from cycleStart + 1 to length(array) - 1
       if array[i] < item:
           pos += 1
   if pos == cycleStart:
       continue
   while item == array[pos]:
       pos += 1
   array[pos], item = item, array[pos]
   writes += 1
   while pos != cycleStart:
       pos = cycleStart
       for i from cycleStart + 1 to length(array) - 1
           if array[i] < item:
               pos += 1
       while item == array[pos]:
           pos += 1
       array[pos], item = item, array[pos]
       writes += 1
return outout

ترتيب الفردي-الزوجي Odd-Even Sort

• المساحة الإضافية: ‎O(n)‎
• التعقيد الزمني: ‎O(n)‎

خوارزمية ترتيب الفردي-الزوجي Odd-Even Sort (أو الترتيب بالطوب Brick sort هي خوارزمية ترتيب بسيطة طُوِّرت لتُستخدم مع المعالجات المتوازية ذات التقاطعات المحلية parallel processors with local interconnection.

توازن هذه الخوارزمية بين جميع أزواج العناصر المتجاورة ذات الفهارس الفردية / الزوجية في المصفوفة، وتبدل العناصر إذا وجدت أنّ الزوج مرتّب ترتيبًا خاطئًا. تكرر الخوارزمية الخطوة نفسها، لكن هذه المرة على الأزواج ذات الفهارس الزوجية / الفردية، وتستمر في المناوبة بين النمط زوجي / فردي وفردي / زوجي إلى أن تُرتّب المصفوفة.

هذا مثال توضيحي لخوارزمية الطوب Brick:

if n>2 then
   1. apply odd-even merge(n/2) recursively to the even subsequence a0, a2, ..., an-2 and to the
odd subsequence a1, a3, , ..., an-1
   2. comparison [i : i+1] for all i element {1, 3, 5, 7, ..., n-3}
else
   comparison [0 : 1]

هذا رسم توضيحي لآلية عمل خوارزمية الترتيب فردي/زوجي على مجموعة عشوائية:

المصدر: ويكيبيديا

وهذا مثال توضيحي على الخوارزمية:

وفيما يلي تطبيق بلغة C#‎‎ لخوارزمية الترتيب بقوالب الطوب:

public class OddEvenSort
{
   private static void SortOddEven(int[] input, int n)
   {
       var sort = false;
       while (!sort)
       {
           sort = true;
           for (var i = 1; i < n - 1; i += 2)
           {
               if (input[i] <= input[i + 1]) continue;
               var temp = input[i];
               input[i] = input[i + 1];
               input[i + 1] = temp;
               sort = false;
           }
           for (var i = 0; i < n - 1; i += 2)
           {
               if (input[i] <= input[i + 1]) continue;
               var temp = input[i];
               input[i] = input[i + 1];
               input[i + 1] = temp;
               sort = false;
           }
       }
   }
   public static int[] Main(int[] input)
   {
       SortOddEven(input, input.Length);
       return input;
   }
}

الترتيب بالتحديد Selection Sort

• المساحة الإضافية: ‎O(n)‎
• التعقيد الزمني: ‎O(n^2)‎

الترتيب بالتحديد هي خوارزمية موضعية لترتيب المصفوفات، تعقيدها الزمني يساوي O (n2)‎‎، ما يجعلها غير فعالة مع المصفوفات الكبيرة، وعادةً ما يكون أداؤها أسوأ من خوارزميات الإدراج المماثلة. بالمقابل، تتميّز خوارزمية الترتيب بالتحديد بالبساطة وقد تتفوّق أداءً على بعض الخوارزميات الأعقد في بعض الحالات، خاصّةً عندما تكون الذاكرة الإضافية محدودة.

تقسّم الخوارزمية المصفوفة إلى قسمين هما مصفوفة تضم العناصر المرتبة فعليًا، والتي تُبنى من اليسار إلى اليمين من مقدمة المصفوفة (اليسرى)؛ فيما تضم المصفوفة الأخرى العناصر المتبقية التي تنتظر أن تُرتّب، والتي تشغل بقية المصفوفة.

وتكون المصفوفة المرتّبة فارغةً في البداية، بينما تحتوى المصفوفة غير المرتّبة كل عناصر المصفوفة المُدخلة. تبحث الخوارزمية عن أصغر عنصر (أو أكبر عنصر، بحسب غرض الترتيب) في المصفوفة غير المرتّبة وتبدّله بالعنصر غير المرتّب الموجود في أقصى اليسار (أي تضعه في المكان الصحيح)، ثمّ تنقل حدود المصفوفة الفرعية عنصرًا واحدًا إلى اليمين .

هذا مثال توضيحي للخوارزمية:

function select(list[1..n], k)
for i from 1 to k
    minIndex = i
    minValue = list[i]
    for j from i+1 to n
        if list[j] < minValue
            minIndex = j
            minValue = list[j]
    swap list[i] and list[minIndex]
return list[k]

وهذا تمثيل بصري للخوارزمية:

وهذا مثال على خوارزمية الترتيب بالتحديد:

فيما يلي تطبيق على لخوارزمية بلغة C #‎‎:

public class SelectionSort
{
   private static void SortSelection(int[] input, int n)
   {
       for (int i = 0; i < n - 1; i++)
       {
           var minId = i;
           int j;
           for (j = i + 1; j < n; j++)
           {
               if (input[j] < input[minId]) minId = j;
           }
           var temp = input[minId];
           input[minId] = input[i];
           input[i] = temp;
       }
   }
   public static int[] Main(int[] input)
   {
       SortSelection(input, input.Length);
       return input;
   }
}

وهذا تطبيق على الخوارزمية بلغة إكسير Elixir:

defmodule Selection do
 def sort(list) when is_list(list) do
   do_selection(list, [])
 end
 def do_selection([head|[]], acc) do
   acc ++ [head]
 end
 def do_selection(list, acc) do
   min = min(list)
   do_selection(:lists.delete(min, list), acc ++ [min])
 end
 defp min([first|[second|[]]]) do
   smaller(first, second)
 end
 defp min([first|[second|tail]]) do
   min([smaller(first, second)|tail])
 end
 defp smaller(e1, e2) do
   if e1 <= e2 do
     e1
   else
     e2
   end
 end
end
Selection.sort([100,4,10,6,9,3])
|> IO.inspect

ترجمة -بتصرّف- للفصول من 28 إلى 38 من الكتاب Algorithms Notes for Professionals.

اقرأ أيضًا

• المقال السابق: أمثلة عن أنواع الخوارزميات
• خوارزميات تحليل المسارات في الأشجار
• خوارزمية ديكسترا Dijkstra’s Algorithm
• الخوارزميات الشرهة Greedy Algorithms