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

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

صفحه 2:
سورد در سلل49 پیشنهاد کردم لست © از روش تقسيم و حل ‎US (gs call (Divide & Oveaquer)‏ © آرايه را به صورت “در جا” (ج2-|<) 10)مرتب مي كند - شبيه مرتب سازي درجي (م58) +طاءوص21) است. - برخلاف (:م8) جب-ج() ) به حافظه اضافي نياز ندارد. © بياده سازي هاي سريعي كه براي آن ارائه شدهء باعث بكاركيري وسيع آن در عمل شده است. 

صفحه 3:
2.0 تقسيم:يك عضو مثل از آرايه را انتخاب كرده و آرایه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از : كوجكتر و بخش ديكر از « بزرگتر باشند. حل: به صورت بازگشتي هر کدام از این دو بخش را مرتب مي کنیم ترکیب: كارخاصي لازم نیست! : هزینه عمل تقسیم خطي است ‎O(a)‏ 

صفحه 4:
[د . ‎lp.‏ //(و ,م ,8)) 1ك« كجوووم ‎x—Olp] // puot= lp]‏ 

صفحه 5:


صفحه 6:


صفحه 7:


صفحه 8:


صفحه 9:


صفحه 10:


صفحه 11:


صفحه 12:


صفحه 13:


صفحه 14:
8 6 7 | ۰ || 13 |10 1 6 ۱۰۱۲۶ ۶ 613 5 | 3 ۱10 | 8 6 8 8 5 10 13 10 |13 6 

صفحه 15:
شبه کد الگوریتم مرتب سازي QOICKEORTN(®, p, r) P op<r tea g—PORMMOV(, p, vr) QO1ICKGORN(, p, A) QO1ICKOORTO, v4, r) ‎vA QODICKGORT(®, 4, «)‏ مساك 

صفحه 16:
© فرض كنيد تمام اعضاي آرایه غیر تكراري هستند. * در عمل معمولا روشهاي مناسبتري براي تقسیم آرایه هايي که اعضاي تكراري دارند. استفاده مي شود ‎٩‏ فرض کنید ()۳" هزینه مرتب سازي آرایه اي به طول ب با استفاده ازاين الگوریتم در بدترین حالت باشد. ‏# معمولا بهترین حالت الگوریتمها را در نظر نمي كيريم اما براي مرتب سازي سریع این حالت را نیز بررسي مي کنیم. 

صفحه 17:
‎٩‏ آرایه از قبل مرتب شده باشد. © تقسیم حول مقدار مینیمم یا ماکزیمم صورت گیرد. © يكي از دو بخش بدست آمده از تقسیم» هیچ عضوي نداشته باشد. ‎Ma) = PO) + P(r) + O(a)‏ © ‎O() + Nu -C) + O(s)‏ = 0+... +0 + ه > ‎P(r) + O(a)‏ = ‎O(a?)‏ = 

صفحه 18:
1( > 1)0( + /1)7-1( + 7 

صفحه 19:
1( > 1)0( + /1)7-1( + 7 1 

صفحه 20:
1( > 1)0( + /1)7-1( + 7 ca ‏سر‎ ‎™) Trl) 

صفحه 21:


صفحه 22:
1( > 1)0( + /1)7-1( + 7 cn ‏کم‎ ‎710( e(n-l) ‏م‎ + 10) c(n-2) “oN 10) 0)۱( 

صفحه 23:
Mn) = 10) + Un-1) + en ‎ofS =@(n?)‏ نی 1 10 )10 

صفحه 24:


صفحه 25:
# در بهترین حالت» دو بخش تقسیم شده تقریبا هم اندازه هستند و اندازه مساله در هر بار تقسیم نصف مي شود: (سسسی) ( ما6 3 )6 + (9/6 - ۱ ‎٩‏ سوال: اگر تقسیم طوري صورت بگیرد که 96000 اعضاي آرایه در يك بخش و 00096 در بخش دیگر قرار بگیرند» هزینه الگوریم چگونه خواهد بود ؟ ‎D(a) = VID) + NOWdID)+ O(a) & 

صفحه 26:
90% 06 

صفحه 27:
90% 06 

صفحه 28:
90% 06 

صفحه 29:
90% 06 

صفحه 30:
90% 06 : ۱ bi ۱ )0 وم 07100 > (] > 07208 

صفحه 31:
90% 06 07208 > ]( >20071080 

صفحه 32:
90% : \ 0)1( T(n) =0(nlod,) =O(nlog) =O(nlgn) 

صفحه 33:
قرض کنید. به صورت متوالي در هربار تقسیم. آرایه بطور متوازن نامتوازن تقسیم شود. حالت متوازن را ,ولس,ا و حالت نا متوازن | رواسای مي نامیم و هزینه الگوریتم را محاسبه مي کنیم جد بواسما 3 (9)0 + (60)06 - رز ۰ ‎(a) =L(«-() + O(a) > Ockohy sep‏ ۰ ‎O(e/2)) + O(a)‏ + رمولم‌راه ع ور ه ‎L(a) = QL(al2 -0) + O(a) > L(m) = Ofelogs)‏ ® 

صفحه 34:
© عمل نقسیم نقش اصلي را در تعبین هزینه الگوریتم دارد - چگونه تقسیم متوازني انجام دهیم؟ - یا چگونه مي توانیم امیدوار باشیم اغلب نقسیم ها متوازن هستند؟ 9 انتخاب تصادفي عضو نشانگر سردم - زمان اجرا مستقل از مقادیر و توزیع ورودیهاست - هیچ ورودي خاصي سبب شکل گيري بدترین حالت الگوریتم نمي شود - احتمال وقوع بدترین حالت تنها به مولد اعداد (شبه) تصادفي بستگي دارد 

صفحه 35:
شبه کد الگوریتم تقسیم تصادفي RODOOO-PORM MOO, p, a)/l ‎puo= lp]‏ // م0 ‎imp‏ ‎Poricpt )) 25‏ ‎eo Fl] Sx‏ ‎feat (1‏ ‎ounp Of] Of]‏ ‎swe Op] Ol] // Prod place oF prt!‏ موب 

صفحه 36:
آنالیز مرتب سازي با تقسیم تصادفي © با انتخاب تصادفي نشانگر؛ آرایه اي به طول » ممکن است به صورت (0:) : (صمرا): ..: (9/: ولم) تقسیم شود. © فرض كنيد الكوريتم تقسيم دو بخش سجن را تولید مي کند که در آن ,00,0 است. * متغیر تصادفي ۱ را چنین تعریف مي کنیم: - 22 لگر طول‌دوبخش:| بساشد؛ در غیر لینصورت 20 2۷ - مارا متغیر تتصادفی‌نشانگر (عاطادسه() ط»0() له )ميك ويند. - 01 > (2 0 - [606 

صفحه 37:
آنالیز مرتب سازي با تقسیم تصادفي ۵(+ ‏رم‎ + O(a) 0+ ‏+رمم‎ O(a) ‏مه‎ ‎Ma)= Dol) + PO) + O(a) we: 1 Ti) = 3) X(T) + Th ‏عل‎ 1(+06)۸( k=O * هزینه: برابريا اميد رياضي تابع تضادفي (م)۳* است: هزینه < [()۳ 

صفحه 38:
آنالیز مرتب سازي با تقسیم تصادفي nl eal ‎X(T) +Tur k- 1)+0()] &‏ و27 ‎AX (T+ Tur ke +010) =‏ ,)= ‎Xk » T(h) ‏6 1+۵0 +718 و ‏[() م ‎ke De‏ وس ار ‏سس ‎“a‏ 5 اه 00 2 

صفحه 39:
آنالیز مرتب سازي با تقسیم تصادفي 1 E(T(n)) =2/n¥ 8)1)19(+ ©) ‏معز‎ (66) مزه - (6)0)00 ج لد ماس وعبا ‎P‏ ‎O(a)‏ 1 AT) =2/ ny, AT(A))+ O(n) k-2 

صفحه 40:
تقسیم تصا آنالیز مرتب سازي با تق لفي mi Mogk<=1 ‏م2‎ ogk< ‏جح‎ rf logn- ait ‎Bsa.‏ باشد. مي زنیم» هزینه الگوریتم از مرتبه ب بسا ب 2 عه ؛ 0 ‎ley‏ ۰ اي اثبات اين حدس بايا ام 5 1 توان یافت بنحوي كه: — وبا وه > (())) 

صفحه 41:
آنالیز مرتب سازي با تقسیم تصادفي m1 A T()) =; klogk+ O(n) k=2 AT) <="2 jit logn- at + 0 )0 ۲۲710(( > < 710 07- 7 09 

صفحه 42:
آنالیز مرتب سازي با تقسیم تصادفي oa - ‏اه‎ ۲۳]17](( ><621097- E(T(a)) > ‏وا موم و‎ ud > O(a) ‏يسء با انتخاب مناسب > مي توان كران بالايي از‎ ‏کرد.‎ lan a fog ‏مرتبه ب‎ &(M(a)) = O(a oa a) 

صفحه 43:
© الكوريتم ‎quicker‏ تصادفي, از نظر هزینه با مومس هم رتبه است. چون نيازي به حافظه اضافی ندارد» مسعمولا انتقلب اول براي مرقب ستازي :اسك 9 در عمل اين الگوریتم بین ۵ تا 6 برابر سریعتر از سس اجرا مي شود. 

صفحه 44:
‎٩‏ در پروژه ۰ مقایسه الگوریتم هاي مرتب سازي اسب معمولي و تصادفي را نیز پیاده سازي کرده. با بقیه مقایسه کنید. ‏* مسایل 07 تا 6-6 را حل و ارسال کنید 

مرتب سازي سريع Quicksort ساختمان داده ها و الگوريتمها Quicksort پ###يشنه#اد ك##رده #ا#ست Hoare در س##ا##ل1962 از روش تقسيم و حل ( )Divide & Conquerاستفاده مي كند آرايه را به صورت “در جا” ()In Placeمرتب مي كند – – شبيه مرتب سازي درجي( )Insertion Sortاست. برخالف ( ) Merge Sortبه حافظه اضافي نياز ندارد. پياده سازي هاي سريعي كه براي آن ارائه شده ،باعث بكارگيري وسيع آن در عمل شده است. تقسيم و حل .1 تقسيم:يك عضو مثل xاز آرايه را انتخاب كرده و آرايه را طوري به دو بخش طوري تقسيم مي كنيم كه يك بخش آن از xكوچكتر و بخش ديگر از xبزرگتر باشند. >= x ‏x <= x .2حل :به صورت بازگشتي هر كدام از اين دو بخش را مرتب مي كنيم .3تركيب :كارخاصي الزم نيست! نكته :هزينه عمل تقسيم خطي است )Θ(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] return i // final place of pivot! n هزينه تقسيم براي آرايه استΘ(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 آرايه از قبل مرتب شده باشد. تقسيم حول مقدار مينيمم يا ماكزيمم صورت گيرد. يكي از دو بخش بدست آمده از تقسيم ،هيچ عضوي نداشته باشد. ) T(n) = T(0) + T(n-1) + Θ(n )= Θ(1) + T(n -1) + Θ(n = T(n-1) + Θ(n)  n + n-1+ …+1 )= Θ(n2 درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت درخت هزينه بدترين حالت بهترين حالت در بهترين حالت ،دو بخش تقسيم شده تقريبا هم اندازه هستند و اندازه مساله در هر بار تقسيم نصف مي شود: )T(n) = 2T(n/2) + Θ(n)  Θ(n log n) (mergesort سوال :اگر تقسيم طوري صورت بگيرد كه %90اعضاي آرايه در يك بخش و 10%در بخش ديگر قرار بگيرند ،هزينه الگوريم چگونه خواهد بود ؟ ‏T(n) = T(n/10) + T(9n/10)+ Θ(n)  90% 10% 90% 10% 90% 10% 90% 10% 90% n 10 10% n 10/ 9 cnlog T(n) cnlog 90% n 10 10% n 10 cnlog T(n) 20cnlog 90% n 10 10% n 2 T(n) (nlog ) (nlog ) (nlgn) حالتي ديگر فرض كنيد ،به صورت متوالي در هربار تقسيم ،آرايه بطور متوازن و نامتوازن تقسيم شود .حالت متوازن را 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 Randomized Quicksort عمل تقسيم نقش اصلي را در تعيين هزينه الگوريتم دارد – – چگونه تقسيم متوازني انجام دهيم؟ يا ،چگونه مي توانيم اميدوار باشيم اغلب تقسيم ها متوازن هستند؟ انتخاب تصادفي عضو نشانگر 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←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] return i // final place of pivot! pivot انتخاب تصادفي عضو نشانگر آناليز مرتب سازي با تقسيم تصادفي ‏ ‏ ‏ با انتخاب تصادفي نشانگر؛ آرايه اي به طول nممكن است به صورت { }n/2 :n/2{ ;… ;}1,n-2{ ; }n-1:0تقسيم شود. فرض كنيد الگوريتم تقسيم دو بخش k:n-k-1را توليد مي كند كه در آن k=0,1,…, n-1است. متغير تصادفي Xkرا چنين تعريف مي كنيم: – #ينصورت .Xk =0 ، Xk=1ا#گر طولدوبخش k:n-k-1ب###اشد؛ در غير ا Xkرا متغير ت###صادفين##شانگر ()Indicator Random Variableميگ###ويند. – ‏E[Xk] = P(Xk =1) = 1/n – آناليز مرتب سازي با تقسيم تصادفي 0:n-1 )T(0) + T(n-1) + Θ(n 1:n-2 )T(1) + T(n-2) + Θ(n =)T(n … ‏n-1:0 )T(n-1) + T(0) + Θ(n ‏n 1 ))T(n)  Xk (T(k)  T(n k  1)  (n ‏k0 ‏ هزينه ،برابربا اميد رياضي تابع تصادفي ) T(nاست :هزينه = ])E[T(n آناليز مرتب سازي با تقسيم تصادفي جايگذاري n 1 E[T(n)] E[ Xk (T(k)  T(n k  1)  (n))] n 1 k0  E[ Xk (T(k)  T(n k  1)  (n))] k0 n 1  E[ Xk ]* E[(T(k)  T(n k  1)  (n))] ،اميد رياضي تابعي خطي است Xk وT(k) مستقل#از هم هستند k0 n 1 1 1 n 1 1 n   E[(T(k)]  E[T(n k  1)]  E[(n))] n k0 n k0 n k0 2 n 1   E[(T(k)] (n) n k0 E(Xk) = 1/n متقارن،اين دو سري هستند آناليز مرتب سازي با تقسيم تصادفي n 1 E(T(n)) 2/ n E(T(k))  (n) k0 if k=0 or k =1  E(T(K)) = 2/nΘ(n2) = Θ(n) n 1 E(T(n)) 2/ n E(T(k))  (n) k2 آناليز مرتب سازي با تقسيم تصادفي ‏n 1 بعنوان تمرين ثابت كنيد 1 2 1 2 ‏k logk  n logn n ‏ 2 8 ‏k2 حدس مي زنيم ،هزينه الگوريتم از مر#تبه n log nباشد. بر#اي اثبات اين حدس بايد نشان دهيم: ثابت aر#ا مي توان يافت ،بنحوي كه‌: ‏E(T(n)) <= a n log n آناليز مرتب سازي با تقسيم تصادفي جايگذاري حدس براي هر كدام از جمالت سري ‏n 1 )E(T(n))  k logk  (n جايگذاري رابطه قبلي به جاي سري باال ‏k2 2a  1 2 1 2 )E(T(n))   n logn n   (n ‏n2 8  ‏ an ‏ ‏E(T(n)) anlogn   (n) ‏ 4 ‏ آناليز مرتب سازي با تقسيم تصادفي ‏ an ‏ ‏E(T(n)) anlogn   (n) ‏ 4 ‏ به ازاي برخي مقادير aمثبت است ‏E(T(n)) <= a n log n if )an/4 > Θ(n پس ،با انتخاب مناسب aمي توان كران بااليي از مرتبه n log nپيدا كرد. )E(T(n)) = Θ(n log n بحث و بررسي الگوريتم quicksortتصادفي ،از نظر هزينه با mergesortهم رتبه است. چون نيازي به حافظه اضافي ندارد ،معموال انتخاب اول براي مرتب سازي است. در عمل اين الگوريتم بين 3تا 9برابر سريعتر از mergesort اجرا مي شود. تمرين در پروژه ،1مقايسه الگوريتم هاي مرتب سازيquicksort ، معمولي و تصادفي را نيز پياده سازي كرده ،با بقيه مقايسه كنيد. مسايل 1-7تا 5-7را حل و ارسال كنيد