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

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

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

نوع فایل : .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

شبه كد الگوريتم تقسيم تصادفي

آناليز مرتب سازي با تقسيم تصادفي

بحث و بررسي