مرتب‌سازی سطلی
بازه را به n سطل برابر تقسیم می‌کند، هر عدد را در سطل خودش می‌اندازد، سطل‌ها را جدا مرتب می‌کند و پشت هم می‌چیند.
اگر عددها در بازه‌ای مشخص یکنواخت پخش باشند، می‌شود بازه را به n سطل هم‌اندازه تقسیم کرد. هر سطل به‌طور متوسط فقط یک عضو می‌گیرد، پس مرتب کردن سطل‌ها تقریباً رایگان است.
- زمان:
O(n) on average for evenly spread input, O(n²) at worst - حافظه:
O(n) - CLRS، بخش ۸.۴
ده عدد پخش در بازه؛ بیشتر سطل‌ها یک یا دو عضو دارند و مرتب کردنشان تقریباً هزینه‌ای ندارد.
def bucket_sort(a):n = len(a)buckets = [[] for _ in range(n)]for x in a:buckets[x * n // 100].append(x)for b in buckets:insertion_sort(b)out = []for b in buckets:out.extend(b)return outdef insertion_sort(b):for j in range(1, len(b)):key = b[j]i = j - 1while i >= 0:if b[i] <= key:breakb[i + 1] = b[i]i = i - 1b[i + 1] = key
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
78173926729421122368
Call stack
- bucket_sort()خط 1
گام ۱ از ۱۲۶
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- ورودی فعلی (n=10)
نمایش به شکل جدول
| n | comparisons |
|---|---|
| 4 | 1.2 |
| 6 | 1.9 |
| 8 | 3.8 |
| 10 | 3.8 |
| 12 | 4.5 |
| 14 | 5.7 |
| 16 | 5.9 |
توضیح
ایده
اگر عددها در بازه‌ای مشخص یکنواخت پخش باشند، می‌شود بازه را به n سطل هم‌اندازه تقسیم کرد. هر سطل به‌طور متوسط فقط یک عضو می‌گیرد، پس مرتب کردن سطل‌ها تقریباً رایگان است.
- هر عدد
xدر سطل⌊x · n / 100⌋می‌افتد (اینجا عددها ۰ تا ۹۹اند، یعنی صدم‌های بازه‌ی[0, 1)). - هر سطل جداگانه با مرتب‌سازی درجی مرتب می‌شود.
- سطل‌ها به ترتیب پشت هم چیده می‌شوند.
هزینه
- برای ورودی یکنواخت، زمان متوسط
O(n)است. - اگر همه در یک سطل بیفتند (ورودی «همه در یک سطل»)، کار به مرتب‌سازی درجی روی کل آرایه تبدیل می‌شود:
O(n²).
در trace به چه چیزی نگاه کنی
- لیست
bucketsدر پنل حافظه است: ببین هر عدد در کدام سطل می‌افتد. - شمار
compareرا در ورودی «یکنواخت» (صفر) و «همه در یک سطل» مقایسه کن.