آنچه می‌خوانید ویراست جدید نوشته‌ای است که اولین بار با عنوان «مرتب سازی سریع»
دی ماه ۱۳۸۵
از طریق وبگاه برنامه‌نویسی و طراحی الگوریتم (عنوان و طرح پیشین وبگاه الگوریتمستان)
منتشر شده بود.
روش مرتب‌سازی سریع (Quick Sort) یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:
1- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) - به عنوان مثال عنصر اول - انتخاب می‌شود.
2- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده می‌شود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.
3- مرتب‌سازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع مرتب می‌شوند.
پیاده‌سازی تقسیم آرایه
[بازگشت به فهرست]
با استفاده از تابع زیر - با فرض انتخاب عنصر اول به عنوان محور - میتوان مرحله‌ی تقسیم آرایه را پیاده‌سازی کرد:
| 1 | int partition(int arr[], int low, int high){
|
| 2 | int left = low + 1, right = high, temp, pivot = arr[low];
|
| 3 | while(left <= right){
|
| 4 | while(arr[left] <= pivot && left <= right)
|
| 5 | left++;
|
| 6 | while(arr[right] > pivot && left <= right)
|
| 7 | right--;
|
| 8 | if(left < right){
|
| 9 | temp = arr[left];
|
| 10 | arr[left] = arr[right];
|
| 11 | arr[right] = temp;
|
| 12 | }
|
| 13 | }
|
| 14 | arr[low] = arr[right];
|
| 15 | arr[right] = pivot;
|
| 16 | return right;
|
| 17 | } |
| 1 | def partition(arr, low, high):
|
| 2 | left, right, pivot = low + 1, high, arr[low]
|
| 3 | while left <= right:
|
| 4 | while arr[left] <= pivot and left <= right:
|
| 5 | left += 1
|
| 6 | while arr[right] > pivot and left <= right:
|
| 7 | right -= 1
|
| 8 | if left < right:
|
| 9 | arr[left], arr[right] = arr[right], arr[left]
|
| 10 | arr[low] = arr[right]
|
| 11 | arr[right] = pivot
|
| 12 | return right |
تابع partition آرایه‌ی arr و اندیس بازه‌ی مورد نظر از آرایه جهت مرتب‌سازی را با low و high دریافت می‌کند. در متغیر pivot مقدار عنصر ابتدای بازه به عنوان عنصر محوری ذخیره می‌شود. همینطور در متغیر left اندیس عنصر دوم - اولین عنصر غیر محور بازه - و در متغیر right اندیس عنصر آخر ذخیره می‌شوند.
حلقه‌ی بیرونی تا زمانی که اندیس left کوچکتر یا مساوی اندیس right است تکرار خواهد شد. در این حلقه جابجایی‌های لازم برای قرار گرفتن عنصر محوری در محل صحیح خود صورت می‌گیرد. حلقه‌ی درونی اول مقدار اندیس left را تا جایی که مقدار آن کمتر یا مساوی right بوده و مقدار عنصر متناظر آن در آرایه کمتر یا مساوی محور باشد افزایش می‌دهد. به همین ترتیب حلقه‌ی بعدی مقدار اندیس right را تا جایی که مقدار آن بیشتر یا مساوی left بوده و مقدار عنصر متناظر آن در آرایه بیشتر از عنصر محوری باشد کاهش می‌دهد. در انتها اگر left کوچکتر از right باشد مقدار متناظر آنها در آرایه جابجا می‌شود. چرا که بر اساس عملکرد دو حلقه‌ی درونی، اندیس left محل اولین عنصر بزرگتر از محور از ابتدای بازه و اندیس right محل اولین عنصر کوچکتر از محور از انتهای بازه را مشخص می‌کند. اگر این شرط برقرار نباشد به معنی آن است که تمامی عناصر بزرگتر از محور در سمت راست و تمامی عناصر کوچکتر از محور در سمت چپ بازه جمع شده‌اند (چرا؟). در پایان مقدار محور با مقدار حد فاصل دو زیرآرایه جابجا شده و اندیس محل محور به عنوان محل تقسیم دو زیرآرایه از تابع بازگشت داده می‌شود.
این تابع را روی یک آرایه‌ی هفت عنصری از اعداد صحیح بررسی می‌کنیم:
3 0 6 1 7 2 5
تابع به صورت (partition(arr, 0, 6 فراخوانی می‌شود:
3 0 6 1 7 2 5: pivot = 3, left = 1, right = 6
شرط left < right برقرار است. پس وارد حلقه شده و حلقه‌های درونی اجرا می‌شوند. پس از اجرای حلقه‌ها مقدار left و right به اندیس دو و پنج تغییر می‌کنند و مقادیر متناظر آنها جابجا می‌شوند:
3 0 2 1 7 6 5: pivot = 3, left = 2, right = 5
شرط left < right همچنان برقرار است. حلقه‌های درونی مقدار left و right را به چهار و سه تغییر می‌دهند. اما چون left < right نیست جابجایی انجام نمی‌شود:
3 0 2 1 7 6 5: pivot = 3, left = 4, right = 3
با نادرست بودن شرط left < right از حلقه‌ی بیرونی نیز خارج شده و به دستورات جابجایی نهایی می‌رسیم:
1 0 2 3 7 6 5
عنصر محوری جابجا شده است. در این حالت عدد سه به طور قطع در محل اصلی خود پس از مرتب‌سازی قرار دارد. چرا که تمامی عناصر زیرآرایه‌ی چپ از آن کوچکتر و تمامی عناصر زیرآرایه‌ی راست از آن بزرگتر هستند. این بازه‌ها هر تغییری در چینش داشته باشند، تاثیری در محل عدد سه نخواهند داشت.
پیاده‌سازی مرتب‌سازی سریع
[بازگشت به فهرست]
در مرحله‌ی بعدی از الگوریتم مرتب‌سازی سریع، دو زیرآرایه‌ی چپ و راست به صورت بازگشتی مرتب می‌شوند:
| 1 | void quick_sort(int arr[], int low, int high){
|
| 2 | if(low < high){
|
| 3 | int pivot = partition(arr, low, high);
|
| 4 | quick_sort(arr, low, pivot - 1);
|
| 5 | quick_sort(arr, pivot + 1, high);
|
| 6 | }
|
| 7 | } |
| 1 | def quick_sort(arr, low, high):
|
| 2 | if low >= high:
|
| 3 | return
|
| 4 | pivot = partition(arr, low, high)
|
| 5 | quick_sort(arr, low, pivot - 1)
|
| 6 | quick_sort(arr, pivot + 1, high) |
تابع quick_sort آرایه و بازه‌ی مورد نظر برای مرتب‌سازی را دریافت کرده، پس از تقسیم آرایه و مشخص شدن محل عنصر محوری، دو زیرآرایه‌ی چپ و راست را با فراخوانی بازگشتی حل می‌کند. توجه داشته باشید که در این تابع pivot اندیس عنصر محوری را در خود ذخیره می‌کند. در تابع partition این متغیر مقدار عنصر محوری را ذخیره می‌کرد.
در مثال فوق وضعیت آرایه پس از اجرای دستور تقسیم آرایه در هر فراخوانی به صورت زیر خواهد بود:
0) 3 0 6 1 7 2 5: low = 0, high = 6
1) quick_sort(arr, 0, 6 ) -> 1 0 2 3 7 6 5, pivot = 3
2) quick_sort(arr, 0, 2 ) -> 0 1 2 3 7 6 5, pivot = 1
3) quick_sort(arr, 0, 0 ) -> 0 1 2 3 7 6 5
4) quick_sort(arr, 2, 2 ) -> 0 1 2 3 7 6 5
5) quick_sort(arr, 4, 6 ) -> 0 1 2 3 5 6 7, pivot = 6
6) quick_sort(arr, 4, 5 ) -> 0 1 2 3 5 6 7, pivot = 4
7) quick_sort(arr, 5, 5 ) -> 0 1 2 3 5 6 7
در پایان آرایه مرتب شده است.
پیچیدگی زمانی مرتب‌سازی سریع
[بازگشت به فهرست]
در مرتب‌سازی‌های مبتنی بر مقایسه عموما تعداد مقایسه‌ها ملاک بررسی پیچیدگی زمانی است. $T(n)$ را تعداد مقایسه‌های لازم برای مرتب کردن آرایه‌ای به طول $n$ با روش مرتب‌سازی سریع در نظر می‌گیریم. تابع partition برای تقسیم‌بندی بازه‌ای به طول $n$ به غیر از عنصر محوری تمامی عناصر را مقایسه می‌کند و به $n - 1$ مقایسه نیاز دارد.
بهترین حالت قرار گرفتن عنصر محوری زمانی است که این عنصر در وسط بازه قرار بگیرد و آن بازه را به دو بازه با اندازه‌ی تقریبا برابر تقسیم کند. در این حالت هر زیربازه $ T(\frac{n}{2}) $ مقایسه نیاز خواهد داشت و میتوان نوشت:
\[T(n) = 2 T(\frac{n}{2}) + n - 1 \]
با استفاده از قضیه‌ی اصلی یا حل رابطه‌ی بازگشتی مشخص می‌شود که $T(n)$ از مرتبه‌ی اجرای $ \theta (n log n)$ است.
در بدترین حالت عنصر محوری در یک سوی بازه قرار گرفته و تمامی عناصر دیگر در یک سمت آن جمع می‌شوند. این حالت زمانی اتفاق می‌افتد که بازه از قبل به صورت نزولی یا صعودی مرتب باشد. در نتیجه یک زیربازه از اندازه‌ی صفر و یک زیربازه از اندازه‌ی $n - 1$ تولید خواهد شد:
\[T(n) = T(0) + T(n - 1) + n - 1 = T(n - 1) + n - 1 \]
حل این رابطه‌ی بازگشتی نشان از مرتبه‌ی اجرایی $ \theta(n^2)$ در بدترین حالت اجرای الگوریتم دارد.
ویژگی‌های مرتب‌سازی سریع
[بازگشت به فهرست]
1- پیچیدگی زمانی اجرای الگوریتم در بهترین حالت $ \theta(n log n)$ و در بدترین حالت $ \theta (n^2)$ است. با استفاده محاسبات ریاضی میتوان نشان داد در حالت متوسط نیز مرتبه‌ی اجرا $ \theta (n log n)$ است.
2- این الگوریتم یک مرتب‌سازی درجا است. یعنی میزان حافظه‌ی مصرفی الگوریتم مستقل از طول آرایه است.
3- زمانی که تعداد عناصر آرایه کم باشد، سرعت اجرای مرتب‌سازی درجی بهتر از مرتب‌سازی سریع است. به همین دلیل طی مراحل بازگشتی مرتب‌سازی سریع، اگر طول بازه عدد کوچکی باشد، معمولا بازه با مرتب‌سازی درجی مرتب می‌شود.
4- الگوریتم مرتب‌سازی سریع با پیاده‌سازی فوق یک روش ناپایدار است. چنین الگوریتمی لزوما ترتیب عناصر با مقدار یکسان را پس از مرتب‌سازی حفظ نمی‌کند.
5- انتخاب عنصر محوری بحث مفصلی دارد. اما در کل یک انتخاب آزاد است. میتوان عنصر اول، عنصر آخر، یا هر عنصر دیگری را به عنوان عنصر محوری انتخاب کرد. حتی لازم نیست از ابتدا تا انتها از یک روش انتخاب استفاده کرد. یکی از روش‌های رایج، انتخاب یک عنصر تصادفی به عنوان عنصر محوری است. اگرچه انتخاب عنصر محوری مناسب باعث بالا رفتن کارایی الگوریتم می‌شود، اما عموما هزینه‌ی لازم برای یافتن چنین محوری بالا بوده و مقرون به صرفه نیست.