مرتب‌سازی سریع
از ویکی‌پدیا، دانشنامهٔ آزاد.
فهرست مندرجات |
[ویرایش] مرتب سازی سریع QuickSort
مرتب‌سازی سریع، یکی از روش‌های مرتب‌سازی آرایه است که به‌دلیل مصرف حافظه کم، سرعت اجرای مناسب و پیاده‌سازی ساده بسیار مورد قبول واقع شده است.
[ویرایش] پیاده سازی
هر پیاده سازی این الگوریتم به‌صورت کلی از دو بخش تشکیل شده است. یک بخش تقسیم‌بندی آرایه ( partition ) و قسمت مرتب کردن.
نمونه ای از این پیاده سازی به زبان ++C به صورت زیر است
void quicksort(int array[] , int left , int right){
if (left < right){
int middle = partition(array , left , right) ;
quicksort(array , left , middle-1) ;
quicksort(array , middle+1 , 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 2];
repeat while a[i] < x do i := i + 1;
while x < a[j] do j := j - 1;
if i <= j then
begin y := a[i]; a[i] := a[j]; a[j] := y;
i := i + 1; j := j - 1;
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 را به صورت تصادفی انتخاب می کنیم. تنها نکته مهم دراین زمینه این است که در این پیاده سازی باید دقت شود که انتخاب درایه جدید به قبلی ها وابسته نشود و هر بار یک درایه جدید را اختیار نماید.
[ویرایش] پیاده سازی صنعتی
الگوریتم مرتب سازی در دنیای واقعی برای آرایه نسبتا کوچک مناسب نیست. به علاوه بخش پارتیشن خود نیز مشکل بزرگی در زمان اجرا می باشد. برای همین پیشنهاد می گردد برای آرایه هایی از طول کمتر از 7 از مرتب سازی های دیگر مانند مرتب سازی درجی یا حبابی استفاده شود. به علاوه بجای پیاده سازی بخش partition به صورت عادی با احتمالاتی می توان از میانه 9 برای آرایه های بزرگ ( بیش از 40 درایه ) و میانه 3 برای ارایه های متوسط ( کمتر از 40 درایه ) و عضو وسط برای آرایه های کوچک استفاده کرد. به علاوه در چنین پیاده سازی هایی ابتدا اعداد صفر ( برای آرایه از اعداد مثبت ) را ابتدا به شروع آرایه منتقل می کنند. و همچنین درایه های غیر عددی را نیز هندل می کنند تا در اجرای الگوریتم اختلالی به وجود نیاورد.
برای توضیحات بیشتر درباره نسخه های بهینه مرتب سازی سریع می توانید به مرجع بنتلی و مک ایلوری مراجعه نمایید. پیاده سازی بسیار خوبی از این الگوریتم را می توانید در کد منبع جاوا و در کلاس java.util.Array بیابید.
[ویرایش] زمان اجرا
مرتب سازی سریع چه در پیاده سازی عادی و چه در پیاده سازی احتمالی در حالت متوسط در زمان اجرای ( O(n lgn اجرا می شود. چرا که رابطه بازگشتی T(n) = 2T(n/2) + Theta(n) x درباره آن صدق میکند. در بدترین حالت زمان اجرای این الگوریتم (Theta(n^2\ است.
[ویرایش] مراجع
الگوریتم QuickSort را می توان در هر مرجع داده ساختار و الگوریتم یافت. با این وجود مراجع زیر ( به خصوص کتاب کناث ) برای مطالعات بعدی توصیه می شود.
- D.E.Knuth "The Art of Computer Programming" Vol.2
- Udi Manber , Introduction to Algorithms- A creative Approach
- CLRS , Introduction to Algorithms
- Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function
