پاورپوینتی در مورد مرتب سازی سریع Quicksort

لینک دانلود و خرید پایین توضیحات

دسته بندی : پاورپوینت

نوع فایل :  .ppt ( قابل ویرایش و آماده پرینت )

تعداد اسلاید : 44 اسلاید

 قسمتی از متن .ppt : 

مرتب سازی سریع 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