مرتب‌سازی شمارشی و مبنایی
مرتب‌سازی بدون مقایسه: Counting Sort و Radix Sort با پیچیدگی خطی + جدول مقایسه کامل همه الگوریتم‌های مرتب‌سازی
فراتر از مقایسه
همه الگوریتم‌های قبلی بر مقایسه جفت عناصر تکیه داشتند و اثبات شده که نمی‌توان از O(n log n) بهتر شد. اما اگر از ساختار خاص داده استفاده کنیم (مثل اعداد صحیح در بازه محدود)، می‌توان خطی O(n) مرتب کرد!
Counting Sort — مرتب‌سازی شمارشی
ایده: به‌جای مقایسه، تعداد تکرار هر مقدار را بشمار:
- بازه مقادیر را پیدا کن (مثلاً ۰ تا ۹)
- آرایه شمارش بساز: چند بار هر مقدار آمده؟
- از آرایه شمارش، خروجی مرتب بساز
ورودی: [4, 2, 2, 8, 3, 3, 1]
شمارش: [1, 2, 2, 0, 1, 0, 0, 0, 1] (اندیس=مقدار)
خروجی: [1, 2, 2, 3, 3, 4, 8] ✓پیچیدگی: O(n + k) که k بازه مقادیر است. اگر k کوچک باشد (مثل نمره ۰ تا ۲۰)، فوق‌العاده سریع!
محدودیت: فقط برای اعداد صحیح (یا قابل نگاشت به عدد) و وقتی k معقول باشد.
Radix Sort — مرتب‌سازی مبنایی
ایده: مرتب‌سازی پایدار رقم به رقم از کم‌ارزش‌ترین (LSD):
- ارقام یکان: با Counting Sort مرتب کن
- ارقام دهگان: دوباره (پایدار!)
- ... تا بالاترین رقم
[170, 45, 75, 90, 802, 24, 2, 66]
یکان: [170, 90, 802, 2, 24, 45, 75, 66]
دهگان: [802, 2, 24, 45, 66, 170, 75, 90]
صدگان: [2, 24, 45, 66, 75, 90, 170, 802] ✓پیچیدگی: O(d × (n + k)) که d تعداد ارقام است. برای اعداد با ارقام کم، عملاً خطی!
جدول مقایسه همه الگوریتم‌های مرتب‌سازی
| الگوریتم | میانگین | بدترین | حافظه | پایدار | کاربرد |
|---|---|---|---|---|---|
| Bubble | O(n²) | O(n²) | O(1) | ✓ | آموزشی |
| Selection | O(n²) | O(n²) | O(1) | ✗ | نوشتن گران |
| Insertion | O(n²) | O(n²) | O(1) | ✓ | کوچک/تقریباً مرتب |
| Merge | O(n log n) | O(n log n) | O(n) | ✓ | تضمینی، دیسک |
| Quick | O(n log n) | O(n²) | O(log n) | ✗ | عمومی، سریع‌ترین عملی |
| Counting | O(n+k) | O(n+k) | O(k) | ✓ | صحیح با بازه کم |
| Radix | O(d(n+k)) | O(d(n+k)) | O(n+k) | ✓ | اعداد/رشته با ارقام کم |
کدام را انتخاب کنم؟
- داده عمومی، عملکرد عملی ← Quick Sort (یا sort آماده پایتون!)
- نیاز به پایداری یا تضمین ← Merge / TimSort
- تقریباً مرتب یا کوچک ← Insertion
- اعداد صحیح با بازه کم ← Counting
- اعداد زیاد با ارقام کم ← Radix
نکته نهایی: در پروژه واقعی، تقریباً همیشه از sort آماده زبان استفاده کنید (TimSort در پایتون) — بهینه‌شده و تست‌شده. پیاده‌سازی دستی برای یادگیری و مصاحبه است!
جمع‌بندی
- بدون مقایسه می‌توان خطی مرتب کرد: Counting و Radix
- Counting: O(n+k) برای صحیح با بازه کم
- Radix: رقم به رقم پایدار — O(d(n+k))
- جدول انتخاب: Quick عملی، Merge تضمینی، Insertion برای تقریباً مرتب
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.