مرتب سازی سریع در پایتون (Quick Sort)

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

1. آشنایی با تابع
2. آشنایی با لیست
3. آشنایی با روش بازگشتی
4. آشنایی با شرط if
5. آشنایی با حلقه for

مرتب سازی سریع

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

هر پیاده‌سازی این الگوریتم به‌صورت کلی از دو بخش تشکیل شده‌است. یک بخش تقسیم‌بندی آرایه (partition) و قسمت مرتب کردن. روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1. انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) – به عنوان مثال عنصر اول – انتخاب می‌شود.
2. تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی عنصر محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.
3. مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند(ویکیپدیا)

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

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

def partition(arr,low,high): 
    i = ( low-1 )         # index of smaller element 
    pivot = arr[high]     # pivot 
  
    for j in range(low , high): 
  
        if   arr[j] <= pivot: 
          
            i = i+1 
            arr[i],arr[j] = arr[j],arr[i] 
  
    arr[i+1],arr[high] = arr[high],arr[i+1] 
    return ( i+1 ) 
  
def quickSort(arr,low,high): 
    if low < high: 
  
        pi = partition(arr,low,high) 
        quickSort(arr, low, pi-1) 
        quickSort(arr, pi+1, high)

کد مرتب سازی سریع در پایتون دارای دو تابع می‌باشد

1. Quicksort
2. Partion

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

در تصویر بالا عدد 4 به عنوان pivot انتخاب شده است. اعداد کوچکتر از آن یعنی 2 و 3 و 3 در سمت چپ آن و اعداد بزرگتر یعنی 5 و 6 و 8 در سمت راست قرار دارند. در مرحله بعد باید زیرلیست سمت چپ و راست به طور جداگانه مرتب کنیم.

برای زیرلیست سمت چپ یعنی 2 و 3 و 3 یک pivot انتخاب می کنیم. عدد 3 pivot ما است. بعد از قرار دادن اعداد کوچکتر و بزرگتر سمت چپ و راست pivot می بینید که زیرلیست سمت چپ مرتب شده است. برای زیر لیست سمت راست نیز همین کار را می‌کنیم. توجه داشته باشید در مثال بالا عنصر pivot خانه وسط لیست ما می‌باشد عنصر pivot می‌تواند هر عنصری از لیست باشد.

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

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

if __name__ == '__main__':
    arr = [10, 7, 8, 9, 1, 5] 
    print ("Before sort:") 
    print(arr)
    n = len(arr) 
    quickSort(arr,00,n-1) 
    print ("Sorted array is:") 
    print(arr)

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

Before sort:

[10, 7, 8, 9, 1, 5]

Sorted array is:

[1, 5, 7, 8, 9, 10]

ویدئو آموزش

اگر سوالی در خصوص مرتب سازی سریع در پایتون دارید در قسمت کامنت سوال خود را مطرح کنید تا پاسخگوی شما باشیم.