آموزش مرتب سازی سریع

فرض کنید به شما تعدادی از توپ های رنگی که در یک ردیف هر کدام در یک خانه جدا قرار گرفته اند داده اند و حال میگویند این توپ ها را به ترتیب رنگ های رنگین کمان مرتب کنید هر کسی به روشی این کار را انجام میدهد یکی تمام توپ ها را خالی میکند و به ترتیب از اول میچیند فرد دیگر توپ ها را نگاه کرده و جستجو میکند رنگ درخواستی را پیدا کرده و آن را با توپ خانه مورد نظر و ... جابه جا میکند در مرتب سازی آرایه ها هم روش های مختلفی وجود دارد عبارت اند از مرتب سازی انتخابی ، دودویی ، حبابی ، هرمی ، درجی و ...

که روش مرتب سازی سریع هم یکی از آن هاست که در این مقاله آموزش آن میپردازیم

روش مرتب‌سازی سریع (Quick Sort)یکی از الگوریتم‌های مشهور مرتب‌سازی داده‌ها است. این الگوریتم طی مراحل زیر که یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:

1- انتخاب عنصر محوری:

یکی از عناصر آرایه به عنوان عنصر محوری (pivot) معمولا عنصر اول است را انتخاب می‌شود.

2- تقسیم آرایه:

چینش عناصر آرایه به صورتی می‌شود که تمامی عناصر کوچکتر یا مساوی عنصر محوری در سمت چپ آن و تمامی عناصر بزرگتردر سمت راست آن قرار بگیرند. این دو قسمت ،زیر آرایه‌های چپ و راست نامیده می‌شوند.

3- مرتب‌سازی بازگشتی:

زیرآرایه‌های چپ و راست به روش مرتب‌سازی سریع به ترتیب مرتب می‌شوند. که در زیر عکس به توضیح ان میپردازیم:

حالا مرتب سازی به روش سریع رو به این ترتیب انجام میدهیم:

این مرحله شامل تقسیم آرایه است ، یک عضو آرایه را انتخاب میکنیم و اسم آن را عنصر محوری (pivot point) میگزاریم

و کلیه عناصری که از عنصر محوری کوچکتر هستند را سمت چپ عنصر محوری قرار میدهیم

و عناصر بزرگتر از عنصر محوری را در سمت راست قرار میدهیم.

اسم این رویه را partition میگذاریم که الگوریتم آن به زبان phpبه شکل زیر نوشته میشود:

<?php
$ pivot = $arr_beg;
$ higher = $arr_end;
while($pivot < $higher ) {
if($ar[$pivot] >$ ar[$pivot+1] ) {
$ temp=$ar[$pivot+1];
$ar[$pivot+1]=$ar[$pivot];
$ar[$pivot]=$temp;
$pivot++;
}
else {
$temp=$ar[$pivot+1];
$ar[$pivot+1]=$ar[$higher];
$ar[$higher]=$temp;
$higher--;
}
}
return $pivot;
}

اولین عنصر ارایه را به عنوان عنصر محوری در نظر میگیریم و اخرین عنصر ارایه را به عنوان بزرگترین عنصر higherدر نظر میگیریم هر بار در حلقه while شرط این است که مقایسه کند تا ببیند higher از عنصر محوری بزرگتر باشد تا دستور حلقه اجرا شوددر هر بار اجرای حلقه while عنصری از آرایه که در محل pivot قرار دارد با عنصر بعدی یعنی عنصر (pivot+1)مقایسه میکند و اگر ازآن بزرگتر باشد با آن جابجا میشه(مسلماً وقتی که این اتفاق بیفتد باید خود متغیر pivot هم که شماره عنصر محوری هست اصلاح بشود پس به اضافه یک میشود)و اگر بزرگتر نباشد با عنصر انتهای آرایه که با متغیر higher مشخص شده بود جابجا میشود و برای اینکه دفعه بعد عنصرانتهای آرایه دوباره جابجا نشود متغیر higher را یکی کم میکنیم.

در نهایت شرط انتهای حلقه این است که متغیر های pivot و higher با هم برابر شوند تا از حلقه خارج شود.

در این حالت آرایه به دو بخش تقسیم شده کهیک بخش از ((*arr_beg ((begin شروع و تا عنصر قبل از pivot بخش دیگر از عنصر بعد از pivot شروع میشه و تا arr_end ادامه داره.

دوباره هر دو بخش به همین روش مرتب و جابه جا میشوند تا کل ارایه به شکل مرتب شده در آید

<?php
function quick_sort($my_array) {
$loe = $gt = array();
if(count($my_array) < 2) {
return $my_array;
}
$pivot_key = key($my_array);
$pivot = array_shift($my_array);
foreach($my_array as $val) {
if($val <= $pivot) { $loe[ ] = $val;
}
elseif
($val > $pivot) { $gt[ ] = $val;
}
}
return array_merge(quick_sort($loe),array($pivot_key=>$pivot),quick_sort($gt));

}
$my_array = array(3, 0, 2, 5, -1, 4, 1);
echo 'Original Array : '.implode(',',$my_array).'\n';
$my_array = quick_sort($my_array);
echo 'Sorted Array : '.implode(',',$my_array);
?>

نکته ای که نباید فراموش کنید این است که محل عنصر محوری بعد از مرحله بازگشتی تغییری نمیکند برای همین در تابع quick_sort بعد از اینکه دو گروه کمتر از عنصر محوری و بیشتر از عنصر محوری، ساخته شدند، در بخشی که فراخوانی بازگشتی تابع quick_sort انجام میشود عنصر محوری در هیچکدام از مرتب سازی های بخشهای جدید تشکیل شده وجود ندارد.

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

1- این الگوریتم یک مرتب ‌سازی درجا است. یعنی میزان حافظه ای که الگوریتم مصرف میکند مستقل از طول آرایه است.

2- زمانی که تعداد عناصر آرایه کم باشد، سرعت اجرای مرتب سازی درجی بهتر از مرتب‌سازی سریع است. به همین دلیل طی مراحل بازگشتی مرتب‌سازی سریع، اگر طول بازه عدد کوچکی باشد، معمولا بازه با مرتب‌سازی درجی مرتب می‌شود.

3- انتخاب عنصر محوری بحث مفصلی تری دارد و همیشه عنصراول درنظر گرفته نمیشود اما در کل یک انتخاب آزاد است ومی‌توانید عنصر اول، عنصر آخر، یا هر عنصر دیگری را به عنوان عنصر محوری انتخاب کرد.حتی یکی از روش‌های رایج، انتخاب یک عنصربه صورت تصادفی به عنوان عنصر محوری است.

* اگرچه انتخاب عنصر محوری مناسب باعث بالا رفتن کارایی الگوریتم می‌شود، اما عموما هزینه‌ی لازم برای یافتن چنین محوری بالا بوده و مقرون به صرفه نیست.