علوم الحاسوب — خوارزميات الترتيب: الدمج والترتيب السريع

خوارزميات الترتيب: الدمج والترتيب السريع

تعتبر خوارزميات الترتيب (Sorting Algorithms) من المواضيع الاساسية في علوم الحاسوب. سنتناول في هذا الدرس الجامعي اثنتين من اهم خوارزميات الترتيب المتقدمة: ترتيب الدمج (Merge Sort) والترتيب السريع (Quick Sort).

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

ترتيب الدمج هو خوارزمية ترتيب تعتمد على مبدأ “فرق تسد” (Divide and Conquer). تقوم الخوارزمية بتقسيم المصفوفة إلى نصفين، ترتيب كل نصف بشكل منفصل، ثم دمج النصفين المرتبين.

خطوات الخوارزمية:
1. تقسيم المصفوفة إلى نصفين متساويين تقريبا
2. استدعاء الخوارزمية بشكل تكراري لكل نصف
3. دمج النصفين المرتبين للحصول على مصفوفة مرتبة بالكامل

على سبيل المثال، لترتيب المصفوفة [38, 27, 43, 3, 9, 82, 10]:
نقسمها إلى [38, 27, 43, 3] و [9, 82, 10]، ونستمر في التقسيم حتى نحصل على مصفوفات احادية العنصر، ثم ندمجها بالترتيب.

تحليل التعقيد لترتيب الدمج

تعقيد ترتيب الدمج هو O(n log n) في جميع الحالات (الافضل والمتوسط والاسوا). يحتاج إلى ذاكرة اضافية O(n).

الترتيب السريع (Quick Sort)

الترتيب السريع هو ايضا خوارزمية تعتمد على “فرق تسد”، لكنها تختلف في طريقة التقسيم. تختار الخوارزمية عنصرا يسمى “المحور” (Pivot)، وتعيد ترتيب المصفوفة بحيث تكون العناصر الاصغر من المحور على يساره والاكبر على يمينه.

متوسط التعقيد: O(n log n)
اسوأ حالة: O(n^2) وتحدث عندما يكون المحور هو اصغر او اكبر عنصر دائما

مقارنة بين الخوارزميتين

ترتيب الدمج مستقر (Stable) ويضمن O(n log n) دائما، لكنه يحتاج ذاكرة اضافية. الترتيب السريع غير مستقر ولكنه اسرع في المتوسط ويحتاج ذاكرة اقل (O(log n) فقط). لمزيد من المعلومات، راجع درس الخوارزميات المتقدمة: المصفوفات والدوال ودرس هياكل البيانات المتقدمة.