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

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

اسلاید 1: Sorting Algorithms 2

اسلاید 2: Quicksortالگوريتم کلي quicksortيکي از عناصر را به عنوان محور انتخاب کنيد.عناصر را به دو زير مجموعه چپ و راست تقسيم کنيد.تمام عناصر زير مجموعه سمت چپ از محور کوچکتر هستند.تمام عناصر زير مجموعه سمت رلست از محور يزرگتر هستند.الگوريتم را براي زير مجموعه هاي بدست آمده تکرار کنيد.نيازي به ادغام نداريم محور در هر مرحله سر جاي درست خود قرار دارد.

اسلاید 3: Quicksortvoid quicksort(int* arrayOfInts, int first, int last) { int pivot; if (first < last) { pivot = partition(arrayOfInts, first, last); quicksort(arrayOfInts,first,pivot-1); quicksort(arrayOfInts,pivot+1,last); } }

اسلاید 4: Quicksortint 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; }

اسلاید 5: 953201891832059318205Partition Step Throughpartition(cards, 0, 4)P = 0 K = 1P = 1 K = 3cards[1] < cards[0] ? Nocards[3] < cards[0]? YesP = 2P = 0 K = 2temp = cards[3]cards[2] < cards[0] ? Yescards[3] = cards[2]P = 1cards[2] = cards[3]temp = cards[2]P = 2 K = 4cards[2] = cards[1]cards[4] < cards[0]? Nocards[1] = temptemp = cards[2], cards[2] = cards[first]cards[first] = temp, return p = 2;3918205

اسلاید 6: Complexity of Quicksortبدترين حالت: O(n2)بدترين حالت کي اتفاق مي افتد؟ليست مرتب يا تقريبا مرتبزير مجموعه هاي بدست آمده نامتعادل خواهند شد.در حالت متوسط پيچيدگي برابر O(n log2n) است حالت متوسط اين الگوريتم حالت غالب است

اسلاید 7: Complexity of Quicksortرابطه بازگشتي: (حالت متوسط) 2 زير مساله داريم.اگر محور خوب باشد سايز هر کدام ½ مساله اصلي است.هزينه تابع partition برابر O(n)است.a = 2 b = 2 k = 12 = 21تئوري master: O(nlog2n)

اسلاید 8: Complexity of Quicksortرابطه بازگشتي: (بدترين حالت) دو زير مجموعه با سايز هاي 1 و n-1 خواهيم داشت. نمي شود از تئوري master استفاده کرد. چون b يعني اندازه زير مسائل ثابت نيست. n-1/n n-2/n-1 n-3/n-2اما مي شود اعداد را با هم جمع کرد:n + (n-1) + (n-2) + (n-3) …Sum(1,N) = N(N+1)/2= O(N2)

اسلاید 9: Complexity of Quicksortبراي پياده سازي quicksort به فضاي پشته نياز داريم.بدترين حالت: فضاي پشته برابرO(n) است. اگر دو زير مجموعه با سايز هاي 1 و n-1 توليد شود.حالت متوسط: O(log n)اگر محور درست انتخاب شده باشد.

اسلاید 10: MergeSortالگوريتم ادغام: هر بار آرايه به دو زير مجموعه مساوي تقسيم شود. سپس زيرمجموعه ها را با هم ادغام کنيد.تقسيم را تا وقتي ادامه دهيد که به يک عنصر برسيد.يک مجموعه تک عنصري خود به خود مرتب است.سپس زير مجموعه ها را طوري با هم ادغام کنيد که مجموعه حاصل مرتب باشد.1+1 item subarrays => 2 item subarrays2+2 item subarrays => 4 item subarraysاز اين حقيقت که زير مجموعه ها مرتب هستند براي ادغام استفاده کنيد.

اسلاید 11: MergeSortvoid 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); }}

اسلاید 12: MergeSortvoid 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 smallerarray[k++] = tempArray[i++];// put in final array, increment else// final array position, lhs indexarray[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

اسلاید 13: MergeSort ExampleRecursively Split20318952031895

اسلاید 14: MergeSort ExampleRecursively Split20318952031895

اسلاید 15: MergeSort ExampleMerge2031895

اسلاید 16: Merge Sort ExampleTemp ArrayijArrayTemp[i]< Temp[j]Yes2 cardsNot very interestingThink of as swap20318203203k3

اسلاید 17: MergeSort ExampleTemp ArrayijArrayTemp[i]< Temp[j]Nokبايد j را زياد کنيم. j از high بيشتر مي شود و حلقه اول تمام مي گردد. حال بايد حلقه دوم را تا وقتي که i برابر medium شود ادامه دهيم. 18203318k20Array183

اسلاید 18: MergeSort Example2 Card SwapFinal aftermergingabove sets955920183593i=1,j=35i=1,j=4i=0,j=39i=1,j=518i=2,j=520i=3,j=5

اسلاید 19: Complexity of MergeSortرابطه بازگشتي:2 زير مسألهاندازه هر يک ½ براي هر زيرمسأله ادغام از درجه O(n) است.چون هميشه در tempArray جلو مي رويم. a = 2 b = 2 k = 12 = 21 است. در نتيجه طبق تئوري Master مرتب سازي ادغام از درجه O(n log2n) است. مرتب سازي ادغام هم در حال متوسط و هم در بدترين حالت هميشه از درجه O(n log2n) است.ديگر پيچيدگي الگوريتم وابسته به کيفيت محور نيست.

اسلاید 20: Space Complexity of Mergesortدر مرتب سازي ادغام به يک آرايه موقت با سايز O(n) نياز داريم.تعداد توابع بازگشتي:هميشه برابر O(log2n)است.

اسلاید 21: Tradeoffsتعدادي داده تصادفي داده شده اند. کدام حالت بهتر است؟جستجوي خاليمرتب سازي Quicksort و مرتب سازي ادغامفرض کنيد n داده و Z جستجو داريم:جستجوي داده تصادفي: Z * O(n)مرتب سازي ادغام و جستجوي دودويي: O(nlog2n) + Z *log2n

اسلاید 22: TradeoffsZ * n <= nlog2n + Zlog2nZ(n - log2n) <= n log2nZ <= (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

اسلاید 23: How Fast?اگر از روش مقايسه و جابجايي استفاده کنيم ، بهترين مرتب سازي ممکن از لحاظ تئوري داراي پيچيدگي O(n log2n) است.اثبات: درخت تصميم گيري- هر گره يک مقايسه است و هر شاخه يک نتيجهحرکت در درخت نحوه اجراي الگوريتم را نشان مي دهد.

اسلاید 24: How Fast?K1 <= K2[1,2,3]K2 <= K3K1 <= K3[1,2,3][2,1,3]YesNostopK1 <= K3YesNoK2 <= K3stopstopstopstopstopYesYesYesNoNoNo[1,2,3][1,3,2][2,1,3][1,3,2][3,1,2][2,3,1][2,3,1][3,2,1]

اسلاید 25: How Fast?در اين درخت n! برگ وجود دارد که هر برگ يک جواب از مسأله است.لذا هر الگوريتمي که با درخت تصيم گيري مدل شود داراي n! حالت است. ارتفاع درخت تصميم گيري با پيچيدگي الگوريتم برابر است.چون درخت دودويي است ، ارتفاع درخت در بهترين حالت برابر log2n! + 1 است.

اسلاید 26: How Fast?n! = (n)(n-1)(n-2)(n-3) … (3)(2)(1) > (n)(n-1)(n-2)(n-3) … ceil(n/2) // doing fewer multiplies > ceil(n/2) (ciel(n/2)) // doing multiplies of bigger things > approximately (n/2)(n/2)log 2 n! > log 2 (n/2)(n/2) log 2 n! > (n/2) log 2 (n/2)//exponentiation in logs = multiplication out frontlog 2 n! > (n/2)(log2n – log2 2) // division in logs = subtractionlog 2 n! > (n/2)(log2n – 1)log 2 n! > (n/2)(log2n) – (n/2)log 2 n! > (1/2) [nlog2n – n]log 2 n! ~ O(n log2n)