مرتب سازی انتخابی در پایتون (Selection Sort)

در این جلسه به آموزش مرتب سازی انتخابی در پایتون می‌پردازیم. پیش نیاز این آموزش شامل موارد زیر می‌شود:

1. لیست در پایتون
2. حلقه for در پایتون
3. آشنایی با توابع

مرتب سازی انتخابی در پایتون

مرتب‌سازی انتخابی یکی از انواع الگوریتم مرتب‌سازی می‌باشد که در گروه  الگوریتم‌های مرتب‌سازی مبتنی بر مقایسه‌است. این الگوریتم دارای پیچیدگی زمانی از درجه O(n²)  است که به همین دلیل اعمال آن روی مجموعه بزرگی از اعداد کارا به نظر نمی رسد و به طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند. این مرتب‌سازی به دلیل سادگی‌اش قابل توجه‌است.(ویکیپدیا).

نحوه عملکرد

این الگوریتم اینگونه عمل می‌کند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا می‌کنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا می‌کنیم و این روند را برای n-1 عدد اول تکرار می‌کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می‌کنیم. زیرلیست اول که قبلاً مرتب کرده‌ایم و سایر اعضای لیست که هنوز مرتب نشده‌است. در جدول زیر مثالی از پیاده‌سازی این روال بر روی 7 عدد آمده‌است(ویکیپدیا)

پیاده سازی مرتب سازی انتخابی در پایتون

برای پیاده سازی مرتب سازی انتخابی در پایتون ما از یک تابع به نام selection sort استفاده می‌کنیم. کل کاری که این تابع انجام می‌دهد این است که یک لیست را ورودی می‌گیرد و آن ورودی را مرتب کرده و به عنوان خروجی بر می‌گرداند.

def selectionSort(A): 
  
    for i in range(len(A)): 
          
        min_idx = i 
        for j in range(i + 1, len(A)): 
            if A[min_idx] > A[j]: 
                min_idx = j 
                  
        A[i], A[min_idx] = A[min_idx], A[i] 

همانطور که در کد مرتب سازی انتخابی میبینید ما یک متغیر به نام  min index داریم. حلقه دوم یک دور کل لیست میچرخد و اگر خانه ای کوچکتر از min index بود اندیس آن را به عنوان min index قرار میدهد. سپس بعد از یک دور کامل ما اندیس کوچکترین خانه را داریم و آن را با خانه i (دور اول می‌شود اولین خانه لیست) عوض می‌کنیم. در دور بعد نیز همین روال را ادامه می‌دهیم فقط دومین خانه کوچکتر را در دور بعد پیدا می‌کنیم(دور بعد یکی به i اضافه می‌شود و ما از خانه i تا خانه آخر لیست دنبال عنصر کوچکتر می‌گردیم).

تست برنامه

برای تست برنامه کد زیر را بزنید.

if __name__ == '__main__':
    A= [64, 25, 12, 22, 11] 
    print("befor sort:")
    print(A)
    selectionSort(A)
    print ("Sorted array")
    print(A)  

خروجی برنامه به صورت زیر است.

befor sort:

[64, 25, 12, 22, 11]

Sorted array

[11, 12, 22, 25, 64]

ویدئو آموزش