مرتب سازی انتخابی (Selection Sort)
در «مرتب سازی انتخابی (Selection Sort)» هر بار کوچک ترین مقدار را پیدا می کنیم. سپس آن را به ابتدای بخش نامرتب می آوریم. با تکرار این کار، لیست کاملاً مرتب می شود.
ایده اصلی مرتب سازی انتخابی
در هر دور، کمترین عنصرِ بخش نامرتب پیدا می شود. بعد آن عنصر به ابتدای همان بخش منتقل می شود. سپس مرز بخش مرتب، یک خانه جلو می آید.
پیاده سازی پایه با جابه جایی و درج
این نسخه کمترین مقدار را حذف می کند و در جای درست درج می کند. در زبان های سطح بالا، پشت صحنه عناصر جابه جا می شوند.
mylist = [64, 34, 25, 5, 22, 11, 90, 12]
n = len(mylist)
for i in range(n - 1):
min_index = i
for j in range(i + 1, n):
if mylist[j] < mylist[min_index]:
min_index = j
min_value = mylist.pop(min_index)
mylist.insert(i, min_value)
print(mylist)
بهبود: تعویض به جای جابه جایی زیاد
برای کاهش جابه جایی ها، به جای حذف/درج، تعویض (Swap) انجام می دهیم. سرعت بهتر می شود.
mylist = [64, 34, 25, 12, 22, 11, 90, 5]
n = len(mylist)
for i in range(n):
min_index = i
for j in range(i + 1, n):
if mylist[j] < mylist[min_index]:
min_index = j
mylist[i], mylist[min_index] = mylist[min_index], mylist[i]
print(mylist)
گام های عملی
- مرز بخش مرتب را تعیین کن.
- کوچک ترین عنصر بخش نامرتب را بیاب.
- آن را به ابتدای بخش نامرتب بیاور.
- مرز را یک خانه جلو ببر.
- تا پایان لیست تکرار کن.
پیچیدگی زمانی مرتب سازی انتخابی
در هر دور حدود نصف عناصر بررسی می شود. این کار تقریباً n بار تکرار می شود. بنابراین «پیچیدگی زمانی (Time Complexity)» برابر O(n^2) است.
نکته: اگر به سرعت بیشتر نیاز داری، به مرتب سازی حبابی و سپس مرتب سازی درجی هم نگاه کن.
جمع بندی سریع
- هر دور کمترین عنصر جلو می آید.
- نسخه تعویض، جابه جایی اضافی ندارد.
- پیچیدگی زمانی O(n^2) است.
- برای لیست بزرگ، کند می شود.
- روی داده کوچک، ساده و قابل فهم است.