بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
Hoare در سال 1962 پيشنهاد كرده است
از روش تقسيم و حل (Divide & Conquer) استفاده مي كند
آرايه را به صورت “در جا” (In P ace)مرتب مي كند
–شبيه مرتب سازي درجي(Insertion Sort) است.
–برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد.
پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است.
اسلاید 2 :
.1تقسيم:يك عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند.
.2حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم
.3تركيب: كارخاصي لازم نيست!
نكته: هزينه عمل تقسيم خطي است Θ(n)
اسلاید 3 :
فرض كنيد تمام اعضاي آرايه غير تكراري هستند.
در عمل معمولا روشهاي مناسبتري براي تقسيم آرايه هايي كه اعضاي تكراري دارند، استفاده مي شود
فرض كنيد T(n) هزينه مرتب سازي آرايه اي به طول n با استفاده ازاين الگوريتم در بدترين حالت باشد.
معمولا بهترين حالت الگوريتمها را در نظر نمي گيريم اما براي مرتب سازي سريع اين حالت را نيز بررسي مي كنيم.
اسلاید 4 :
آرايه از قبل مرتب شده باشد.
تقسيم حول مقدار مينيمم يا ماكزيمم صورت گيرد.
يكي از دو بخش بدست آمده از تقسيم، هيچ عضوي نداشته باشد.
T(n) = T(0) + T(n-1) + Θ(n)
= Θ(1) + T(n -1) + Θ(n)
= T(n-1) + Θ(n) à n + n-1+ …+1
= Θ(n2)
اسلاید 5 :
در بهترين حالت، دو بخش تقسيم شده تقريبا هم اندازه هستند و اندازه مساله در هر بار تقسيم نصف مي شود:
T(n) = 2T(n/2) + Θ(n) à Θ(n og n) (mergesort)
سوال: اگر تقسيم طوري صورت بگيرد كه 90% اعضاي آرايه در يك بخش و %10 در بخش ديگر قرار بگيرند، هزينه الگوريم چگونه خواهد بود ؟
T(n) = T(n/10) + T(9n/10)+ Θ(n)
اسلاید 6 :
عمل تقسيم نقش اصلي را در تعيين هزينه الگوريتم دارد
–چگونه تقسيم متوازني انجام دهيم؟
– يا، چگونه مي توانيم اميدوار باشيم اغلب تقسيم ها متوازن هستند؟
انتخاب تصادفي عضو نشانگر pivot
–زمان اجرا مستقل از مقادير و توزيع وروديهاست
–هيچ ورودي خاصي سبب شكل گيري بدترين حالت الگوريتم نمي شود
–احتمال وقوع بدترين حالت تنها به مولد اعداد (شبه) تصادفي بستگي دارد
اسلاید 7 :
با انتخاب تصادفي نشانگر؛ آرايه اي به طول n ممكن است به صورت
{0:n-1} ; {1,n-2}; …; {n/2 :n/2} تقسيم شود.
فرض كنيد الگوريتم تقسيم دو بخش k:n-k-1 را توليد مي كند كه در آن k=0,1,…, n-1 است.
متغير تصادفي Xk را چنين تعريف مي كنيم:
–Xk=1 اگر طول دوبخش k:n-k-1 باشد؛ در غير اينصورت، Xk =0.
–Xk را متغير تصادفي نشانگر (Indicator Random Variab e)مي گويند.
–E[Xk] = P(Xk =1) = 1/n
اسلاید 8 :
الگوريتم quicksort تصادفي، از نظر هزينه با mergesort هم رتبه است.
چون نيازي به حافظه اضافي ندارد، معمولا انتخاب اول براي مرتب سازي است.
در عمل اين الگوريتم بين 3 تا 9 برابر سريعتر از mergesort اجرا مي شود.
