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

توضیحات محصول

دانلود پاورپوینت مرتب سازي سريع Quicksort با فرمت ppt ودر 44 اسلاید قابل ویرایش 

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

Quicksort

lHoare در سال 1962 پيشنهاد كرده است

از روش تقسيم و حل (Divide & Conquer) استفاده مي كند

آرايه را به صورت “در جا” (In Place)مرتب مي كند

–شبيه مرتب سازي درجي(Insertion Sort) است.

–برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد.

پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است.

تقسيم و حل

.1تقسيم:يك عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند.

2.حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم

3.تركيب: كارخاصي لازم نيست!

نكته: هزينه عمل تقسيم خطي است Θ(n)

آناليز الگوريتم
 

فرض كنيد تمام اعضاي آرايه غير تكراري هستند.

در عمل معمولا روشهاي مناسبتري براي تقسيم آرايه هايي كه اعضاي تكراري دارند، استفاده مي شود

فرض كنيد T(n) هزينه مرتب سازي آرايه اي به طول n با استفاده ازاين الگوريتم در بدترين حالت باشد.

معمولا بهترين حالت الگوريتمها را در نظر نمي گيريم اما براي مرتب سازي سريع اين حالت را نيز بررسي مي كنيم.

بهترين حالت

lدر بهترين حالت، دو بخش تقسيم شده تقريبا هم اندازه هستند و اندازه مساله در هر بار تقسيم نصف مي شود:

T(n) = 2T(n/2) + Θ(n) à Θ(n log n) (mergesort)

سوال: اگر تقسيم طوري صورت بگيرد كه 90% اعضاي آرايه در يك بخش و %10 در بخش ديگر قرار بگيرند، هزينه الگوريم چگونه خواهد بود ؟

lT(n) = T(n/10) + T(9n/10)+ Θ(n)

حالتي ديگر

فرض كنيد، به صورت متوالي در هربار تقسيم، آرايه بطور متوازن و نامتوازن تقسيم شود. حالت متوازن را 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)