مرتب سازی الگوریتم ها 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 ۱۳ ۱۳ ۳ ۱۳