مرتب‌سازی درجی (Insertion Sort)
مرتب‌سازی درجی: مثل مرتب‌کردن ورق در دست؛ عالی برای داده تقریباً مرتب و پایه الگوریتم TimSort پایتون
مرتب‌سازی درجی چیست؟
Insertion Sort مثل مرتب‌کردن ورق‌های بازی در دست: هر کارت جدید را بردارید و در جای درستش بین کارت‌های مرتب قبلی درج کنید.
الگوریتم
- عنصر اول خودش مرتب است (زیرلیست با طول ۱)
- عنصر بعدی (کلید) را بردار
- عناصر مرتب قبلی که از کلید بزرگ‌ترند را یک خانه به راست بکش
- کلید را در جای خالی‌شده بگذار
- تکرار تا آخر لیست
مثال گام‌به‌گام
[12, 11, 13, 5, 6]
کلید=11: 12>11، بکش -> [11, 12 | 13, 5, 6]
کلید=13: 12<13، اوکی -> [11, 12, 13 | 5, 6]
کلید=5: همه بکش -> [5, 11, 12, 13 | 6]
کلید=6: 13,12,11 بکش -> [5, 6, 11, 12, 13] ✓پیچیدگی
| حالت | پیچیدگی | توضیح |
|---|---|---|
| بدترین (معکوس) | O(n²) | هر کلید تا اول می‌رود |
| میانگین | O(n²) | — |
| بهترین (مرتب) | O(n) ✓ | هر کلید فقط یک مقایسه |
| تقریباً مرتب | ≈ O(n) ✓✓ | قهرمان این حالت! |
قهرمان داده تقریباً مرتب
اگر هر عنصر فقط چند خانه از جای درستش دور باشد، Insertion Sort تقریباً خطی عمل می‌کند! به همین دلیل:
- TimSort (الگوریتم sort پایتون و جاوا) از Insertion Sort برای قطعات کوچک/تقریباً مرتب استفاده می‌کند
- در الگوریتم‌های پیشرفته (Quick/Merge) برای زیرآرایه‌های کوچک (زیر ~۱۰) به Insertion سوییچ می‌کنند
مزایا و معایب
- ✓ ساده و کارآمد برای داده کوچک
- ✓ عالی برای داده تقریباً مرتب — O(n)
- ✓ پایدار (Stable)
- ✓ درجا: O(1) حافظه
- ✓ آنلاین: می‌تواند داده در حال رسیدن را مرتب نگه دارد!
- ✗ کند برای داده بزرگ نامرتب: O(n²)
نکته: اگر داده‌تان «تقریباً مرتب» است (مثلاً لیست کاربران که فقط چند تای جدید جابه‌جا شده)، Insertion Sort می‌تواند از Quick Sort هم سریع‌تر باشد!
جمع‌بندی
- درج هر عنصر در جای درست بخش مرتب — مثل ورق در دست
- بهترین/تقریباً مرتب: O(n) — قهرمان این سناریو
- پایدار، درجا، آنلاین
- پایه TimSort پایتون و الگوریتم‌های ترکیبی
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.