پیاده سازی الگوریتم مرتب سازی سریع(Quick Sort)
سلام دوستان
من میخوام الگوریتم مرتب سازی سریع رو پیاده سازی کنم تو سی شارپ.
سرچ زدم تو اینترنت کدشو پیدا کردم اما اصن از نحوه کارش سر در نمیارم...یه کمی پیچیده است
public static void QuickSortRecursive(ref int[] data, int left, int right)
{
if (left < right)
{
int q = Partition(ref data, left, right);
QuickSortRecursive(ref data, left, q - 1);
QuickSortRecursive(ref data, q + 1, right);
}
}
private static int Partition(ref int[] data, int left, int right)
{
int pivot = data[right];
int temp;
int i = left;
for (int j = left; j < right; ++j)
{
if (data[j] <= pivot)
{
temp = data[j];
data[j] = data[i];
data[i] = temp;
i++;
}
}
data[right] = data[i];
data[i] = pivot;
return i;
}
کسی میتونه راهنمایی کنه که این کد چطوری کار میکنه؟!
1 پاسخ
ااین الگوریتم توی بحث طراحی الگوریتم جزء الگوریتمهای تقسیم و غلبه محسوب میشه...یعنی هر دفعه به قسمت های کوچکتر تقسیم میکنه و ریز ترین زیرمسئله ها رو حل میکنه و به حل مسئله اصلی می رسه.....
حالابریم سر الگوریتم مرتب سازی سریع یا quick sort.
اینجوریه که اول یه آرایه رو که به ما میدن رو اولین عددش رو به عنوان لولا یا Pivot انتخاب میکنیم بعد از عدد بعد لولا شروع میکنیم مقایسه با این لولا. اگر کوچکتر از لولا بود میاد پشت لولا و لولا میره جلو یدونه اگرم که بزرگتر بود که سرجاش میمونه..حالا دو تا آرایه داریم و یه لولا که دقیقا سر جاش هست..حالا میریم قسمت عددهای قبل لولا و همین فرآیند رو اونجا تکرار میکنیم و همین فرآیند رو برای قسمت بعد از لولا انجام میدیم...حالا یه سری مباحث طراحی الگوریتمی راجع به الگوریتم پارتیشن بندی و انتخاب خود لولا هست که زیاد بدردت نمیخوره..ولی تعداد مقایسه های این الگوریتم توی بد ترین حالت 2/ [n(n-1)] هست...stable نیست این الگوریتم..