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

معرفی

مرتب سازی سریع یک الگوریتم مرتب‌سازی محبوب است و اغلب در کنار Merge Sort استفاده می‌شود. این یک مثال خوب از یک الگوریتم مرتب سازی کارآمد است، با پیچیدگی متوسط ​​\(O(nlogn)\). بخشی از محبوبیت آن نیز ناشی از سهولت آن است پیاده سازی.

ما در قسمت اول این مقاله از اعداد صحیح ساده استفاده خواهیم کرد، اما مثالی از روش تغییر این الگوریتم برای مرتب سازی اشیاء یک کلاس سفارشی ارائه می دهیم.

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

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

این چیزی است که وقتی اشیاء را به جای انواع اولیه مرتب می‌کنید، اهمیت پیدا می‌کند. به عنوان مثال، تصور کنید چندین مورد دارید Person اشیایی که دارای یکسان هستند age، یعنی دیو 21 ساله و مایک 21 ساله. اگر قرار بود از Quicksort استفاده کنید روی مجموعه‌ای که هم دیو و هم مایک را در بر می‌گیرد و بر اساس سن مرتب شده‌اند، هیچ تضمینی وجود ندارد که هر بار که الگوریتم را اجرا می‌کنید، دیو پیش مایک بیاید و بالعکس.

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

نسخه اصلی الگوریتم موارد زیر را انجام می دهد:

• با گرفتن یک عنصر شبه تصادفی و استفاده از آن به عنوان یک مجموعه را به دو قسمت (تقریبا) مساوی تقسیم کنید. محوری.

• عناصر کوچکتر از محور به سمت چپ محور و عناصر بزرگتر از محور به سمت راست آن منتقل می شوند.

• این process برای مجموعه سمت چپ pivot و همچنین برای آرایه عناصر سمت راست pivot تکرار می شود تا زمانی که کل آرایه مرتب شود.

هنگامی که ما عناصر را به عنوان “بزرگتر” یا “کوچکتر” از عنصر دیگر توصیف می کنیم – لزوماً به معنای اعداد صحیح بزرگتر یا کوچکتر نیست، می توانیم بر اساس هر ویژگی که انتخاب می کنیم مرتب کنیم.

اگر کلاس سفارشی داریم Person، و هر فرد دارای یک name و age، می توانیم مرتب سازی کنیم name (از نظر لغوی) یا بر اساس سن (صعودی یا نزولی).

مرتب سازی سریع چگونه کار می کند

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

یک لحظه درباره آن فکر کن – چگونه یک محور مناسب برای آرایه خود انتخاب می کنید؟ ایده های زیادی در مورد روش انتخاب یک محور در تاریخچه Quicksort ارائه شده است – انتخاب تصادفی یک عنصر، که به دلیل “گران بودن” انتخاب یک عنصر تصادفی کار نمی کند در حالی که یک انتخاب محوری خوب را تضمین نمی کند. انتخاب یک عنصر از وسط؛ انتخاب میانه عنصر اول، میانی و آخر؛ و حتی فرمول های بازگشتی پیچیده تر.

ساده ترین رویکرد این است که به سادگی اولین (یا آخرین) عنصر را انتخاب کنید. این منجر به Quicksort، از قضا، عملکرد بسیار بدی است روی آرایه هایی که قبلا مرتب شده اند (یا تقریبا مرتب شده اند).

این روشی است که اکثر مردم پیاده‌سازی Quicksort را انتخاب می‌کنند و از آنجایی که ساده است و این روش انتخاب pivot یک عملیات بسیار کارآمد است (و ما باید آن را مکررا انجام دهیم)، این دقیقاً همان کاری است که ما انجام خواهیم داد.

اکنون که یک محور را انتخاب کرده ایم – با آن چه کنیم؟

باز هم راه های مختلفی برای انجام خود پارتیشن بندی وجود دارد. یک خواهیم داشت “نشانگر” به محور ما، آ اشاره گر به عناصر “کوچکتر”.، و الف اشاره گر به عناصر “بزرگتر”..

این هدف حرکت دادن عناصر به اطراف است تا همه عناصر کوچکتر از محور در سمت چپ آن و همه عناصر بزرگتر در سمت راست آن قرار دارند. عناصر کوچکتر و بزرگتر لزوماً مرتب نمی شوند، ما فقط آنها را می خواهند روی سمت مناسب محور سپس به صورت بازگشتی از سمت چپ و راست پیوت عبور می کنیم.

آ گام به گام نگاهی به آنچه که ما قصد انجام آن را داریم به نشان دادن آن کمک خواهد کرد process. با استفاده از آرایه نشان داده شده در زیر، اولین عنصر را به عنوان محور انتخاب کردیم (29)، و نشانگر عناصر کوچکتر (به نام “کم”) بلافاصله بعد شروع می شود، و اشاره گر به عناصر بزرگتر (به نام “بالا”) شروع می شود. در پایان شروع می شود

• 29 اولین محور است، کم اشاره می کند 99، و بالا اشاره می کند 44:

• حرکت می کنیم high به سمت چپ تا زمانی که مقداری کمتر از pivot خود پیدا کنیم:

• حالا که ما بالا متغیر به 21، یک عنصر کوچکتر از pivot، می خواهیم مقداری را در نزدیکی ابتدای آرایه پیدا کنیم که بتوانیم swap آن را با. هیچ معنایی ندارد swap با مقداری که از pivot نیز کوچکتر است، بنابراین اگر کم به عنصر کوچکتری اشاره می کند که ما سعی می کنیم عنصری بزرگتر را پیدا کنیم.
• ما حرکت می کنیم کم متغیر سمت راست تا زمانی که عنصری بزرگتر از the را پیدا کنیم محوری. خوشبختانه، کم قبلا مستقر شده بود روی 99.
• ما swap مکان های از کم و بالا:

• بلافاصله پس از انجام این کار، حرکت می کنیم بالا به سمت چپ و کم به سمت راست (از آنجا که 21 و 99 اکنون در مکان های صحیح خود هستند)
• باز هم حرکت می کنیم بالا به سمت چپ تا زمانی که به مقدار کمتر از مقدار برسیم محوری، که بلافاصله پیدا می کنیم – 12
• اکنون مقداری بزرگتر از the را جستجو می کنیم محوری با حرکت کم به سمت راست، و ما اولین مقدار را در پیدا می کنیم 41

این process تا زمان ادامه دارد کم و بالا اشاره گرها در نهایت در یک عنصر به هم می رسند:

• ما دیگر هیچ استفاده ای از این محور نداریم، بنابراین تنها کاری که باید انجام دهیم این است swap محوری و بالا و ما با این مرحله بازگشتی به پایان رسیدیم:

همانطور که می بینید، ما به تمام مقادیر کوچکتر از 29 اکنون در سمت چپ هستند 29، و همه مقادیر بزرگتر از 29 سمت راست هستند.

سپس الگوریتم همین کار را برای 28،21،27،12،19 (سمت چپ) مجموعه و 44,78,87,66,31,76,58,88,83,97,41,99,44 مجموعه (سمت راست).

پیاده سازی

مرتب سازی آرایه ها

Quicksort به طور طبیعی است الگوریتم بازگشتی – آرایه ورودی را به آرایه های کوچکتر تقسیم کنید، عناصر را به سمت مناسب محور حرکت دهید و تکرار کنید.

بیایید ببینیم چند تماس بازگشتی چگونه به نظر می رسند:

• هنگامی که ما برای اولین بار الگوریتم را فراخوانی می کنیم، همه عناصر را – از شاخص ها – در نظر می گیریم 0 به n-1 جایی که n تعداد عناصر آرایه ما است.
• اگر پیوت ما در موقعیتی قرار بگیرد ک، ما سپس تکرار می کنیم process برای عناصر از 0 به k-1 و از k+1 به n-1.
• در حین مرتب سازی عناصر از k+1 به n-1، محور فعلی در موقعیتی قرار می گیرد پ. سپس عناصر را از آن مرتب می کنیم k+1 به p-1 و p+1 به n-1، و غیره روی.

همانطور که گفته شد، ما از دو تابع استفاده خواهیم کرد – partition() و quick_sort(). این quick_sort() ابتدا عملکرد خواهد داشت partition() مجموعه و سپس به صورت بازگشتی خود را فراخوانی می کند روی قسمت های تقسیم شده

بیایید با partition() تابع:

def partition(array, start, end):
    pivot = array(start)
    low = start + 1
    high = end

    while True:
        
        
        
        
        
        while low <= high and array(high) >= pivot:
            high = high - 1

        
        while low <= high and array(low) <= pivot:
            low = low + 1

        
        
        if low <= high:
            array(low), array(high) = array(high), array(low)
            
        else:
            
            break

    array(start), array(high) = array(high), array(start)

    return high

و در نهایت، بیایید پیاده سازی کنیم quick_sort() تابع:

def quick_sort(array, start, end):
    if start >= end:
        return

    p = partition(array, start, end)
    quick_sort(array, start, p-1)
    quick_sort(array, p+1, end)

با اجرای هر دوی آنها، می توانیم اجرا کنیم quick_sort() روی یک آرایه ساده:

array = (29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44)

quick_sort(array, 0, len(array) - 1)
print(array)

خروجی:

(12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99)

مرتب سازی اشیاء سفارشی

چند راه وجود دارد که می توانید این الگوریتم را برای مرتب کردن اشیاء سفارشی در پایتون بازنویسی کنید. یک راه بسیار پایتونیک پیاده سازی عملگرهای مقایسه برای یک کلاس معین است، به این معنی که ما در واقع نیازی به تغییر پیاده سازی الگوریتم نداریم. >، ==، <=و غیره نیز کار خواهد کرد روی شی کلاس ما

گزینه دیگر این است که به تماس گیرنده اجازه دهیم تا روشی را به الگوریتم ما ارائه دهد که سپس برای انجام مقایسه واقعی اشیاء استفاده می شود. بازنویسی الگوریتم به این روش برای استفاده با اشیاء سفارشی نسبتاً ساده است. البته به خاطر داشته باشید که الگوریتم پایدار نیست.

بیایید با یک شروع کنیم Person کلاس:

class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __str__(self):
        return self.name

این یک کلاس بسیار ابتدایی با تنها دو ویژگی است، name و age. می خواهیم استفاده کنیم age به عنوان کلید مرتب سازی ما، که با ارائه یک تابع لامبدا سفارشی به الگوریتم مرتب سازی انجام خواهیم داد.

اما ابتدا، بیایید ببینیم که چگونه این تابع ارائه شده در الگوریتم استفاده می شود. به جای مقایسه مستقیم با <= یا >= عملگرها، در عوض تابع را فراخوانی می کنیم تا بگوییم کدام است Person از نظر سنی بالاتر است:

def partition(array, start, end, compare_func):
    pivot = array(start)
    low = start + 1
    high = end

    while True:
        while low <= high and compare_func(array(high), pivot):
            high = high - 1

        while low <= high and not compare_func(array(low), pivot):
            low = low + 1

        if low <= high:
            array(low), array(high) = array(high), array(low)
        else:
            break

    array(start), array(high) = array(high), array(start)

    return high

def quick_sort(array, start, end, compare_func):
    if start >= end:
        return

    p = partition(array, start, end, compare_func)
    quick_sort(array, start, p-1, compare_func)
    quick_sort(array, p+1, end, compare_func)

و حالا بیایید مجموعه ای از این اشیاء را مرتب کنیم. می بینید که مقایسه شی در اختیار شما قرار می گیرد quick_sort تماس از طریق لامبدا، که مقایسه واقعی را انجام می دهد age ویژگی:

p1 = Person("Dave", 21)
p2 = Person("Jane", 58)
p3 = Person("Matthew", 43)
p4 = Person("Mike", 21)
p5 = Person("Tim", 10)

array = (p1,p2,p3,p4,p5)

quick_sort(array, 0, len(array) - 1, lambda x, y: x.age < y.age)
for person in array:
    print(person)

خروجی این است:

Tim
Dave
Mike
Matthew
Jane

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

بهینه سازی Quicksort

با توجه به اینکه Quicksort “نیمه های” یک آرایه داده شده را به طور مستقل مرتب می کند، برای موازی سازی بسیار راحت است. ما می‌توانیم یک رشته مجزا داشته باشیم که هر «نیمی» از آرایه را مرتب می‌کند، و در حالت ایده‌آل می‌توانیم زمان مورد نیاز برای مرتب‌سازی آن را به نصف کاهش دهیم.

با این حال، Quicksort می تواند داشته باشد یک پشته تماس بازگشتی بسیار عمیق اگر در انتخاب محوری بدشانس باشیم و موازی سازی به اندازه Merge Sort کارآمد نباشد.

توصیه می شود از یک الگوریتم ساده و غیر بازگشتی برای مرتب سازی آرایه های کوچک استفاده کنید. حتی یک چیز ساده مانند مرتب سازی درج کارآمدتر است روی آرایه های کوچک نسبت به Quicksort. بنابراین در حالت ایده‌آل، می‌توانیم بررسی کنیم که آیا زیرآرایه ما فقط تعداد کمی از عناصر دارد (بیشتر توصیه‌ها می‌گویند حدود 10 یا کمتر)، و اگر چنین است، به جای آن، آن را با Insertion Sort مرتب می‌کنیم.

یکی از انواع محبوب Quicksort، Multi-pivot Quicksort است که آرایه اصلی را به دو قسمت تقسیم می کند n آرایه های کوچکتر، با استفاده از n-1 محورها با این حال، بیشتر اوقات فقط از دو محور استفاده می شود، نه بیشتر.

نتیجه

همانطور که قبلا ذکر کردیم، کارایی Quicksort بسیار بستگی دارد روی انتخاب محور – می تواند پیچیدگی زمان (و فضای پشته) الگوریتم را “بسازد یا از بین ببرد”. ناپایداری الگوریتم نیز چیزی است که می تواند در هنگام استفاده از اشیاء سفارشی باعث شکستن معامله شود.

با این حال، با وجود همه اینها، میانگین پیچیدگی زمانی Quicksort از \(O(nlogn)\) و فضای نسبتاً کم و اجرای ساده آن، آن را به یک الگوریتم بسیار کارآمد و محبوب تبدیل کرده است.