Quick sort هم الگوریتمیه که از روش Divide and conquer استفاده می کنه یعنی ما مساله رو به صورت بازگشتی به مسایل کوچیکتر تقسیم می کنیم و وقتی که مساله به اندازه کافی کوچیک شد حل می کنیم و جواب هایی که بدست میاد رو ترکیب می کنیم تا جواب کامل رو داشته باشیم
توی Quick sort به این شکل عمل می کنیم که :
۱ـ یک عنصر به عنوان Pivot انتخاب می کنیم
۲ـ عناصری که از pivot کوچیکترن رو قبلش و عناصر بزرگتر رو بعد از اون قرار میدیم .(به این مرحله partition میگیم )
۳ـ وقتی که محل جدید pivot بدست آمد ما عملیات ۱ به بعد روبرای آرایه های سمت چپ و راست pivot تا زمانی که اندازه آرایه های سمت چپ و راست ۱ نشدن دوباره تکرار می کنیم .
مثلا این آرایه رو در نظر بگیرید : 4-6-5-3-1-7-8-2
فرض می کنیم که pivot رو همیشه به عنوان عنصر آخر در نظر بگیریم .
الگوریتم بعد از یک بار انجام مرحله partition به شکل زیر در میاد (همون طوری که از شکل مشخصه هر بار آرایه رو به قسمت های کوچکتر تقسیم میکنیم (devide) و روی قسمت های کوچیک تر partition انجام میشه (conquer) .)
partition هم به این شکل کار می کنه که ما اندیس شروع با اسم p (با مقدار اولیه start ) در نظر می گیریم شروع به پیمایش آرایه می کنیم هر وقت که یک عنصر کمتر از pivot ما وجود داشت خونه ی p ام رو با عنصری که کمتر بوده جابه جا می کنیم و p رو هم یک واحد اضافه می کنیم
نهایتا هم pivot رو با عنصر p ام جا به جا می کنیم ( عکس از کتاب CLRS )
کد سی پلاس پلاس Quick sort به این شکله :
#include <iostream>
using namespace std;
int partition(int* arr,int start,int end)
{
int pivotLocation=start;
int pivot=arr[end];//in ja be jaye end agar az median estefade konim behtar hast
for(int i=start;i<end;i++)
{
if(arr[i]<pivot)
{
swap(arr[pivotLocation],arr[i]);
pivotLocation++;
}
}
swap(arr[pivotLocation],arr[end]);
return pivotLocation;
}
void quickSort(int* arr,int start,int end)
{
if(start >= end)
return;
int pivotLocation=partition(arr,start,end);
quickSort(arr,start,pivotLocation-1);
quickSort(arr,pivotLocation+1,end);
}
int main ()
{
int arr[]={5,2,7,8,2,4,3,9};
quickSort(arr,0,7);
for(auto i:arr)
cout<<i;
return 0;
}
این الگوریتم زمانی بدترین حالتش رخ میده که تمام pivot هایی که انتخاب میشن در هر مرحله بزرگترین یا کوچیکترین عنصر باشن (یکی از جاهایی که رخ میده زمانی هستش که آرایه کاملا مرتب باشه )
برای بهتر انتخاب کردن pivot و جلوگیری از بدترین حالت از روش های آماری استفاده می کنن مثلا pivot روهر مرحله بصورت میانه ۳ تا عنصر از این آرایه در نظر می گیرن .