پاور پوینت درموردمرتب سازی سریع Quicksort
نوع فایل : پاورپوینت( Power Point )قابل ویرایش
تعداداسلایدها :44 اسلاید
بخشی ازاسلایدها:
lHoare در سال 1962 پیشنهاد کرده است
lاز روش تقسیم و حل (Divide & Conquer) استفاده می کند
lآرایه را به صورت “در جا” (In Place)مرتب می کند
–شبیه مرتب سازی درجی(Insertion Sort) است.
–برخلاف (Merge Sort ) به حافظه اضافی نیاز ندارد.
lپیاده سازی های سریعی که برای آن ارائه شده، باعث بکارگیری وسیع آن در عمل شده است.
.1تقسیم:یک عضو مثل x از آرایه را انتخاب کرده و آرایه را طوری به دو بخش طوری تقسیم می کنیم که یک بخش آن از x کوچکتر و بخش دیگر از x بزرگتر باشند.
.2حل: به صورت بازگشتی هر کدام از این دو بخش را مرتب می کنیم
.3ترکیب: کارخاصی لازم نیست!
نکته: هزینه عمل تقسیم خطی است Θ(n)
●
lفرض کنید تمام اعضای آرایه غیر تکراری هستند.
lدر عمل معمولا روشهای مناسبتری برای تقسیم آرایه هایی که اعضای تکراری دارند، استفاده می شود
lفرض کنید T(n) هزینه مرتب سازی آرایه ای به طول n با استفاده ازاین الگوریتم در بدترین حالت باشد.
lمعمولا بهترین حالت الگوریتمها را در نظر نمی گیریم اما برای مرتب سازی سریع این حالت را نیز بررسی می کنیم.
l
lدر بهترین حالت، دو بخش تقسیم شده تقریبا هم اندازه هستند و اندازه مساله در هر بار تقسیم نصف می شود:
T(n) = 2T(n/2) + Θ(n) à Θ(n log n) (mergesort)
l
lسوال: اگر تقسیم طوری صورت بگیرد که 90% اعضای آرایه در یک بخش و %10 در بخش دیگر قرار بگیرند، هزینه الگوریم چگونه خواهد بود ؟
lT(n) = T(n/10) + T(9n/10)+ Θ(n)
lفرض کنید، به صورت متوالی در هربار تقسیم، آرایه بطور متوازن و نامتوازن تقسیم شود. حالت متوازن را Lucky و حالت نا متوازن را unlucky می نامیم و هزینه الگوریتم را محاسبه می کنیم
lL(n) = 2U(n/2) + Θ(n) à Lucky step
lU(n) = L(n -1) + Θ(n) à Unlucky step
lL(n) = 2(L(n/2-1) + Θ(n/2)) + Θ(n)
lL(n) = 2L(n/2 -1) + Θ(n) à L(n) = Θ(nlogn)
lعمل تقسیم نقش اصلی را در تعیین هزینه الگوریتم دارد
–چگونه تقسیم متوازنی انجام دهیم؟
– یا، چگونه می توانیم امیدوار باشیم اغلب تقسیم ها متوازن هستند؟
lانتخاب تصادفی عضو نشانگر pivot
–زمان اجرا مستقل از مقادیر و توزیع ورودیهاست
–هیچ ورودی خاصی سبب شکل گیری بدترین حالت الگوریتم نمی شود
–احتمال وقوع بدترین حالت تنها به مولد اعداد (شبه) تصادفی بستگی دارد
آنالیز مرتب سازی با تقسیم تصادفی
lبا انتخاب تصادفی نشانگر؛ آرایه ای به طول n ممکن است به صورت
{0:n-1} ; {1,n-2}; …; {n/2 :n/2} تقسیم شود.
{0:n-1} ; {1,n-2}; …; {n/2 :n/2} تقسیم شود.
l فرض کنید الگوریتم تقسیم دو بخش k:n-k-1 را تولید می کند که در آن k=0,1,…, n-1 است.
lمتغیر تصادفی Xk را چنین تعریف می کنیم:
–Xk=1 اگر طول دوبخش k:n-k-1 باشد؛ در غیر اینصورت، Xk =0.
–Xk را متغیر تصادفی نشانگر (Indicator Random Variable)می گویند.
–E[Xk] = P(Xk =1) = 1/n