مرجع دانلود پاورپوینت های درسی

حجم فایل : 84.8 KB
نوع فایل : پاور پوینت
تعداد اسلاید ها : 28
بنام خدا Sorting Algorithms
2 Quicksort الگوريتم کلي quicksort
يکي از عناصر را به عنوان محور انتخاب کنيد.
عناصر را به دو زير مجموعه چپ و راست تقسيم کنيد.
تمام عناصر زير مجموعه سمت چپ از محور کوچکتر هستند.
تمام عناصر زير مجموعه سمت رلست از محور يزرگتر هستند.
الگوريتم را براي زير مجموعه هاي بدست آمده تکرار کنيد.
نيازي به ادغام نداريم
محور در هر مرحله سر جاي درست خود قرار دارد. Quicksort void quicksort(int* arrayOfInts, int first, int last)
{
int pivot;
if (first < last)
{
pivot = partition(arrayOfInts, first, last);
quicksort(arrayOfInts,first,pivot-1);
quicksort(arrayOfInts,pivot+1,last);
}
}
Quicksort int partition(int* arrayOfInts, int first, int last)
{
int temp;
int p = first; // set pivot = first index
for (int k = first+1; k <= last; k++) // for every other indx
{
if (arrayOfInts[k] <= arrayOfInts[first]) // if data is smaller
{
p = p + 1; // update final pivot location
swap(arrayOfInts[k], arrayOfInts[p]);
}
}
swap(arrayOfInts[p], arrayOfInts[first]);
return p;
}
Partition Step Through partition(cards, 0, 4)
P = 0 K = 1 P = 1 K = 3
cards[1] < cards[0] ? No cards[3] < cards[0]? Yes
P = 2
P = 0 K = 2 temp = cards[3]
cards[2] < cards[0] ? Yes cards[3] = cards[2]
P = 1 cards[2] = cards[3]
temp = cards[2] P = 2 K = 4
cards[2] = cards[1] cards[4] < cards[0]? No
cards[1] = temp
temp = cards[2], cards[2] = cards[first]
cards[first] = temp, return p = 2;

Complexity of Quicksort بدترين حالت: O(n2)
بدترين حالت کي اتفاق مي افتد؟
ليست مرتب يا تقريبا مرتب
زير مجموعه هاي بدست آمده نامتعادل خواهند شد.

در حالت متوسط پيچيدگي برابر O(n log2n) است حالت متوسط اين الگوريتم حالت غالب است Complexity of Quicksort رابطه بازگشتي: (حالت متوسط)
2 زير مساله داريم.
اگر محور خوب باشد سايز هر کدام ½ مساله اصلي است.
هزينه تابع partition برابر O(n)است.

a = 2 b = 2 k = 1
2 = 21
تئوري master: O(nlog2n) Complexity of Quicksort رابطه بازگشتي: (بدترين حالت)

دو زير مجموعه با سايز هاي 1 و n-1 خواهيم داشت.
نمي شود از تئوري master استفاده کرد. چون b يعني اندازه زير مسائل ثابت نيست.
n-1/n n-2/n-1 n-3/n-2
اما مي شود اعداد را با هم جم...