آموزش کامل الگوریتم QuickSort با مثال عملی

آیا تابحال به این فکر کرده اید که چگونه در سیستم های کامپیوتری اعداد و آیتم های مورد نظر ما به صورت سریع Sort یا به زبان فارسی (مرتب سازی) می شوند؟ چه روش هایی برای مرتب سازی این داده ها به صورت سریع در دنیای کامپیوتر وجود دارد؟ 

در اینجاست که الگوریتم شگفت انگیز QuickSort به کمک ما می آید که یکی از پرکاربردترین و کارآمد ترین روش های مرتب سازی مبتنی بر تقسیم و حل (Divide and Conquer) می باشد. دلیل محبوبیت این الگوریتم و استفاده گسترده از آن به خاطر سرعت بالا و پیاده سازی بهینه در کنار کتابخانه های استاندارد برنامه نویسی می باشد که به برنامه نویس این اجازه را می دهد تا داده های خود را به صورت شگفت انگیزی مرتب کند.

ما در این مقاله از آکادمی برنامه نویسی کدیاد، قصد داریم تا به عمق این الگوریتم سفر کنیم و شما را با چیستی این الگوریتم آشنا سازیم. شما عزیزان پس از خواندن این مقاله با مراحل انجام این مرتب سازی، پیچیدگی های زمانی آن، ویژگی های اصلی این الگوریتم و پیاده سازی عملی QuickSort همراه با چندین مثال آشنا خواهید شد. پس در ادامه این مقاله با ما همراه باشید تا به دنیای جذاب این الگوریتم ها سفر کنیم…

الگوریتم QuickSort به زبان ساده چیست؟

و اما قبل از هرچیزی بیایید تا با چیستی اصلی این الگوریتم آشنا شویم. به زبان ساده، الگوریتم QuickSort یک الگوریتم مرتب سازی سریع شناخته می شود که داده های موجود در یک ساختمان داده را با روشی نوین و جذاب و همچنین سریع مرتب می کند. 

برای اینکه بتوانیم داده های یک ساختمان داده را به صورت سریع مرتب سازی کنیم، نیازمند این هستیم که یک عنصر داده را از آرایه به عنوان (لولا - محور) به زبان انگلیسی Pivot در نظر بگیریم که بتوانیم آرایه را به دو پارتیشن اصلی تقسیم کنیم. نحوه انتخاب عنصر اصلی یا همان Pivot هم استاندارد های خودش را دارد که در ادامه به آن خواهیم پرداخت.

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

نحوه انتخاب عنصر Pivot در الگوریتم مرتب سازی QuickSort

یکی از مهم ترین ارکان الگوریتم QuickSort عنصر محوری یا همان Pivot می باشد که برای انتخاب آن از میان داده های ساختمان داده استاندارد های اساسی را برای یک مرتب سازی دقیق باید رعایت کنیم. 

مجموعه داده ای که قصد مرتب سازی آن را داریم از یک نقطه یا بهتر است بگوییم که از یک عنصر محوری شکسته شده است. و به دو مجموعه اساسی دیگر تقسیم شده است. این روند در همه زیر مجموعه ها ادامه پیدا خواهد کرد. مسئله ی مهم اینجاست که دقیقا باید کدام عنصر را به عنوان عنصر محوری انتخاب کنیم. در ادامه به استاندارد های انتخاب عنصر Pivot اشاره می کنیم…

1. می توانیم همیشه اولین عنصر از داده های خود را به عنوان Pivot در نظر بگیریم.
2. می توانیم عنصر انتهایی مجموعه داده خود را به عنوان Pivot در نظر بگیریم.
3. می توانیم عنصر Pivot را به صورت Random یا تصادفی انتخاب کنیم.
4. همچنین می توانیم عنصر میانه را از مجموعه داده های خود به عنوان Pivot در نظر بگیریم.

مراحل اجرای الگوریتم QuickSort

یکی از مهمترین موضوعاتی که باید در مورد این الگوریتم بدانیم، مراحل اجرایی الگوریتم مرتب سازی سریع یا همان (QuickSort) است. به صورت کلی ما می توانیم این الگوریتم را در 7 مرحله انجام دهیم و به نتیجه برسیم و همچنین بتوانیم مجموعه داده های خود را در ساختمان داده مرتب کنیم. 

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

1. نخستین عنصر لیست را به عنوان Pivot در نظر میگیریم که البته این یکی از روش های انتخاب عنصر محوری است.
2. در مرحله ی دوم، دو متغیر  با نام های i و j تعریف می کنیم و آن ها را به ترتیب به عناصر اول و آخر لیست منتسب می کنیم.
3. تا زمانی که مقادیر مجموعه ی ما از Pivot بزرگتر باشد مقدار I افزایش می یابد و سپس متوقف می شود.
4. و تا زمانی که j که عضوی از مجموعه آرایه ی ما است کوچکتر از Pivot باشد مقدار J کاهش پیدا می کند.
5. اگر I < J باشد آنگاه عنصر List که شامل i است و عنصر List که شامل j است را جابجا می کنیم.
6. تا قبل از اینکه عنصر i بزرگتر از j باشد مراحل 3،4،5 را تکرار می کنیم.
7. عنصر Pivot را با عنصر List که شامل j است جابجا می کنیم.

با استفاده از این گام ها و اجرای آن ها به صورت مرتب می توانیم مقادیر یک مجموعه را به آسانی با استفاده از الگوریتم QuickSort مرتب سازی سریع انجام دهیم و از کار با این الگوریتم محاسباتی لذت ببریم.

پیچیدگی زمانی الگوریتم مرتب سازی سریع (QuickSort)

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

برای درک بهتر بیایید تا با یک مثال این مسئله را در ذهن شما روشن تر کنیم…

تصور کنید که ما یک الگوریتم داریم که داده هایی را از ورودی دریافت می کند. اگر ما داده های خود را 2 برابر کنیم، یعنی میزان داده های ارسالی به الگوریتم را افزایش دهیم، این کار ما باعث می شود تا زمان اجرای آن هم 2 برابر شود.

در کنار پیچیدگی زمانی در الگوریتم ها، ما پیچیدگی فضایی هم داریم. پیچیدگی فضایی به ارزیابی میزان حافظه مورد نیاز برای اجرای الگوریتم ها می پردازد.

ویژگی های الگوریتم QuickSort

حالا که با ماهیت الگوریتم جذاب QuickSort آشنا شدید، وقت آن است که سری به ویژگی های جذاب این الگوریتم بزنیم. در ادامه به 4 نوع از ویژگی های این الگوریتم جذاب برای برنامه نویسان خواهیم پرداخت…

• الگوریتم مرتب سازی سریع یک الگوریتم درجا (in place) است به این معنی که به حافظه ی اضافی اصلا نیازی ندارد و همچنین به طول آرایه هیچ وابستگی ندارد. در نتیجه استفاده از این الگوریتم برای حافظه ی سیستم بهینه است.
• روش مرتب سازی سریع یک روش ناپایدار (unbalance) است. به این معنی که اگر ما دو عنصر x1 و x2 را داشته باشیم که در آرایه مقادیری برابر داشته باشند ترتیب آن ها در آرایه مرتب شده نهایی لزوما تغییری نخواهد داشت.
• اگر تعداد عناصر آرایه کم باشد، الگوریتم مرتب سازی سریع روش مناسبی نیست و به جای آن بهتر است تا از روش مرتب سازی درجی استفاده کنیم.
• زمان اجرای الگوریتم مرتب سازی سریع QuickSort، به عنصر Pivot وابستگی دارد که می تواند عنصر ابتدا یا انتهای آرایه باشد. همچنین انتخاب یک عنصر Pivot بهینه هزینه ی بالایی دارد.

مثال (مرتب سازی آرایه)

به عنوان مثال اول ما قصد داریم تا یک آرایه را با استفاده از الگوریتم مرتب سازی سریع یا همان QuickSort مرتب کنیم. آرایه ای که ما در این جا داریم [10, 7, 8, 9, 1, 5] این آرایه است. در مرحله اول ما عنصر Pivot را انتخاب می کنیم که اخرین عنصر یعنی عدد 5 را در نظر میگیریم.

در مرحله دوم تقسیم بندی آرایه را انجام می دهیم. عناصر کمتر از Pivot به چپ و عناصر بزرگتر از Pivot به راست منتقل می شود که در نتیجه آرایه ما به این شکل در می آید : [1, 5, 8, 9, 10, 7]  

در مرحله سوم ما مرتب سازی بازگشت زیرآرایه ها را انجام  می دهیم. 

• زیر آرایه چپ تنها یک عنصر دارد که عدد 1 است و مرتب است.
• زیر آرایه راست [8, 9, 10, 7] می باشد که دوباره عدد Pivot 7 در نظر گرفته می شود و همان مراحل 1 و 2 دوباره اجرا می شود.
• در مرحله اخر آرایه مرتب شده ی ما به این صورت است : [1, 5, 7, 8, 9, 10]

نمونه کد پیاده سازی شده از الگوریتم  QuickSort

شاید در حال حاضر این سوال در ذهن شما ایجاد شده باشد که حالا که با ماهیت و نحوه کارکرد این الگوریتم بهینه مرتب سازی سریع آشنا شدیم، چگونه می توانم از آن در یک زبان برنامه نویسی استفاده کنم؟ ما در اینجا برای شما یک مثال از کد پیاده سازی شده این الگوریتم با استفاده از زبان برنامه نویسی Python آورده ایم. به کد زیر دقت کنید : 

def quick_sort(arr):
    """
    تابع مرتب‌سازی سریع (QuickSort) به صورت بازگشتی
    :param arr: لیست ورودی برای مرتب‌سازی
    :return: لیست مرتب‌شده
    """
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # انتخاب pivot به عنوان عنصر میانی
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# مثال استفاده از تابع
if __name__ == "__main__":
    data = [8, 3, 1, 7, 0, 10, 2]
    print("لیست قبل از مرتب‌سازی:", data)
    sorted_data = quick_sort(data)
    print("لیست بعد از مرتب‌سازی:", sorted_data)

سوالات متداول

۱. چرا QuickSort سریع است؟

QuickSort با پیچیدگی متوسط O(n log n) و روش تقسیم-و-حل کار می‌کند. این الگوریتم داده‌ها را به بخش‌های کوچکتر تقسیم می‌کند که پردازش را تسریع می‌بخشد. همچنین پیاده‌سازی بهینه آن در زبان‌های برنامه‌نویسی باعث سرعت عملی بالایش شده است.

۲. تاثیر انتخاب Pivot چیست؟ 

انتخاب Pivot نامناسب (مثل کوچکترین/بزرگترین عنصر) می‌تواند کارایی را به O(n²) برساند. انتخاب Pivot بهینه (میانه یا تصادفی) عملکرد O(n log n) را تضمین می‌کند. روش‌هایی مثل "میانه سه‌تایی" تعادل بهتری ایجاد می‌کنند.

۳. آیا QuickSort همیشه بهتر است؟ 

خیر. برای داده‌های تقریباً مرتب‌شده یا بسیار کوچک مناسب نیست. MergeSort برای داده‌های حجیم یا وقتی پایداری مهم است بهتر عمل می‌کند. QuickSort معمولاً برای داده‌های تصادفی و معمولی گزینه بهتری است.

۴. محدودیت‌های QuickSort چیست؟

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

۵. چگونه QuickSort را بهینه کنیم؟ 

با ترکیب Insertion Sort برای زیرآرایه‌های کوچک (مثلاً زیر ۱۰ عنصر). استفاده از Pivot تصادفی یا میانه سه‌تایی از بدترین حالت جلوگیری می‌کند. پیاده‌سازی غیربازگشتی مصرف حافظه را کاهش می‌دهد.