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

صفحه 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 را حل و ارسال کنید