لینک دانلود و خرید پایین توضیحات
دسته بندی : پاورپوینت
نوع فایل : .ppt ( قابل ویرایش و آماده پرینت )
تعداد اسلاید : 44 اسلاید
قسمتی از متن .ppt :
مرتب سازی سریع Quicksort
ساختمان داده ها و الگوریتمها
Quicksort
Hoare در سال 1962 پیشنهاد کرده است
از روش تقسیم و حل (Divide & Conquer) استفاده می کند
آرایه را به صورت “در جا” (In Place)مرتب می کند
شبیه مرتب سازی درجی(Insertion Sort) است.
برخلاف (Merge Sort ) به حافظه اضافی نیاز ندارد.
پیاده سازی های سریعی که برای آن ارائه شده، باعث بکارگیری وسیع آن در عمل شده است.
تقسیم و حل
تقسیم:یک عضو مثل x از آرایه را انتخاب کرده و آرایه را طوری به دو بخش طوری تقسیم می کنیم که یک بخش آن از x کوچکتر و بخش دیگر از x بزرگتر باشند.
حل: به صورت بازگشتی هر کدام از این دو بخش را مرتب می کنیم
ترکیب: کارخاصی لازم نیست!
نکته: هزینه عمل تقسیم خطی است Θ(n)
شبه کد الگوریتم مرتب سازی
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
درخت هزینه بدترین حالت
حالتی دیگر
Randomized Quicksort
انتخاب تصادفی عضو نشانگر pivot
شبه کد الگوریتم تقسیم تصادفی
آنالیز مرتب سازی با تقسیم تصادفی
بحث و بررسی
