مرتب سازی سریع

مرتب سازی سریع

اسلاید 1: مرتب سازي سريع Quicksort ساختمان داده ها و الگوريتمها

اسلاید 2: QuicksortHoare در سال 1962 پيشنهاد كرده استاز روش تقسيم و حل (Divide & Conquer) استفاده مي كندآرايه را به صورت “در جا” (In Place)مرتب مي كندشبيه مرتب سازي درجي(Insertion Sort) است.برخلاف (Merge Sort ) به حافظه اضافي نياز ندارد.پياده سازي هاي سريعي كه براي آن ارائه شده، باعث بكارگيري وسيع آن در عمل شده است.

اسلاید 3: تقسيم و حلتقسيم:يك عضو مثل x از آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از x كوچكتر و بخش ديگر از x بزرگتر باشند.حل: به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيمتركيب: كارخاصي لازم نيست!نكته: هزينه عمل تقسيم خطي است Θ(n)

اسلاید 4: تقسيمهزينه تقسيم براي آرايه n عضوي برابر Θ(n) است PARTITION(A, p, q)// A[p. . q] x←A[p]// pivot= A[p]i←pfor j←p+ 1 to qdo if A[j] ≤xthen i←i+ 1swap A[i] ↔A[j]swap A[p] ↔A[i]// final place of pivot!return i

اسلاید 5: مثال

اسلاید 6: مثال

اسلاید 7: مثال

اسلاید 8: مثال

اسلاید 9: مثال

اسلاید 10: مثال

اسلاید 11: مثال

اسلاید 12: مثال

اسلاید 13: مثال

اسلاید 14: مثال

اسلاید 15: شبه كد الگوريتم مرتب سازيQUICKSORT(A, p, r)if p< rthen q←PARTITION(A, p, r)QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r)Initial call:QUICKSORT(A, 1, n)

اسلاید 16: آناليز الگوريتمفرض كنيد تمام اعضاي آرايه غير تكراري هستند. در عمل معمولا روشهاي مناسبتري براي تقسيم آرايه هايي كه اعضاي تكراري دارند، استفاده مي شودفرض كنيد T(n) هزينه مرتب سازي آرايه اي به طول n با استفاده ازاين الگوريتم در بدترين حالت باشد. معمولا بهترين حالت الگوريتمها را در نظر نمي گيريم اما براي مرتب سازي سريع اين حالت را نيز بررسي مي كنيم.

اسلاید 17: بدترين حالات quicksortآرايه از قبل مرتب شده باشد.تقسيم حول مقدار مينيمم يا ماكزيمم صورت گيرد.يكي از دو بخش بدست آمده از تقسيم، هيچ عضوي نداشته باشد.T(n) = T(0) + T(n-1) + Θ(n) = Θ(1) + T(n -1) + Θ(n) = T(n-1) + Θ(n) n + n-1+ …+1 = Θ(n2)

اسلاید 18: درخت هزينه بدترين حالت

اسلاید 19: درخت هزينه بدترين حالت

اسلاید 20: درخت هزينه بدترين حالت

اسلاید 21: درخت هزينه بدترين حالت

اسلاید 22: درخت هزينه بدترين حالت

اسلاید 23: درخت هزينه بدترين حالت

اسلاید 24: درخت هزينه بدترين حالت

اسلاید 25: بهترين حالتدر بهترين حالت، دو بخش تقسيم شده تقريبا هم اندازه هستند و اندازه مساله در هر بار تقسيم نصف مي شود:T(n) = 2T(n/2) + Θ(n)  Θ(n log n) (mergesort)سوال: اگر تقسيم طوري صورت بگيرد كه 90% اعضاي آرايه در يك بخش و %10 در بخش ديگر قرار بگيرند، هزينه الگوريم چگونه خواهد بود ؟T(n) = T(n/10) + T(9n/10)+ Θ(n)

اسلاید 26: 10% 90%

اسلاید 27: 10% 90%

اسلاید 28: 10% 90%

اسلاید 29: 10% 90%

اسلاید 30: 10% 90%

اسلاید 31: 10% 90%

اسلاید 32: 10% 90%

اسلاید 33: حالتي ديگرفرض كنيد، به صورت متوالي در هربار تقسيم، آرايه بطور متوازن و نامتوازن تقسيم شود. حالت متوازن را Lucky و حالت نا متوازن را unlucky مي ناميم و هزينه الگوريتم را محاسبه مي كنيمL(n) = 2U(n/2) + Θ(n)  Lucky stepU(n) = L(n -1) + Θ(n)  Unlucky stepL(n) = 2(L(n/2-1) + Θ(n/2)) + Θ(n) L(n) = 2L(n/2 -1) + Θ(n)  L(n) = Θ(nlogn)

اسلاید 34: Randomized Quicksortعمل تقسيم نقش اصلي را در تعيين هزينه الگوريتم داردچگونه تقسيم متوازني انجام دهيم؟ يا، چگونه مي توانيم اميدوار باشيم اغلب تقسيم ها متوازن هستند؟انتخاب تصادفي عضو نشانگر pivotزمان اجرا مستقل از مقادير و توزيع وروديهاستهيچ ورودي خاصي سبب شكل گيري بدترين حالت الگوريتم نمي شوداحتمال وقوع بدترين حالت تنها به مولد اعداد (شبه) تصادفي بستگي دارد

اسلاید 35: انتخاب تصادفي عضو نشانگر pivotشبه كد الگوريتم تقسيم تصادفيRANDOM-PARTITION(A, p, q)// A[p. . q] k ← random-number (p..q)swap A[p] , A[k]x←A[p]// pivot= A[p]i←pfor j←p+ 1 to qdo if A[j] ≤xthen i←i+ 1swap A[i] ↔A[j]swap A[p] ↔A[i]// final place of pivot!return i

اسلاید 36: آناليز مرتب سازي با تقسيم تصادفيبا انتخاب تصادفي نشانگر؛ آرايه اي به طول 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 Variable)مي گويند. E[Xk] = P(Xk =1) = 1/n

اسلاید 37: آناليز مرتب سازي با تقسيم تصادفيهزينه، برابربا اميد رياضي تابع تصادفي T(n) است: هزينه = E[T(n)]

اسلاید 38: اين دو سري، متقارن هستندآناليز مرتب سازي با تقسيم تصادفيجايگذارياميد رياضي، تابعي خطي استXk و T(k) از هم مستقل هستندE(Xk) = 1/n

اسلاید 39: آناليز مرتب سازي با تقسيم تصادفيif k=0 or k =1  E(T(K)) = 2/nΘ(n2) = Θ(n)

اسلاید 40: آناليز مرتب سازي با تقسيم تصادفيحدس مي زنيم، هزينه الگوريتم از مرتبه n log n باشد. براي اثبات اين حدس بايد نشان دهيم: ثابت a را مي توان يافت، بنحوي كه:‌E(T(n)) <= a n log nبعنوان تمرين ثابت كنيد

اسلاید 41: آناليز مرتب سازي با تقسيم تصادفيجايگذاري حدس براي هر كدام از جملات سريجايگذاري رابطه قبلي به جاي سري بالا

اسلاید 42: به ازاي برخي مقادير a مثبت استآناليز مرتب سازي با تقسيم تصادفيE(T(n)) <= a n log n if an/4 > Θ(n) پس، با انتخاب مناسب a مي توان كران بالايي از مرتبه n log n پيدا كرد. E(T(n)) = Θ(n log n)

اسلاید 43: بحث و بررسيالگوريتم quicksort تصادفي، از نظر هزينه با mergesort هم رتبه است. چون نيازي به حافظه اضافي ندارد، معمولا انتخاب اول براي مرتب سازي است.در عمل اين الگوريتم بين 3 تا 9 برابر سريعتر از mergesort اجرا مي شود.

اسلاید 44: تمريندر پروژه 1، مقايسه الگوريتم هاي مرتب سازي، quicksort معمولي و تصادفي را نيز پياده سازي كرده، با بقيه مقايسه كنيد.مسايل 7-1 تا 7-5 را حل و ارسال كنيد