مرتبسازی سریع
از ویکیپدیا، دانشنامهٔ آزاد.
مرتبسازی سریع(به انگلیسی: Quicksort)، یکی از روشهای مرتبسازی آرایه است که بهدلیل مصرف حافظه کم، سرعت اجرای مناسب و پیادهسازی ساده بسیار مورد قبول واقع شدهاست.
فهرست مندرجات |
[ویرایش] پیاده سازی
هر پیاده سازی این الگوریتم بهصورت کلی از دو بخش تشکیل شدهاست. یک بخش تقسیمبندی آرایه (partition) و قسمت مرتب کردن.
[ویرایش] پیادهسازی به زبان سیپلاسپلاس
نمونهای از این پیاده سازی به زبان ++C به صورت زیر است
void quicksort(int array[] , int left , int right){
if (left < right){
int middle = partition(array , left , right) ;
quicksort(array , left , middle-۱) ;
quicksort(array , middle+۱ , right);
}
}
int partition(int array[] , int left , int right){
int middle ;
int x = array[left] ;
int l = left ;
int r = right ;
while(l < r){
while((array[l] <= x) && (l < right)) l++ ;
while((array[r] > x) && (r >= left)) r-- ;
if(l < r){
int temp = array[l];
array[l] = array[r];
array[r] = temp ;
}
}
middle = r ;
int temp = array[left];
array[left] = array[middle] ;
array[middle] = temp; return middle ; }
[ویرایش] پیادهسازی به زبان پاسکال
پیاده سازی مشابه ولی فشردهتر به زبان pascal به صورت زیر میتواند باشد
procedure Sort(l, r: Integer);
var i, j, x, y: integer;
begin
i := l; j := r; x := a[(l+r) DIV ۲];
repeat
while a[i] < x do i := i + ۱;
while x < a[j] do j := j - ۱;
if i <= j then
begin
y := a[i]; a[i] := a[j]; a[j] := y;
i := i + ۱; j := j - ۱;
end;
until i > j;
if l < j then Sort(l, j);
if i < r then Sort(i, r);
end;
}
[ویرایش] پیاده سازی به صورت تصادفی
در پیاده سازی الگوریتم quickSort به صورت Randomized تغییر اصلی در بخش Partition کردن آرایه رخ میدهد مه ما درایه a[i] x را به صورت تصادفی انتخاب میکنیم. تنها نکته مهم دراین زمینه این است که در این پیاده سازی باید دقت شود که انتخاب درایه جدید به قبلیها وابسته نشود و هر بار یک درایه جدید را اختیار نماید.
[ویرایش] پیاده سازی صنعتی
الگوریتم مرتب سازی در دنیای واقعی برای آرایه نسبتا کوچک مناسب نیست. به علاوه بخش پارتیشن خود نیز مشکل بزرگی در زمان اجرا میباشد. برای همین پیشنهاد میگردد برای آرایههایی از طول کمتر از ۷ از مرتب سازیهای دیگر مانند مرتب سازی درجی یا حبابی استفاده شود. به علاوه بجای پیاده سازی بخش partition به صورت عادی با احتمالاتی میتوان از میانه ۹ برای آرایههای بزرگ (بیش از ۴۰ درایه) و میانه ۳ برای ارایههای متوسط (کمتر از ۴۰ درایه) و عضو وسط برای آرایههای کوچک استفاده کرد. به علاوه در چنین پیاده سازیهایی ابتدا اعداد صفر (برای آرایه از اعداد مثبت) را ابتدا به شروع آرایه منتقل میکنند. و همچنین درایههای غیر عددی را نیز هندل میکنند تا در اجرای الگوریتم اختلالی به وجود نیاورد.
برای توضیحات بیشتر درباره نسخههای بهینه مرتب سازی سریع میتوانید به مرجع بنتلی و مک ایلوری مراجعه نمایید. پیاده سازی بسیار خوبی از این الگوریتم را میتوانید در کد منبع جاوا و در کلاس java.util.Array بیابید.
[ویرایش] زمان اجرا
مرتب سازی سریع چه در پیاده سازی عادی و چه در پیاده سازی احتمالی در حالت متوسط در زمان اجرای (O(n lgn اجرا میشود. چرا که رابطه بازگشتی T(n) = ۲T(n/۲) + Theta(n) x درباره آن صدق میکند. در بدترین حالت زمان اجرای این الگوریتم (Theta(n^۲\ است.
[ویرایش] مراجع
الگوریتم QuickSort را میتوان در هر مرجع داده ساختار و الگوریتم یافت. با این وجود مراجع زیر (به خصوص کتاب کناث) برای مطالعات بعدی توصیه میشود.
- D.E.Knuth «The Art of Computer Programming» Vol.۲
- Udi Manber , Introduction to Algorithms- A creative Approach
- CLRS , Introduction to Algorithms
- Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function


