مرتب‌سازی انتخابی (Selection Sort)
مرتب‌سازی انتخابی: پیدا کردن کوچک‌ترین و گذاشتن در جایش؛ کمترین تعداد جابه‌جایی بین الگوریتم‌های ساده
مرتب‌سازی انتخابی چیست؟
Selection Sort در هر پاس، کوچک‌ترین عنصر باقی‌مانده را پیدا و در جای درستش (ابتدای بخش نامرتب) می‌گذارد.
الگوریتم
- بخش مرتب (اول خالی) و بخش نامرتب (کل لیست) داریم
- کوچک‌ترین عنصر بخش نامرتب را پیدا کن
- با اولین عنصر بخش نامرتب جابه‌جا کن
- مرز بخش مرتب یک خانه جلو می‌رود
- تکرار تا n−1 پاس
مثال گام‌به‌گام
[64, 25, 12, 22, 11]
پاس ۱: min=11 -> [11 | 25, 12, 22, 64]
پاس ۲: min=12 -> [11, 12 | 25, 22, 64]
پاس ۳: min=22 -> [11, 12, 22 | 25, 64]
پاس ۴: min=25 -> [11, 12, 22, 25 | 64] ✓پیچیدگی
| معیار | مقدار |
|---|---|
| مقایسه‌ها (همه حالات) | O(n²) — همیشه n(n−1)/2 |
| جابه‌جایی‌ها | O(n) — حداکثر n−1 ✓ |
| حافظه | O(1) — درجا |
ویژگی منحصربه‌فرد: کمترین جابه‌جایی!
برخلاف Bubble Sort که ممکن است هزاران جابه‌جایی کند، Selection Sort حداکثر n−1 جابه‌جایی دارد. وقتی هزینه نوشتن/جابه‌جایی بسیار بالاست (مثل حافظه فلش)، این ویژگی ارزشمند است!
مقایسه با Bubble Sort
| ویژگی | Bubble | Selection |
|---|---|---|
| مقایسه‌ها | O(n²) | O(n²) |
| جابه‌جایی | O(n²) | O(n) ✓ |
| بهترین حالت | O(n) با بهینه‌سازی | O(n²) همیشه! |
| پایدار | ✓ | ✗ |
نکته: Selection Sort حتی روی داده مرتب هم O(n²) مقایسه می‌کند — چون همیشه باید کوچک‌ترین را با اسکن کامل پیدا کند!
جمع‌بندی
- هر پاس: کوچک‌ترین باقی‌مانده → جای درست
- مقایسه همیشه O(n²) اما جابه‌جایی فقط O(n)
- مناسب وقتی نوشتن گران است
- ناپایدار — ترتیب عناصر برابر حفظ نمی‌شود
این مبحث بخشی از دوره آموزش کامل ساختار داده و الگوریتم است.