Insertion Sort (الترتيب بالإدراج)
آلية العمل
تشبه ترتيب أوراق اللعب في يدك.
نبدأ بعنصر واحد (مرتب افتراضياً)، ثم نأخذ العنصر التالي وندخله (Insert) في مكانه الصحيح بين العناصر السابقة.
tmp = a[p];
for (j = p; j > 0 && tmp < a[j-1]; j--)
a[j] = a[j-1];
a[j] = tmp;
}
Complexity
- Worst Case: $O(N^2)$ (عكسي الترتيب).
- Best Case: $O(N)$ (مرتبة مسبقاً).
- ميزة: ممتاز للمصفوفات الصغيرة جداً.
Shellsort (ترتيب شيل)
الحل لمشكلة $O(N^2)$
Insertion Sort بطيء لأنه يحرك العناصر خطوة واحدة فقط في كل مرة.
Shellsort يقارن عناصر متباعدة بمسافة (Gap) كبيرة، ثم يقلل المسافة تدريجياً.
أداء الخوارزمية يعتمد كلياً على اختيار الفجوات.
• Shell's ($N/2, N/4...$): سيء، قد يصل لـ $O(N^2)$.
• Hibbard's ($2^k - 1$): أفضل، يضمن $O(N^{3/2})$.
Compare gap elements first
Heapsort (ترتيب الكومة)
الاستراتيجية الذكية
- حول المصفوفة إلى Max-Heap (الأب أكبر من الأبناء).
- احذف أكبر عنصر (الجذر) وضعه في آخر خانة في المصفوفة (مكان العنصر المحذوف منطقياً).
- قلل حجم الـ Heap بواحد، وأعد الترتيب (Percolate Down).
- كرر حتى تنتهي العناصر.
$O(N \log N)$
Build Heap: $O(N)$
Delete N times: $N \times O(\log N)$
Min-Heap vs Max-Heap for Sorting
لترتيب المصفوفة تصاعدياً (Ascending)، هل نستخدم Min-Heap أم Max-Heap؟
الجواب: Max-Heap.
السبب: نحتاج لسحب أكبر عنصر ووضعه في نهاية المصفوفة الفارغة تدريجياً.
Insertion Sort Efficiency
Insertion Sort هو الأفضل في حالة واحدة: عندما تكون البيانات شبه مرتبة (Almost Sorted). في هذه الحالة يقترب أداؤه من $O(N)$.