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

---

الگوریتم مرتب‌سازی سریع (Quick Sort) یک الگوریتم مرتب‌سازی مقایسه‌ای با کارایی بالا است که از روش تقسیم و غلبه (Divide and Conquer) استفاده می‌کند. در اینجا توضیح گام به گام نحوه عملکرد این الگوریتم آمده است:

**1. انتخاب محور (Pivot):**

* در ابتدا، یک عنصر به عنوان **محور** (pivot) انتخاب می‌شود. انتخاب محور می‌تواند به روش‌های مختلفی صورت گیرد:
* **اولین عنصر:** ساده‌ترین روش، انتخاب اولین عنصر آرایه به عنوان محور است.
* **آخرین عنصر:** انتخاب آخرین عنصر آرایه.
* **عنصر میانی:** انتخاب عنصر وسط آرایه.
* **عنصر تصادفی:** انتخاب یک عنصر به صورت تصادفی.
* **میانه سه عنصر:** انتخاب میانه بین اولین، آخرین و عنصر میانی. این روش اغلب برای بهبود عملکرد استفاده می‌شود.

**2. بخش‌بندی (Partitioning):**

* هدف از بخش‌بندی، **جابجایی عناصر** در آرایه به گونه‌ای است که تمام عناصر کوچکتر یا مساوی محور در سمت چپ محور و تمام عناصر بزرگتر از محور در سمت راست آن قرار گیرند.
* برای این کار، معمولاً از دو نشانگر (pointer) به نام‌های `left` و `right` استفاده می‌شود:
* `left` از ابتدای آرایه شروع به حرکت می‌کند تا به یک عنصر بزرگتر یا مساوی محور برسد.
* `right` از انتهای آرایه شروع به حرکت می‌کند تا به یک عنصر کوچکتر یا مساوی محور برسد.
* هنگامی که `left` و `right` هر دو متوقف شدند (یعنی `left` به یک عنصر بزرگتر یا مساوی محور و `right` به یک عنصر کوچکتر یا مساوی محور رسیدند)، عناصر واقع در این دو موقعیت با یکدیگر **جابجا (swap)** می‌شوند.
* این فرآیند تا زمانی که `left` و `right` از یکدیگر عبور کنند (یعنی `left >= right`) ادامه می‌یابد.
* در پایان فرآیند بخش‌بندی، محور در موقعیت نهایی خود قرار می‌گیرد و تمام عناصر کوچکتر از آن در سمت چپ و تمام عناصر بزرگتر از آن در سمت راست آن قرار دارند.

**3. تقسیم و غلبه (Divide and Conquer):**

* اکنون آرایه به دو زیرآرایه تقسیم شده است:
* زیرآرایه سمت چپ محور (عناصر کوچکتر از محور)
* زیرآرایه سمت راست محور (عناصر بزرگتر از محور)
* الگوریتم مرتب‌سازی سریع به صورت **بازگشتی (recursive)** بر روی هر یک از این زیرآرایه‌ها اعمال می‌شود. این بدان معناست که فرآیندهای انتخاب محور و بخش‌بندی برای هر زیرآرایه تکرار می‌شوند تا زمانی که اندازه زیرآرایه‌ها به 1 برسد (یا 0 شود)، که در این صورت مرتب شده در نظر گرفته می‌شوند.

**4. ترکیب (Combine):**

* نیازی به ترکیب صریح نیست، زیرا در طول فرآیند بخش‌بندی، عناصر در جای درست خود قرار گرفته‌اند و مرتب‌سازی درجا (in-place) انجام می‌شود.

**مثال:**

فرض کنید آرایه زیر را داریم:

`[7, 2, 1, 6, 8, 5, 3, 4]`

1. **انتخاب محور:** فرض می‌کنیم اولین عنصر (7) به عنوان محور انتخاب شود.

2. **بخش‌بندی:**
* `left` از ابتدای آرایه (7) شروع می‌کند.
* `right` از انتهای آرایه (4) شروع می‌کند.
* `left` به 7 می‌رسد (که بزرگتر یا مساوی محور است).
* `right` به 4 می‌رسد (که کوچکتر از محور است).
* 7 و 4 با یکدیگر جابجا می‌شوند: `[4, 2, 1, 6, 8, 5, 3, 7]`
* `left` به سمت راست حرکت می‌کند، به 2 می‌رسد.
* `right` به سمت چپ حرکت می‌کند، به 3 می‌رسد.
* 2 و 3 با یکدیگر جابجا می‌شوند: `[4, 3, 1, 6, 8, 5, 2, 7]`
* `left` به سمت راست حرکت می‌کند، به 1 می‌رسد.
* `right` به سمت چپ حرکت می‌کند، به 5 می‌رسد.
* 1 و 5 با یکدیگر جابجا می‌شوند: `[4, 3, 5, 6, 8, 1, 2, 7]`
* `left` به سمت راست حرکت می‌کند، به 6 می‌رسد.
* `right` به سمت چپ حرکت می‌کند، به 8 می‌رسد.
* 6 و 8 با یکدیگر جابجا می‌شوند: `[4, 3, 5, 8, 6, 1, 2, 7]`
* `left` به سمت راست حرکت می‌کند، به 8 می‌رسد.
* `right` به سمت چپ حرکت می‌کند، به 2 می‌رسد.
* 2 و 8 با یکدیگر جابجا می‌شوند: `[4, 3, 5, 2, 6, 1, 8, 7]`
* `left` به سمت راست حرکت می‌کند، به 6 می‌رسد.
* `right` به سمت چپ حرکت می‌کند، به 1 می‌رسد.
* 1 و 6 با یکدیگر جابجا می‌شوند: `[4, 3, 5, 2, 1, 6, 8, 7]`
* `left` به سمت راست حرکت می‌کند، به 6 می‌رسد.
* `right` به سمت چپ حرکت می‌کند، به 7 می‌رسد.
* از آنجا که `left > right`، فرآیند بخش‌بندی پایان می‌یابد.

3. **جابجایی محور:** اکنون باید محور (7) را با عنصری که `right` به آن اشاره می‌کند (1) جابجا کنیم: `[4, 3, 5, 2, 1, 7, 8, 6]`

4. **تقسیم و غلبه:**
* الگوریتم مرتب‌سازی سریع به صورت بازگشتی بر روی زیرآرایه سمت چپ ( `[4, 3, 5, 2, 1]`) و زیرآرایه سمت راست (`[8, 6]`) اعمال می‌شود.

**ویژگی‌ها:**

* **پیچیدگی زمانی:**
* **بهترین و متوسط:** O(n log n)
* **بدترین:** O(n^2) (هنگامی که محور به طور مداوم بدترین انتخاب باشد، مانند زمانی که آرایه از قبل مرتب شده باشد و اولین عنصر به عنوان محور انتخاب شود.)
* **پیچیدگی فضایی:** O(log n) به طور متوسط (به دلیل فراخوانی‌های بازگشتی). در بدترین حالت O(n)
* **مرتب‌سازی درجا (in-place):** بله (به جز سربار ناشی از فراخوانی‌های بازگشتی)
* **ناپایدار (unstable):** به طور کلی ناپایدار است، به این معنی که ترتیب عناصر با مقادیر مساوی ممکن است حفظ نشود.

**مزایا:**

* به طور کلی یکی از سریعترین الگوریتم‌های مرتب‌سازی برای آرایه‌های بزرگ است.
* نسبتاً ساده برای پیاده‌سازی است.
* مرتب‌سازی درجا است.

**معایب:**

* پیچیدگی زمانی در بدترین حالت O(n^2) است.
* ناپایدار است.
* عملکرد آن به شدت به انتخاب محور بستگی دارد.

**بهینه‌سازی‌ها:**

* **انتخاب محور بهتر:** استفاده از استراتژی‌های انتخاب محور مانند "میانه سه عنصر" می‌تواند به جلوگیری از بدترین حالت کمک کند.
* **مرتب‌سازی درجی (Insertion Sort) برای زیرآرایه‌های کوچک:** برای زیرآرایه‌های کوچکتر از یک اندازه مشخص، مرتب‌سازی درجی (که برای آرایه‌های کوچک کارآمدتر است) می‌تواند به جای مرتب‌سازی سریع استفاده شود. این به دلیل سربار فراخوانی‌های بازگشتی در مرتب‌سازی سریع است.
* **مرتب‌سازی سریع سه‌طرفه (3-way Quick Sort):** این نوع مرتب‌سازی سریع، برای آرایه‌هایی که حاوی تعداد زیادی عناصر تکراری هستند، کارآمدتر است.

امیدوارم این توضیح جامع باشد.