مرتب‌سازی سریع (Quick Sort)
مرتب‌سازی سریع: انتخاب pivot، پارتیشن، میانگین O(n log n) با حافظه کم؛ محبوب‌ترین الگوریتم عملی
مرتب‌سازی سریع چیست؟
Quick Sort محبوب‌ترین الگوریتم مرتب‌سازی عملی؛ مبتنی بر تقسیم و حل اما با ایده متفاوت: انتخاب یک پیوت (Pivot) و پارتیشن‌بندی لیست حول آن.
الگوریتم
- یک عنصر را به‌عنوان پیوت انتخاب کن
- پارتیشن: کوچک‌ترها به چپ پیوت، بزرگ‌ترها به راست
- پیوت حالا در جای نهایی است!
- بازگشتی روی دو بخش چپ و راست
پارتیشن Lomuto — شهود
پیوت = آخرین عنصر. اشاره‌گر i مرز «کوچک‌ترها» را نگه می‌دارد؛ هر عنصر کوچک‌تر از پیوت، به بخش چپ می‌رود. در پایان، پیوت با موقعیت i+1 جابه‌جا می‌شود.
مثال گام‌به‌گام
[10, 80, 30, 90, 40, 50, 70] پیوت=70
پارتیشن: [10, 30, 40, 50] 70 [80, 90]
↑ جای نهایی پیوت!
بازگشت روی چپ: [10, 30, 40, 50]
بازگشت روی راست: [80, 90]
نتیجه: [10, 30, 40, 50, 70, 80, 90] ✓پیچیدگی
| حالت | پیچیدگی | سناریو |
|---|---|---|
| بهترین/میانگین | O(n log n) ✓ | پیوت میانه‌مانند |
| بدترین | O(n²) ✗ | پیوت همیشه کوچک‌ترین/بزرگ‌ترین (داده مرتب!) |
| حافظه | O(log n) | پشته بازگشت |
چرا با وجود بدترین O(n²) محبوب‌ترین است؟
- در عمل، میانگینش از Merge سریع‌تر است (ثابت‌های کوچک‌تر، cache-friendly)
- درجا مرتب می‌کند (حافظه O(log n) در برابر O(n) ادغامی)
- بدترین حالت با پیوت تصادفی یا میانه‌سه‌تایی عملاً نادر می‌شود
انتخاب پیوت — حیاتی!
- اولین/آخرین: ساده اما روی داده مرتب فاجعه O(n²)
- تصادفی: بدترین حالت را عملاً حذف می‌کند ✓
- میانه‌سه‌تایی: میانه‌ی {اول، وسط، آخر} — تعادل عملکرد و سادگی ✓
نکته: sort و sorted پایتون از TimSort استفاده می‌کنند (ترکیب Merge + Insertion)؛ اما Quick Sort پایه بسیاری از کتابخانه‌های دیگر مثل C است (qsort).
جمع‌بندی
- پیوت + پارتیشن: پیوت در جای نهایی، دو طرف بازگشتی
- میانگین O(n log n)، بدترین O(n²) (با پیوت تصادفی نادر)
- درجا و cache-friendly — سریع‌ترین در عمل
- کیفیت پیوت = کیفیت الگوریتم
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.