مرتب سازی درجی در پایتون (insertion Sort)

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

1. آشنایی با حلقه for
2. آشنایی با حلقه while
3. آشنایی با توابع
4. آشنایی با لیست

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

مرتب‌ساز درجی (Insertion Sort)  یک الگوریتم مرتب‌سازی ساده بر مبنای مقایسه است. این الگوریتم برای تعداد داده‌های زیاد، کارآمد نیست و در این موارد، الگوریتم‌های بهتری مثل مرتب‌ساز سریع، مرتب‌ساز ادغامی و مرتب‌ساز پشته وجود دارد.(ویکیپدیا)

الگوریتم

این الگوریتم به این صورت عمل می‌کند که تمام عناصر لیست را یکی یکی برمی‌دارد و آن را در موقعیت مناسب در بخش مرتب شده قرار می‌دهد. انتخاب عنصر مورد نظر، اختیاری است و می‌تواند توسط هر الگوریتم انتخابی، انتخاب شود. مرتب‌سازی درجی به صورت درجا عمل می‌کند. نتیجه عمل بعد از k مرحله، حاوی k عنصر انتخاب شده به صورت مرتب شده است.

معمول‌ترین نسخه از این الگوریتم که روی آرایه‌ها عمل می‌کند، به این صورت است:

1. فرض کنید یک تابع به اسم Insert داریم که داده را در بخش مرتب شده در ابتدای آرایه درج می‌کند. این تابع با شروع از انتهای سری شروع به کار می‌کند و هر عنصر را به سمت راست منتقل می‌کند تا وقتی که جای مناسب برای عنصر جدید پیدا شود. این تابع این اثر جانبی را دارد که عنصر دقیقاً بعد از بخش مرتب شده را رونویسی می‌کند.
2. برای اعمال مرتب‌ساز درجی، از انتهای سمت چپ آرایه شروع می‌کنیم و با صدا زدن تابع insert، هر عنصر را به موقعیت درستش می‌بریم. آن بخشی که عنصر فعلی را در آن می‌کنیم، در ابتدای آرایه و در اندیس‌هایی است که آنها را قبلاً آزمایش کرده‌ایم. هر بار صدا زدن تابع insert، یک عنصر را رونویسی می‌کند، اما این مسئله مشکلی ایجاد نمی‌کند، زیرا این داده، همانی است که الان در حال درج آن هستیم(ویکیپدیا)

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

برای پیاده سازی مرتب سازی درجی در پایتون باید فرآیند این الگوریتم را خوب متوجه شوید. ابتدا این الگوریتم فرض می‌کند ما فقط یک خانه داریم و عنصر بعدی به این یک خانه اضافه می‌کند و این دو خانه مرتب می‌شوند. حال که دو خانه مرتب شدند عنصر سوم را به دو خانه قبلی اضافه می‌کند و حال این 3 خانه را مرتب می‌کند. این کار را تا جایی ادامه می‌دهد که تمام عناصر ما مرتب شده باشند.

def insertionSort(arr): 
  
    for i in range(1, len(arr)): 
  
        key = arr[i] 
  
        j = i - 1
        while j >= 0 and key < arr[j] : 
                arr[j + 1] = arr[j] 
                j -= 1
        arr[j + 1] = key

توضیح کد بالا کمی دشوار است ولی توضیح کلی که در مورد کد میتوان داد این است که حلقه for برای تعداد خانه های لیست است(همانطور که گفتیم الگوریتم تا تمامی عناصر را مرتب نکند تمام نمی‌شود) و حلقه دوم برای مرتب کردن عناصر از 0 تا j است. حلقه while تا زمانیکه خانه‌های مرتب‌شده شده قبلی(خانه 0 تا j ) از خانه جدید که می‌خواهیم آن را مرتب کنیم، بزرگتر باشد، یک خانه به عقب می‌برد. وقتی شرط بزرگتر بودن برقرار نباشد(key < arr[j]) یعنی خانه عنصر جدید پیدا شده است و عنصر جدید(key) را در آن خانه قرار می‌دهیم (arr[j + 1] = key).

تست مرتب‌سازی درجی

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

if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6] 
    print ("before sort array is:") 
    print (arr)
    insertionSort(arr) 
    print ("Sorted array is:") 
    print (arr)

خروجی برنامه:

before sort array is:

[12, 11, 13, 5, 6]

Sorted array is:

[5, 6, 11, 12, 13]

ویدئو آموزش