الإعلام الآلي — الخوارزميات: خوارزميات الترتيب السريع والدمج — Quick Sort و Merge Sort — الثالثة ثانوي (شعب علمية) — بكالوريا — المنهاج الجزائري

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

خوارزميات الترتيب المتقدمة تهدف إلى ترتيب البيانات بكفاءة عالية. خوارزمية الترتيب السريع (Quick Sort) وترتيب الدمج (Merge Sort) من أشهر خوارزميات الترتيب بتعقيد O(n log n) في أفضل الأحوال.

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

تقسيم المصفوفة حول محور (Pivot). العناصر الأصغر من المحور إلى اليسار والأكبر إلى اليمين. تطبيق الخوارزمية على كل جزء بشكل متكرر (Recursion). متوسط التعقيد: O(n log n). أسوأ حالة: O(n²) عندما يكون المحور هو أصغر أو أكبر عنصر.

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

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

تمارين

1. طبق Quick Sort على المصفوفة [7,2,1,6,8,5,3,4] مع محور العنصر الأخير.
2. طبق Merge Sort على المصفوفة [38,27,43,3,9,82,10].
3. قارن بين Quick Sort و Merge Sort من حيث السرعة واستخدام الذاكرة.

للمزيد: الهندسة الفضائية و الدوال الأسية.