الگوریتم مرتب‌سازی سریع

الگوریتم مرتب‌سازی سریع یکی از معروف‌ترین و کارآمدترین الگوریتم‌های مرتب‌سازی است که برای مرتب‌سازی آرایه‌ها و لیست‌ها به کار می‌رود. این الگوریتم از روش تقسیم و حکمت بهره می‌برد و معمولاً به عنوان یک الگوریتم “تقسیم و حکمتی” شناخته می‌شود. الگوریتم مرتب‌سازی سریع بسیار سریع و مؤثر عمل می‌کند و در بسیاری از زمینه‌های کاربردی مورد استفاده قرار می‌گیرد.

در ادامه، به توضیح مراحل اصلی الگوریتم مرتب‌سازی سریع می‌پردازیم:

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

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]  # انتخاب عنصر ابتدایی به عنوان عنصر پایه
        less_than_pivot = [x for x in arr[1:] if x <= pivot]  # زیرآرایه‌ای از عناصر کمتر یا مساوی عنصر پایه
        greater_than_pivot = [x for x in arr[1:] if x > pivot]  # زیرآرایه‌ای از عناصر بزرگتر از عنصر پایه
        return quick_sort(less_than_pivot) + [pivot] + quick_sort(greater_than_pivot)

# مثال استفاده:
unsorted_list = [3, 6, 8, 10, 1, 2, 1]
sorted_list = quick_sort(unsorted_list)
print(sorted_list)

این کد Python الگوریتم مرتب‌سازی سریع را نشان می‌دهد. الگوریتم ابتدا یک عنصر ابتدایی را به عنوان عنصر پایه انتخاب می‌کند و سپس عناصر کوچکتر و بزرگتر از عنصر پایه را جدا کرده و به صورت بازگشتی بر روی هر دو زیرآرایه اجرا می‌شود. در نهایت، عنصر پایه به تنهایی در میان عناصر کوچکتر و بزرگتر از خود قرار می‌گیرد و آرایه به صورت مرتب شده به دست می‌آید.
الگوریتم مرتب‌سازی سریع به دلیل کارآیی بالا و پیاده‌سازی نسبتاً ساده‌ای که دارد، یکی از الگوریتم‌های مرتب‌سازی محبوب در بسیاری از برنامه‌ها و سیستم‌هاست. اما باید توجه داشت که در برخی موارد ممکن است عملکرد الگوریتم مرتب‌سازی سریع برای داده‌های خاصی نسبت به دیگر الگوریتم‌ها کمی کمتر باشد. بنابراین، در انتخاب الگوریتم مناسب برای هر موقعیت، نیاز به ارزیابی دقیق نیازها و ویژگی‌های مسئله دارید.