انتخاب سریع (k امین کوچک‌ترین)
مثل مرتب‌سازی سریع افراز می‌کند، ولی فقط در سمتی که k امین عضو در آن است ادامه می‌دهد؛ به‌طور متوسط زمان خطی.
برای پیدا کردن k امین کوچک‌ترین عضو (مثلاً میانه) لازم نیست کل آرایه را مرتب کنیم. یک افراز مثل مرتب‌سازی سریع انجام بده: محور در جای نهایی‌اش می‌نشیند، کوچک‌ترها چپش و بزرگ‌ترها راستش. اگر رتبه‌ی محور همان k بود، تمام است؛ وگرنه فقط یک طرف را ادامه بده.
- زمان:
O(n) on average, O(n²) at worst - حافظه:
O(1) - CLRS، بخش ۹.۲
چهارمین کوچک‌ترینِ هشت عدد؛ فقط سمت لازم افراز می‌شود.
def quickselect(a, k):lo = 0hi = len(a) - 1while True:if lo == hi:return a[lo]p = partition(a, lo, hi)rank = p - lo + 1if k == rank:return a[p]if k < rank:hi = p - 1else:k = k - ranklo = p + 1def partition(a, lo, hi):pivot = a[hi]i = lo - 1for j in range(lo, hi):if a[j] <= pivot:i = i + 1a[i], a[j] = a[j], a[i]a[i + 1], a[hi] = a[hi], a[i + 1]return i + 1
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
Call stack
- quickselect()خط 1
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- ورودی فعلی (n=8)
نمایش به شکل جدول
| n | comparisons |
|---|---|
| 4 | 4.4 |
| 6 | 7.4 |
| 8 | 13.5 |
| 10 | 20 |
| 12 | 22.1 |
| 14 | 30.6 |
| 16 | 34.6 |
توضیح
ایده
برای پیدا کردن k امین کوچک‌ترین عضو (مثلاً میانه) لازم نیست کل آرایه را مرتب کنیم. یک افراز مثل مرتب‌سازی سریع انجام بده: محور در جای نهایی‌اش می‌نشیند، کوچک‌ترها چپش و بزرگ‌ترها راستش. اگر رتبه‌ی محور همان k بود، تمام است؛ وگرنه فقط یک طرف را ادامه بده.
هزینه
- به‌طور متوسط هر افراز بازه را حدود نصف می‌کند:
n + n/2 + n/4 + … ≈ 2n، یعنیO(n)، از مرتب کردن (n log n) بهتر. - در بدترین حالت (ورودی «مرتب، کوچک‌ترین»)، هر افراز فقط یک عضو کنار می‌گذارد:
O(n²). CLRS با «میانه‌ی میانه‌ها» محوری تضمینی می‌سازد که بدترین حالت را هم خطی می‌کند.
در trace به چه چیزی نگاه کنی
- نوار آبی بازه‌ی
lo..hiاست که جواب در آن است؛ ببین بعد از هر افراز چطور کوچک می‌شود. kبالای آرایه نوشته شده و با رفتن به سمت راست کم می‌شود.