پاورپوینت مرتب سازی سریع ساختمان داده ها و الگوریتمها

مرتب سازی سریع Quicksort
ساختمان داده ها و الگوریتمها

Quicksort
Hoare در سال 1962 پیشنهاد کرده است
از روش تقسیم و حل (Divide & Conquer) استفاده می کند
آرایه را به صورت “در جا” (In Place)مرتب می کند
شبیه مرتب سازی درجی(Insertion Sort) است.
برخلاف (Merge Sort ) به حافظه اضافی نیاز ندارد.
پیاده سازی های سریعی که برای آن ارائه شده، باعث بکارگیری وسیع آن در عمل شده است.

تقسیم و حل
تقسیم:یک عضو مثل x از آرایه را انتخاب کرده و آرایه را طوری به دو بخش طوری تقسیم می کنیم که یک بخش آن از x کوچکتر و بخش دیگر از x بزرگتر باشند.
حل: به صورت بازگشتی هر کدام از این دو بخش را مرتب می کنیم
ترکیب: کارخاصی لازم نیست!
نکته: هزینه عمل تقسیم خطی است Θ(n)

تقسیم
PARTITION(A, p, q)// A[p. . q]
x←A[p] // pivot= A[p]
i←p
for j←p+ 1 to q
do if A[j] ≤x
then i←i+ 1
swap A[i] ↔A[j]
swap A[p] ↔A[i] // final place of pivot!
return i

مثال

مثال

مثال

مثال

مثال

مثال

مثال

مثال

مثال

مثال

شبه کد الگوریتم مرتب سازی
QUICKSORT(A, p, r)
if p< r
then q←PARTITION(A, p, r)
QUICKSORT(A, p, q–1)
QUICKSORT(A, q+1, r)

Initial call:QUICKSORT(A, 1, n)

آنالیز الگوریتم
فرض کنید تمام اعضای آرایه غیر تکراری هستند.
در عمل معمولا روشهای مناسبتری برای تقسیم آرایه هایی که اعضای تکراری دارند، استفاده می شود
فرض کنید T(n) هزینه مرتب سازی آرایه ای به طول n با استفاده ازاین الگوریتم در بدترین حالت باشد.
معمولا بهترین حالت الگوریتمها را در نظر نمی گیریم اما برای مرتب سازی سریع این حالت را نیز بررسی می کنیم.

بدترین حالات quicksort
آرایه از قبل مرتب شده باشد.
تقسیم حول مقدار مینیمم یا ماکزیمم صورت گیرد.
یکی از دو بخش بدست آمده از تقسیم، هیچ عضوی نداشته باشد.
T(n) = T(0) + T(n-1) + Θ(n) = Θ(1) + T(n -1) + Θ(n) = T(n-1) + Θ(n)  n + n-1+ …+1 = Θ(n2)

درخت هزینه بدترین حالت

درخت هزینه بدترین حالت

درخت هزینه بدترین حالت

درخت هزینه بدترین حالت

درخت هزینه بدترین حالت

درخت هزینه بدترین حالت

درخت هزینه بدترین حالت

بهترین حالت
در بهترین حالت، دو بخش تقسیم شده تقریبا هم اندازه هستند و اندازه مساله در هر بار تقسیم نصف می شود:
T(n) = 2T(n/2) + Θ(n)  Θ(n log n) (mergesort)

سوال: اگر تقسیم طوری صورت بگیرد که 90% اعضای آرایه در یک بخش و %10 در بخش دیگر قرار بگیرند، هزینه الگوریم چگونه خواهد بود ؟
T(n) = T(n/10) + T(9n/10)+ Θ(n)

10% 90%

10% 90%

10% 90%

10% 90%

10% 90%

10% 90%

10% 90%

حالتی دیگر
فرض کنید، به صورت متوالی در هربار تقسیم، آرایه بطور متوازن و نامتوازن تقسیم شود. حالت متوازن را Lucky و حالت نا متوازن را unlucky می نامیم و هزینه الگوریتم را محاسبه می کنیم
L(n) = 2U(n/2) + Θ(n)  Lucky step
U(n) = L(n -1) + Θ(n)  Unlucky step
L(n) = 2(L(n/2-1) + Θ(n/2)) + Θ(n)
L(n) = 2L(n/2 -1) + Θ(n)  L(n) = Θ(nlogn)

Randomized Quicksort
عمل تقسیم نقش اصلی را در تعیین هزینه الگوریتم دارد
چگونه تقسیم متوازنی انجام دهیم؟
یا، چگونه می توانیم امیدوار باشیم اغلب تقسیم ها متوازن هستند؟
انتخاب تصادفی عضو نشانگر pivot
زمان اجرا مستقل از مقادیر و توزیع ورودیهاست
هیچ ورودی خاصی سبب شکل گیری بدترین حالت الگوریتم نمی شود
احتمال وقوع بدترین حالت تنها به مولد اعداد (شبه) تصادفی بستگی دارد

شبه کد الگوریتم تقسیم تصادفی
RANDOM-PARTITION(A, p, q)// A[p. . q]
k ← random-number (p..q)
swap A[p] , A[k]
x←A[p] // pivot= A[p]
i←p
for j←p+ 1 to q
do if A[j] ≤x
then i←i+ 1
swap A[i] ↔A[j]
swap A[p] ↔A[i] // final place of pivot!
return i

آنالیز مرتب سازی با تقسیم تصادفی
با انتخاب تصادفی نشانگر؛ آرایه ای به طول n ممکن است به صورت {0:n-1} ; {1,n-2}; …; {n/2 :n/2} تقسیم شود.
فرض کنید الگوریتم تقسیم دو بخش k:n-k-1 را تولید می کند که در آن k=0,1,…, n-1 است.
متغیر تصادفی Xk را چنین تعریف می کنیم:
Xk=1 اگر طول دوبخش k:n-k-1 باشد؛ در غیر اینصورت، Xk =0.
Xk را متغیر تصادفی نشانگر (Indicator Random Variable)می گویند.
E[Xk] = P(Xk =1) = 1/n

آنالیز مرتب سازی با تقسیم تصادفی
هزینه، برابربا امید ریاضی تابع تصادفی T(n) است: هزینه = E[T(n)]

آنالیز مرتب سازی با تقسیم تصادفی
جایگذاری
امید ریاضی،
تابعی خطی است
Xk و T(k) از هم مستقل هستند
E(Xk) = 1/n

آنالیز مرتب سازی با تقسیم تصادفی
if k=0 or k =1  E(T(K)) = 2/nΘ(n2) = Θ(n)

آنالیز مرتب سازی با تقسیم تصادفی
حدس می زنیم، هزینه الگوریتم از مرتبه n log n باشد. برای اثبات این حدس باید نشان دهیم:
ثابت a را می توان یافت، بنحوی که:
E(T(n)) <= a n log n
بعنوان تمرین ثابت کنید

آنالیز مرتب سازی با تقسیم تصادفی
جایگذاری حدس برای هر کدام از جملات سری
جایگذاری رابطه قبلی به جای سری بالا

آنالیز مرتب سازی با تقسیم تصادفی
E(T(n)) <= a n log n if an/4 > Θ(n)
پس، با انتخاب مناسب a می توان کران بالایی از مرتبه n log n پیدا کرد.
E(T(n)) = Θ(n log n)

بحث و بررسی
الگوریتم quicksort تصادفی، از نظر هزینه با mergesort هم رتبه است.
چون نیازی به حافظه اضافی ندارد، معمولا انتخاب اول برای مرتب سازی است.
در عمل این الگوریتم بین 3 تا 9 برابر سریعتر از mergesort اجرا می شود.

تمرین
در پروژه 1، مقایسه الگوریتم های مرتب سازی، quicksort معمولی و تصادفی را نیز پیاده سازی کرده، با بقیه مقایسه کنید.
مسایل 7-1 تا 7-5 را حل و ارسال کنید