لوحة المتصدرين

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

سنتحدث في هذه المقالة عن بعض المفاهيم العامة المتعلقة بخوارزميات الترتيب، ثم نستعرض 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 table { width: 100%; } thead { vertical-align: middle; text-align: center; } td, th { border: 1px solid #dddddd; text-align: right; padding: 8px; text-align: inherit; } tr:nth-child(even) { background-color: #dddddd; } المعامِل الوصف ترتيب مستقر نعم ترتيب موضعي نعم أفضل حالة تعقيد (O(n أسوء حالة تعقيد (O(n^2 أوسط حالة تعقيد (O(n^2 تعقيد المساحة (O(1 توازن خوارزمية الفقاعات ‎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 هي خوارزمية لترتيب الكائنات وفقًا لمفاتيحها. خطوات الخوارزمية: أنشئ مصفوفة C حجمها يساوي عدد العناصر الفريدة في المصفوفة المُدخلة A. املأ المصفوفة 😄 لكل x عنصر فريد من المصفوفة المُدخلة، تحتوي C[x]‎‎ تردّد ذلك العنصر في المصفوفة المُدخلة A. حوّل C إلى مصفوفة بحيث يشير C[x]‎‎ إلى عدد القيم التي تصغُر x عبر التكرار في المصفوفة، وعيّن مجموع القيمة السابقة لكل C [x]‎‎، وكذلك جميع القيم في C التي تظهر قبله. كرِّر خلفيًا على المصفوفة 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

يُستخدم برنامج وورد لتحرير أنواع كثيرة من النصوص وحفظها بشكل مستندات. وفي بعض الأحيان تكون هذه المستندات سريّة أو تحتوي على معلومات حساسة من ناحية الخصوصية ونرغب في حمايتها بطريقة أو بأخرى. ولهذا الغرض يوفّر وورد عدد من مستويات الحماية للمستندات مثل الحماية بكلمة مرور، تقييد عملية التحرير والتنسيق، أو غيرها. في هذا الدرس سنغطي كيفية حماية المستندات بجعلها للقراءة فقط، تقييد عمليات التحرير والتنسيق من قبل الآخرين، تشفير المستند بكلمة مرور، وحذف البيانات الوصفية metadata في المستند. كيفية جعل المستند للقراءة فقط Read Only يمكنك استخدام هذا الخيار إذا كنت ترغب في مشاركة المستند مع الآخرين وتريد تنبيههم إلى أنّ النسخة الحالية هي للقراءة فقط ولا تريد منهم تعديلها. لتحويل المستند إلى النسخة نهائية، أي نسخة القراءة فقط، اذهب إلى ملف File> معلومات Info> حماية المستند Protect Document> وضع علامة كنهائي Mark as Final: انقر على موافق OK> OK في مربعي الحوار التاليين: سيتم تعليم المستند كـ "نهائي"، أي أنّ تحرير وتنقيح المستند مكتمل وأنّ هذه هي النسخة النهائية منه. عند فتح المستند في المرّة القادمة، سواء من قبلك أو من قبل المستخدمين الآخرين، ستظهر أيقونة في شريط الحالة بالإضافة إلى شريط أصفر الجزء العلوي من الصفحة يشيران إلى أنّ المستند بنسخته النهائية: بالرغم من أنّك قمت بتحويل المستند إلى نسخة القراءة فقط، إلّا أنّ المستخدمين الآخرين يمكنهم تحرير المستند وتنسيقه عند تجاهلهم للرسالة في الشريط العلوي والنقر على زر تحرير على أيّة حال Edit Anyway. فإذا رغبت في تقييد المستخدمين أكثر استخدم الخيار التالي. تقييد التنسيق والتحرير يتيح لك هذا الخيار إمكانية التحكم في نوع التغييرات التي تسمح بإجرائها على المستند من قبل المستخدمين الذي ستشاركه معهم. وهذه الطريقة أكثر تقييدًا من الطريقة السابقة. لتخصيص خيارات تقييد التنسيق والتحرير اذهب إلى ملف File> معلومات Info> حماية المستند Protect Document> تقييد التحرير Restrict Editing: سيُفتح جزء Restrict Editing الذي يحتوي على خيارات تقييد التنسيق وتقييد التحرير كل منهما بشكل منفصل. لمنع المستخدمين الآخرين من إجراء التعديلات على تنسيق النص، قم بتأشير الخيار Limit formatting to a selection of styles ثم انقر على Settings: من مربّع الحوار Formatting Restrictions، أبقِ على الخيار Limit formatting to a selection of styles مؤشرًا ثم انتقل إلى قسم Checked styles are currently allowed. من هذا القسم يمكنك إلغاء تأشير الأنماط التي لا تريد السماح باستخدامها في المستند، وبذلك تحدّ من قدرة المستخدمين الآخرين على تعديل الأنماط أو تعديل تنسيقات النصوص بشكل مباشر بواسطة خيارات التنسيق في تبويب الصفحة الرئيسية Home: إذا كنت تريد تقييد التنسيق فقط اكتف بهذه الخطوة ثم انقر على زر Yes, Start Enforcing Protection. أمّا إذا رغبت في تقييد التحرير أيضًا فقم بتأشير الخيار Allow only this type of editing in the document: من القائمة المنسدلة حدّد نوع الترخيص الذي تريد منحه للمستخدمين: Tracked Changes: للسماح بالتغييرات بشرط تعقّبها. Comments: لمنع التغييرات لكن السماح بإضافة تعليقات على المستند. Filling in forms: للسماح بتعبئة النماذج التي تم إنشاؤها في المستند لكن منع أيّة تعديلات أخرى. No Changes (Read Only): لجعل المستند للقراءة فقط ومنع إجراء أي تعديل عليه. بإمكانك استثناء بعض المستخدمين من التقييد والسماح لهم بتحرير المستند بحرية وذلك بالنقر على More Users: بإمكانك استثناء مستخدم آخر على الجهاز الحالي أو على جهاز ثانٍ تابع لنفس النطاق domain، أو أي مستخدم آخر (بإدخال عنوان بريده الإلكتروني) مع الفصل بين أسماء المستخدمين بفاصلة منقوطة: ستتم إضافة عناوين المستخدمين التي قمت بإدخالها في قسم Individuals، قم بتأشير المستخدم الذي تريد استثناءه، أو تجاهل هذه الخطوة وانتقل إلى الخطوة التالية إذا كنت ترغب في تعميم التقييد. الخطوة الأخيرة هي تطبيق الإعدادات والبدء بفرض الحماية بالنقر على زر Yes, Start Enforcing Protection: سيظهر لك مربّع حوار جديد يمكنك من خلال إدخال كلمة مرور لتفعيل الحماية (أو استخدامها لاحقًا إذا رغبت في إلغاء الحماية). أدخل كلمة المرور مرّتين ثم انقر على OK: سيتم تطبيق التقييد على المستخدمين حسب الإعدادات التي اخترتها. ويمكنك دائمًا إلغاء تقييد التنسيق والتحرير للمستند بالذهاب إلى File> Info> Protect Document> Restrict Editing> Stop Protection: ثم قم بإدخال كلمة المرور نفسها التي أدخلتها عند تفعيل الحماية. تشفير المستند (حمايته بكلمة مرور) التشفير هو أقصى مستويات الأمان التي يمكنك تطبيقها على المستند. ويتم بوضع كلمة مرور للمستند بحيث لا يمكن فتحه وقراءته دون إدخالها. ويمكنك استخدام هذا الخيار إذا كان المستند مهم جدًا أو سرّي ولا تريد من المستخدمين الآخرين فتحه وقراءته. لتشفير المستند اذهب إلى ملف File> معلومات Info> حماية المستند Protect Document> التشفير باستخدام كلمة مرور Encrypt with Password: قم بإدخال كلمة المرور مرّتين، وانتبه إلى أنّه لا يمكن استعادتها مجددًا في حال نسيانها، لذا يُفضّل تدوينها في مكان آمن: في المرّة القادمة التي يحاول فيها أحدهم فتح المستند سيُطلب منه إدخال كلمة المرور أولًا لكي يتمكّن من قراءته: حذف البيانات الوصفية Metadata حذف البيانات الوصفية هو أيضًا من الخيارات المفيدة لحماية معلوماتك الخاصّة عند مشاركة المستندات مع الآخرين. وتشتمل هذه البيانات على المعلومات المخفية في المستند أو معلوماتك الشخصية التي يمكن أن تكون مخزونة في المستند نفسه مثل التعليقات والملفات المضمّنة أو في خصائص المستند مثل اسم الكاتب، اسم آخر مستخدم قام بتعديل المستند، أو غيرها. لحذف هذا النوع من البيانات اذهب إلى ملف File> معلومات Info> البحث عن مشاكل Check for Issues> فحص المستند Inspect Document: بعد ذلك قم بتأشير نوع البيانات التي تريد البحث عنها وانقر على زر Inspect: بعد انتهاء الفحص ستظهر أيقونة علامة تعجّب حمراء أمام البيانات التي تم العثور عليها، ويمكنك إزالة البيانات التي لا تريد الكشف عنها عند مشاركة المستند بالنقر على زر Remove All: خاتمة استعرضنا في هذا الدرس طرق حماية مستندات وورد بعدّة مستويات. ويمكنك اختيار الطريقة المناسبة لمستنداتك التي تريد مشاركتها حسب درجة خصوصية أو سرّية المعلومات التي تحتويها. إذا كان لديك أي سؤال حول حماية مستندات وورد تفضّل بطرحه في التعليقات، وسنكون سعداء بمساعدتك