مرتب سازی الگوریتم ها 2

صفحه 1:
Sorting Algorithms 2 

صفحه 2:
Quicksort ا ان ‎yl‏ سر راب ران را ات كال عناصر را به دو زیر مجموعه چپ و راست تقسیم کنید. | * تمام عناصر زیر مجموعه سمت رلست از محور یزرگتر هستند. ‎SC ar ey <li‏ ا ل ‎Be‏ ‏"" نيازى به ار A 5 ‏لا‎ ‎2100010000 

صفحه 3:
Quicksort void quicksort(int *arrayOfints,intfirst,int Cast) 4 int pivot! if (first <Cast) 2 pivot =partition(arrayOfints,first,last)! quicksort(arrayOfints first pivot-7)! quicksort(arrayOfintspivot+7{ast)! ) 0 

صفحه 4:
Quicksort int partition(int* arrayOfints, int first, int last) int temp; int p = first; // set pivot = first index for (int k = first+1; k <= last; k++) // for every other indx 1 ۹ ‏لقا سن م‎ <= arrayOfInts[first]) // if data is smaller i Dadar ty // update final pivot location swap(arrayOfInts[k], arrayOfInts[p]); ۷ swap(arrayOfints[p], arrayOfiInts[first]); return p; i 

صفحه 5:
کی ۳ ۵ سس - مس [وإطه - [فإطهم الا مومت © دن دم ليك دن يقت اس مات موم مس 0 Pee 7 ۵-0-6 ۱ 0 | (a) See een] met ‏سس‎ 

صفحه 6:
Complexity of Quicksort " بدترين حالت: (22) © "" بدترين حالت كى اتفاق مى افتد؟ #لیست مرتب يا تقریبا مرتب زیر مجموعه های بدست آمده نامتعادل خواهند شد. "ادر حالت متوسط ييجيدكى برابر (106211 6012© است حالت متوسط اين الكوريتم حالت غالب است 

صفحه 7:
Complexity of Quicksort رابطه بإزكشى: (حالت متوسط) ” زير مساله داريم. اگر محور خوب باشد سایز هر کدام 72 مساله اصلی است. هزينه تابع 2217]111012 برابر ‎poser] O16)‏ ‎il‏ ک عیا 2 < روا 2 ك 1ه ۳ ‎master: O(nlog,n) «<4‏ 

صفحه 8:
Complexity of Quicksort ‏رابطه بازگشتی: (بدترین حالت)‎ "" دو زير مجموعه با سايز هاى ‎١‏ و 11-1 خواهيم داشت. "" نمى شود از تئورى '112351:©61 استفاده كرد. جون 8 يعنى اندازه زير ‎n-1/n n-2/n-1 n-3/n-2‏ ‎eID yee ie‏ ل ‎(n-1) + (n-2) + (n-3)‏ + 0« ‎Sum(1,N) =N(N+1)/2 = O(N?)‏ 

صفحه 9:
Complexity of Quicksort "ابراى بياده سازى 0]1110155015 به فضاى يشته نياز داريم. درا تررست ی 90:0۳ ات #اگر دو زیر مجموعه با سایز های ۱ و 11-1 تولید شود. "" حالت متوسط: (1 1067) © ‎SIM‏ محور درست انتخاب شده باشد. 

صفحه 10:
۱۱/2 ‎WI‏ الگوریتم لو * هر بار آرایه به دو زیر مجموعه مساوی تقسیم شود. * سپس زیرمجموعه ها را با هم ادغام کنید. ‏* تقسیم را تا وقتی ادامه دهید که به یک عنصر برسید. * یک مجموعه تک عنصری خود به خود مرتب است. ‎9 LC See rea ‏مرتب باشد.‎ item subarrays => 2 item subarrays ‏اجا‎ ‎item subarrays => 4 item subarrays ++ ® ‏و ال‎ 

صفحه 11:
۱۱/2 void mergesort(int* array, int* tempArray, int low, int high, int size) 0 if (low < high) 1 int middle = (low + high) / 2; mergesort(array,tempArray,low,middle, size); mergesort(array,tempArray,middle+1, high, size); merge(array,tempArray,low,middle,high, size); 5 5 

صفحه 12:
MergeSort ۱ Tae NABr eam cnt). tec Namrata nteCeICCMs tLe SEB tLe?) int i, j, k; for (i = low; i <= high; i++) { tempArrayli] = arrayfil; } // copy into temp 7 i = low; j = middle+1; k = low; while ((i <= middle) && (j <= high)) { // merge if (tempArrayli] <= tempArraylj]) _// if Ihs item is smaller ree Nes mou ‏تا‎ ‏ا‎ ‏ال فيا‎ 7 } 00 0 while (i <= middle) ۱/۳ a array[k++] = tempArrayli++]; // copy the rest of the data [ ۱۱ ‏گذ ردرمی مب ۵ع۵ه بولصه‎ O LCE tee ۱ 

صفحه 13:
MergeSort Example (Meta a el | 18 

صفحه 14:
MergeSort Example (Meta a el | 4 ده 5 Dd 

صفحه 15:
MergeSort Example ‎JL‏ ات ‎els Ws ‎c ‎ 

صفحه 16:
Merge Sort Example طلم © يك ‎eee =‏ جلها 5 2 5 و مه مس اس ا زد ۷ 1 

صفحه 17:
MergeSort Example 11 كه 0 5 7 el 2 > 228 0 1 k io“) 81 5 ۳ ا ‎See eee ae eels‏ *حال باید حلقه دوم را تا وقتی که برابر طح شود ادامه دهيم. تسه 17 7 ke 

صفحه 18:
MergeSort Example 8 Cad Cre Me Rn ‏رل‎ > = : 5 : J 8 20 ‏ل لص‎ Oe cl 3-05 2 2 2 

صفحه 19:
Complexity of MergeSort ‏رابظه بازكشتى:‎ "" hen soit =! Eee rs Cel Ronn O1¢:) Peers iter sae a PET Y OW CA N= 101 07-08 Kah Mere ne eles a=2b=2k=18 Banta eres Leki) earn ee eo hE al | O(n log,n) «52 cee Is eens enna e SUSY re ee ed cae ea ‏ل ا‎ a moa log,n) "" ديكر بيجيدكى الكوريتم وابسته به كيفيت محور نيست. 

صفحه 20:
Space Complexity of Mergesort ‏در مرتب سازی ادغام به یک آرایه موقت با سایز (0610) نیاز‎ * ‏داریم.‎ ی تعداد توابع بر کین پا را 

صفحه 21:
۱/۰۵ و زا ار ار ار را ار لان ‎(ce‏ فى ۳ ‎pe‏ ‏"" جستجوى خالى ‎Ta‏ ا ا ا 0 امك 2 داده و 2 جستجو داريم: جستجوی داده تصادفی: (0)۳) * .2 ‎ay Aner entree er es eecges‏ رق ‎*log,n‏ 

صفحه 22:
۱/۰۵ 72۹/۱۱ 2 Z(n - log,n) <= n log,n Z <= (n log,n) / (n-log,n) Z <= (n log,n) / n [Approximation] Z <= log,n [Approximation] در دو روش قبلی بعد از ۷[ جستجو هزینه مرتب سازی جبران می شد. در این حالت اگر ‎Nt peer Ney‏ را 1,000,000 items = 19 searches, instead of 1,000,000 

صفحه 23:
How Fast? "" اكر از روش مقايسه و جابجايى استفاده كنيم » بهترين مرتب سازى ممكن از لحاظ تئورى داراى بيجيدكى (10911 1)11 © است. 9 اثبات: درخت تصميم كيرى- * هر گره یک مقایسه است و هر شاخه یک نتیجه * حرکت در درخت نحوه اجرای الگوریتم را نشان می دهد. 

صفحه 24:
How Fast? 101 [1,2,3] [2,73] ۷95 No ‏هله‎ 52 / [1,2,3] [2,1,3 13 ۳۹۳۸ [3,1,2] 

صفحه 25:
How Fast? ‎Mtoe She] ies‏ ¢ ا لا مساله است. ‏* لذا هر الگوریتمی که با درخت تصیم گیری مدل شود دارای ‎les fin‏ 2 ازستر ‏* ارتفاع درخت تصمیم گیری با پیچیدگی الگوریتم برابر است. ‎ae eons aS roe PEs cs ner aa ‏برابر 1 + 100101 است.‎ 

صفحه 26:
How Fast? a WEG O1G7 tee DG ra (nee) ‏را‎ ‎>(n)(n-7)(n-2)(n-a) ... ceil(n/2) // doing fewer multiplies 0 ‏حون‎ ۱ Cog ,n!>Cog .(n/2)"?” Cog,n!>(n/2)Cog,(n/2) //exponentiationinlogs=multiplication (۲ ۱۳/9 ۱۳ ۱۳ ۳ ۱۳ 

Sorting Algorithms 2 Quicksort الگوريتم کلي quicksort يکي از عناصر را به عنوان محور انتخاب کنيد. عناصر را به دو زير مجموعه چپ و راست تقسيم کنيد. تمام عناصر زير مجموعه سمت چپ از محور کوچکتر هستند. تمام عناصر زير مجموعه سمت رلست از محور يزرگتر هستند. الگوريتم را براي زير مجموعه هاي بدست آمده تکرار کنيد. نيازي به ادغام نداريم محور در هر مرحله سر جاي درست خود قرار دارد. Quicksort void voidquicksort(int* quicksort(int*arrayOfInts, arrayOfInts,int intfirst, first,int intlast) last) {{ int intpivot; pivot; if if(first (first<<last) last) {{ pivot pivot==partition(arrayOfInts, partition(arrayOfInts,first, first,last); last); quicksort(arrayOfInts,first,pivot-1); quicksort(arrayOfInts,first,pivot-1); quicksort(arrayOfInts,pivot+1,last); quicksort(arrayOfInts,pivot+1,last); }} }} Quicksort int partition(int* arrayOfInts, int first, int last) { int temp; int p = first; // set pivot = first index for (int k = first+1; k <= last; k++) // for every other indx { if (arrayOfInts[k] <= arrayOfInts[first]) // if data is smaller { p = p + 1; // update final pivot location swap(arrayOfInts[k], arrayOfInts[p]); } } swap(arrayOfInts[p], arrayOfInts[first]); return p; } Partition Step Through 9 18 5 9 5 18 9 5 3 3 5 9 partition(cards, 0, 4) P=0K=1 cards[1] < cards[0] ? No P=0K=2 cards[2] < cards[0] ? Yes P=1 temp = cards[2] cards[2] = cards[1] cards[1] = temp 3 20 3 20 18 20 18 20 P=1K=3 cards[3] < cards[0]? Yes P=2 temp = cards[3] cards[3] = cards[2] cards[2] = cards[3] P=2K=4 cards[4] < cards[0]? No temp = cards[2], cards[2] = cards[first] cards[first] = temp, return p = 2; Complexity of Quicksort بدترين حالتO(n2) : بدترين حالت کي اتفاق مي افتد؟ ليست مرتب يا تقريبا مرتب زير مجموعه هاي بدست آمده نامتعادل خواهند شد. در حالت متوسط پيچيدگي برابر )O(n log2n است حالت متوسط اين الگوريتم حالت غالب است Complexity of Quicksort رابطه بازگشتي( :حالت متوسط) 2زير مساله داريم. اگر محور خوب باشد سايز هر کدام ½ مساله اصلي است. هزينه تابع partitionبرابر )O(nاست. ‏a=2b=2k=1 21 = 2 تئوري )master: O(nlog2n Complexity of Quicksort رابطه بازMگشMتي( :بدترين حالت) دو زير مجموعه با سايز هاي 1و n-1خواهيم داشت. نمي شود از تئوري masterاستفاده کرد .چون bيعني اندازه زير مسائل ثابت نيست. ‏n-1/n n-2/n-1 n-3/n-2 اما مي شود اعداد را با هم جمع کرد: )… n + (n-1) + (n-2) + (n-3 = N(N+1)/2 )= O(N2 )Sum(1,N Complexity of Quicksort براي پياده سازي quicksortبه فضاي پشته نياز داريم. بدترين حالت :فضاي پشته برابر) O(nاست. اگر دو زير مجموعه با سايز هاي 1و n-1توليد شود. حالت متوسطO(log n) : اگر محور درست انتخاب شده باشد. MergeSort الگوريتم ادغام: هر بار آرايه به دو زير مجموعه مساوي تقسيم شود. سپس زيرمجموعه ها را با هم ادغام کنيد. تقسيم را تا وقتي ادامه دهيد که به يک عنصر برسيد. يک مجموعه تک عنصري خود به خود مرتب است. سپس زير مجموعه ها را طوري با هم ادغام کنيد که مجموعه حاصل مرتب باشد. ‏item subarrays => 2 item subarrays 1+1  ‏item subarrays => 4 item subarrays 2+2  از اين حقيقت که زير مجموعه ها مرتب هستند براي ادغام استفاده کنيد. MergeSort void mergesort(int* array, int* tempArray, int low, int high, int size) { if (low < high) { int middle = (low + high) / 2; mergesort(array,tempArray,low,middle, size); mergesort(array,tempArray,middle+1, high, size); merge(array,tempArray,low,middle,high, size); } } MergeSort void merge(int* array, int* tempArray, int low, int middle, int high, int size) { int i, j, k; for (i = low; i <= high; i++) { tempArray[i] = array[i]; } // copy into temp array i = low; j = middle+1; k = low; while ((i <= middle) && (j <= high)) { // merge if (tempArray[i] <= tempArray[j]) // if lhs item is smaller array[k++] = tempArray[i++]; // put in final array, increment else // final array position, lhs index array[k++] = tempArray[j++]; // else put rhs item in final array } // increment final array position // rhs index while (i <= middle) // one of the two will run out array[k++] = tempArray[i++]; // copy the rest of the data } // only need to copy if in lhs array // rhs array already in right place MergeSort Example 20 3 18 9 5 9 5 Recursively Split 20 3 18 MergeSort Example 20 3 18 9 5 Recursively Split 20 3 18 9 5 MergeSort Example 20 3 18 Merge 9 5 Merge Sort Example 20 3 2 cards Not very interesting Think of as swap 3 20 Temp Array 3 i 20 Array 18 j Temp[i] < Temp[j] Yes 3 k MergeSort Example ‏Array 18 ‏Temp Array 3 ]Temp[i ]< Temp[j ‏No 18 ‏k 20 ‏j 3 ‏i •بايد jرا زياد کنيم. • jاز highبيشتر مي شود و حلقه اول تمام مي گردد. •حال بايد حلقه دوم را تا وقتي که iبرابر mediumشود ادامه دهيم. 20 ‏k 18 3 ‏Array MergeSort Example 9 3 Final after merging above sets i=0,j= 2 Card Swap 5 5 5 9 18 20 3 5 9 18 i=1,j= i=1,j= i=2,j= i=1,j= 9 20 i=3,j= 5 Complexity of MergeSort ‏ رابطه بازگشتي: ‏ ‏ 2زير مسأله اندازه هر يک ½ ‏ براي هر زيرمسأله ادغام از درجه ) O(nاست. ‏ ‏a=2b=2k=1 21 = 2است .در نتيجه طبق تئوري Masterمرتب سازي ادغام از درجه ) O(n log2nاست. ‏ ‏ ‏ ‏ چون هميشه در tempArrayجلو مي رويم. مرتب سازي ادغام هم در حال متوسط و هم در بدترين حالت هميشه از درجه ) O(n log2nاست. ديگر پيچيدگي الگوريتم وابسته به کيفيت محور نيست. Space Complexity of ‏Mergesort در مرتب سازي ادغام به يک آرايه موقت با سايز ) O(nنياز داريم. تعداد توابع بازگشتي: هميشه برابر )O(log2nاست. Tradeoffs تعدادي داده تصادفي داده شده اند .Mکدام حالت بهتر است؟ جستجوي خالي مرتب سازي Quicksortو مرتب سازي ادغام فرض کنيد nداده و Zجستجو داريم: جستجوي داده تصادفيZ * O(n) : مرتب سازي ادغام و جستجوي دودوييO(nlog2n) + Z : *log2n Tradeoffs Z * n <= nlog2n + Zlog2n Z(n - log2n) <= n log2n Z <= (n log2n) / (n-log2n) Z <= (n log2n) / n [Approximation] Z <= log2n [Approximation] در اين حالت اگر. جستجو هزينه مرتب سازي جبران مي شدN در دو روش قبلي بعد از . بيشتر باشد مرتب سازي سودمند خواهد بودlog2n تعداد جستجوها از 1,000,000 items = 19 searches, instead of 1,000,000 ?How Fast اگر Mاز روش مقايسه و جابجايي استفاده کنيم ،بهترين مرتب سازي ممکن از لحاظ تئوري داراي پيچيدگي )O(n log2n است. اثبات :درخت تصميم گيري- هر گره يک مقايسه است و هر شاخه يک نتيجه حرکت در درخت نحوه اجراي الگوريتم را نشان مي دهد. How Fast? K1 <= K2 [1,2,3] Yes No [1,2,3] K2 <= K3 Yes K1 <= K3 Yes No [1,2,3] [2,1,3] stop K1 <= K3 [1,3,2] Yes stop [1,3,2] No stop [3,1,2] [2,1,3] No [2,3,1] stop K2 <= K3 Yes stop [2,3,1] No stop [3,2,1] ?How Fast در اين درخت !nبرگ وجود دارد که هر برگ يک جواب از مسأله است. لذا هر Mالگوريتمي که با درخت تصيم گيري مدMل شود داراي !nحالت است. ارتفاع درخت تصميم گيري با پيچيدگي الگوريتم برابر است. چون درخت دودويي است ،ارتفاع درخت در بهترين حالت برابر log2n! + 1است. How Fast? n! n!==(n)(n-1)(n-2)(n-3) (n)(n-1)(n-2)(n-3)… …(3)(2)(1) (3)(2)(1) >>(n)(n-1)(n-2)(n-3) (n)(n-1)(n-2)(n-3)… …ceil(n/2) ceil(n/2)// //doing doingfewer fewermultiplies multiplies (ciel(n/2)) // doing multiplies of bigger things >>ceil(n/2) ceil(n/2)(ciel(n/2)) // doing multiplies of bigger things (n/2) >>approximately approximately(n/2) (n/2)(n/2) (n/2) log log22 n! n!>>log log22(n/2) (n/2)(n/2) log //exponentiation log22 n! n!>>(n/2) (n/2)log log22(n/2) (n/2) //exponentiationin inlogs logs==multiplication multiplication out outfront front log log22 n! n!>>(n/2)(log (n/2)(log22n n––log log22 2) 2)// //division divisionin inlogs logs==subtraction subtraction log log22 n! n!>>(n/2)(log (n/2)(log22n n––1) 1) log log22 n! n!>>(n/2)(log (n/2)(log22n) n)––(n/2) (n/2) log log22 n! n!>>(1/2) (1/2)[nlog [nlog22n n––n] n] log log22 n! n!~~O(n O(nlog log22n) n)