الخوارزميات المتقدمة: خوارزميات الترتيب السريع والدمج — الثالثة ثانوي

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

خوارزميات الترتيب المتقدمة أسرع من الخوارزميات البسيطة (Bubble Sort) للقوائم الكبيرة.

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

أسلوب divide & conquer: تقسيم القائمة لنصفين، ترتيب كل نصف، دمج النصفين المرتبين. تعقيد: O(n log n) في جميع الحالات. مستقر (يحافظ على ترتيب العناصر المتساوية). يستخدم ذاكرة إضافية.

2. ترتيب سريع (Quick Sort)

اختيار عنصر محور (Pivot). تقسيم القائمة: عناصر أقل من المحور، المحور، عناصر أكبر. ترتيب كل قسم. تعقيد: O(n log n) معدل، O(n²) أسوأ حالة. لا يحتاج ذاكرة إضافية (in-place). الأكثر استخداما.

3. ترتيب بالإدراج (Insertion Sort)

بناء القائمة المرتبة عنصرا عنصرا. تعقيد: O(n²) معدل، O(n) لقائمة مرتبة تقريبا. جيد للقوائم الصغيرة جدا.

4. مقارنة

Merge Sort: n log n، مستقر، ذاكرة O(n). Quick Sort: n log n معدل، غير مستقر، in-place. Insertion Sort: n²، مستقر، جيد للقوائم الصغيرة.

تمارين

1. رتب [8,3,5,1,9,2] باستخدام Quick Sort.