مرتب‌سازی مبنایی
عددها را رقم‌به‌رقم، از یکان شروع کرده، با یک مرتب‌سازی شمارشی پایدار مرتب می‌کند؛ بعد از آخرین رقم کل آرایه مرتب است.
مرتب‌سازی مبنایی عددها را رقم‌به‌رقم مرتب می‌کند، از کم‌ارزش‌ترین رقم (یکان) شروع کرده. هر گذر یک مرتب‌سازی شمارشی روی همان رقم است (فقط ده مقدار ممکن: ۰ تا ۹).
ادامه‌ی توضیح ↓- زمان:
O(d·(n + 10)) for d digits - حافظه:
O(n) - CLRS، بخش ۸.۳
- هوروویتز–ساهنی، فصل ۷
هفت عدد سه‌رقمی: سه گذر برای یکان، دهگان و صدگان.
def radix_sort(a):exp = 1while max(a) // exp > 0:a = sort_by_digit(a, exp)exp = exp * 10return adef sort_by_digit(a, exp):count = [0] * 10for x in a:d = (x // exp) % 10count[d] = count[d] + 1for d in range(1, 10):count[d] = count[d] + count[d - 1]out = [0] * len(a)for j in range(len(a) - 1, -1, -1):d = (a[j] // exp) % 10count[d] = count[d] - 1out[count[d]] = a[j]return out
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
Call stack
- radix_sort()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- place
- ورودی فعلی (n=7)
نمایش به شکل جدول
| n | place |
|---|---|
| 4 | 12 |
| 6 | 18 |
| 8 | 24 |
| 10 | 30 |
| 12 | 36 |
| 14 | 42 |
| 16 | 48 |
توضیح
ایده
مرتب‌سازی مبنایی عددها را رقم‌به‌رقم مرتب می‌کند، از کم‌ارزش‌ترین رقم (یکان) شروع کرده. هر گذر یک مرتب‌سازی شمارشی روی همان رقم است (فقط ده مقدار ممکن: ۰ تا ۹).
چرا از یکان؟
کلید کار پایداری هر گذر است. بعد از گذر یکان، عددها بر اساس یکان مرتب‌اند. گذر دهگان آن‌ها را بر اساس دهگان مرتب می‌کند و چون پایدار است، عددهایی که دهگان برابر دارند همان ترتیب یکان را نگه می‌دارند. پس بعد از گذر دهگان، آرایه بر اساس دو رقم آخر مرتب است، و همین‌طور تا آخرین رقم.
هزینه
برای d رقم: O(d·(n + 10)). وقتی تعداد رقم‌ها ثابت است، زمان خطی است و از n log n بهتر.
در trace به چه چیزی نگاه کنی
- با سطح جزئیات «هر دور حلقه» فقط پایان هر گذر را ببین و ترتیب میله‌ها را بعد از هر رقم دنبال کن.
- در ورودی «مثال به سبک کتاب»، بعد از گذر یکان عددها بر اساس رقم آخرشان مرتب‌اند (۷۲۰، ۳۵۵، ۴۳۶، …).