شرح خوارزمية الترتيب بالدمج Merge Sort
خوارزمية الترتيب بالدمج Merge Sort هى طريقة قوية، متعددة الإستخدام، مبنية على المقارنة. طريقة قوية؟ نعم قوية ﻷنها تأخذ وقت قليل مقارنةً بباقى أنواع خوارزميات الترتيب وفى نفس الوقت نتائجها مُستقرة.
متعددة الإستخدام؟ تعدد الإستخدام يعنى أن هذه الخوارزمية تستطيع ترتيب أى نوع من البيانات الرقمية التى يُمكن مقارنتها. مبنية على المقارنة؟ نعم، فكرة خوارزمية الترتيب merge sort تعتمد على المقارنة لكى تحدد القيمة الأكبر والقيمة الأصغر. وإليك الشرح بالخطوات.
خطوات عمل خوارزمية الترتيب Merge Sort 🔗
- تقسيم المصفوفة (array) إلى مصفوفتين
- تقسيم كل مصفوفة إلى مصفوفتين، حتى الوصول إلى مصفوفات بها عنصر واحد فقط
- دمج كل مصفوفة مع المجاورة لها بالترتيب بناءاً على المقارنة (merge arrays)
- إنشاء مصفوفة جديدة من كل مصفوفتين سابقتين بناءاً على مقارنة أول عنصر فى مصفوفة بأول عنصر فى المصفوفة الأخرى وهكذا حتى الحصول على مصفوفة مرتبه من مصفوفتين مرتبتين
- إنشاء مصفوفة جديدة من كل مصفوفتين سابقتين حسب الترتيب. يتم ذلك بمقارنة العنصر الأول من كلا المصفوفتين وأخذ الأصغر، ثم المقارنة من جديد وأخذ الأصغر،.. وهكذا حتى الوصول إلى مرحلة تكون فيها مصفوفة واحدة مُرتبة!
تطبيق خوارزمية الترتيب بالدمج فى لغة جو 🔗
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")
}
مصدر كود خوارزمية الترتيب بالدمج فى لغة جو : merge sort | 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);
}
}
مصدر كود خوارزمية الترتيب بالدمج فى لغة جافا : merge sort | 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}))
مصدر كود خوارزمية الترتيب بالدمج فى لغة بايثون : merge sort | Github .
إن كان لديك أى استفسار، أكتبه فى تعليق وسأقوم بالرد عليك إن شاء الله. أما إن أردت الوصول لنا بسرعة أكتب على جوجل استفسارك وبعده كلمة “موقع أبانوب” مثل “خوارزميات الترتيب موقع ابانوب”.
![waffarx cash back](/img/waffarx-banner.png)