مرتب‌سازی انتخابی
در هر دور کوچک‌ترین عضو بخش نامرتب را پیدا می‌کند و آن را به ابتدای همان بخش می‌برد.
آرایه دو بخش دارد: بخش مرتب در ابتدا و بخش نامرتب بعد از آن. در هر دور، کوچک‌ترین عضو بخش نامرتب پیدا می‌شود و با اولین عضو همان بخش جابه‌جا می‌شود. بعد از دور i، خانه‌ی i جای نهایی‌اش را دارد.
- زمان:
O(n²) - حافظه:
O(1) - CLRS، بخش ۲.۲
- هوروویتز–ساهنی، فصل ۱
پنج عدد درهم؛ چهار دور، هر دور یک عضو در جای نهایی‌اش می‌نشیند.
def selection_sort(a):n = len(a)for i in range(n - 1):smallest = ifor j in range(i + 1, n):if a[j] < a[smallest]:smallest = ja[i], a[smallest] = a[smallest], a[i]return a
شروع اجرا
متغیرهای محلی
نارنجی = در همین گام عوض شد
a list
6425122211
Call stack
- selection_sort()خط 1
گام ۱ از ۴۵
رشد تعداد عملیات با اندازه‌ی ورودی
میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.
- comparisons
- swaps
- ورودی فعلی (n=5)
نمایش به شکل جدول
| n | comparisons | swaps |
|---|---|---|
| 4 | 6 | 3 |
| 6 | 15 | 5 |
| 8 | 28 | 7 |
| 10 | 45 | 9 |
| 12 | 66 | 11 |
| 14 | 91 | 13 |
| 16 | 120 | 15 |
توضیح
ایده
آرایه دو بخش دارد: بخش مرتب در ابتدا و بخش نامرتب بعد از آن. در هر دور، کوچک‌ترین عضو بخش نامرتب پیدا می‌شود و با اولین عضو همان بخش جابه‌جا می‌شود. بعد از دور i، خانه‌ی i جای نهایی‌اش را دارد.
هزینه
- تعداد مقایسه‌ها همیشه
n(n − 1)/2است، هر ورودی‌ای که باشد:O(n²). - تعداد جابه‌جایی‌ها حداکثر
n − 1است؛ وقتی نوشتن در حافظه گران است، این مزیت مهمی است. - حافظه‌ی اضافه
O(1).
پایداری
جابه‌جایی کوچک‌ترین عضو با a[i] ممکن است عضوی را از کنار عضو برابرش رد کند، پس مرتب‌سازی انتخابی پایدار نیست.
در trace به چه چیزی نگاه کنی
- فلش
smallestکوچک‌ترین عضو تا اینجا را نشان می‌دهد وjبقیه‌ی بخش را مرور می‌کند. - شمار
compareرا در «از قبل مرتب» و «برعکس مرتب» مقایسه کن: یکی است.