مرتب سازی بازگشتی داده ها

صفحه 1:
ساختمان داده ها مرتب سازی بازگشتی 

صفحه 2:
جستجوی دودویی بازگشتی int bsearch(ListItem[] L, int k, int low, int high) { int mid = (low + high)/2; lif (low > high) return -1; lelse if (L[mid].key == return mid; else if (L[mid].key < k) return bsearch(L, k, mid+1, high); else return bsearch(L, k, low, mid-1); حالت پایه 

صفحه 3:
جستجوی دودویی بازگشتی int bsearch(ListItem[] L, int k, int low, int high) { int mid = (low + high)/2; if (low > high) return -1; else if (L[mid].key == k) return mid; else if (L[mid].key < k) return bsearch(L, k, mid+1, high)} else retufn bsearch(L, k, low, m 1 (a) < ‏(ماه‎ 

صفحه 4:
مرتب سازی ادغام: راهبرد تقسیم و پیشروی 318]5]1]7]2[514[ ae divide Ay 3[8[6|1} 7۱254 recursively sor 1]8]618[ 2۱4517 “sy merge “x 1 2 34 5] 7 8} 

صفحه 5:
مرتب سازی ادغام بازگشتی تقسیم و پیشروی: ليست رايه طور مرتب به لیستهای کوچکتر تقسیم کنید تا تعداد عناصر هر لیست به دو عنصر برسد. * این لیستهای کوچک را مرتب کنید. * پیشروی: لیستهای کوچک مرتب شده را با هم ادغام کنید. AMM Hee جر عم کی ۵ 1۳۲۲ ۲۲ مركم 

صفحه 6:
MergeSort ‎eee‏ اك ‎we‏ ‎ae ee ‏سه سه سس دس ‏رد 2 2 

صفحه 7:
ادغام بازگشتی 7 ,51 دو مجموعم ی مرتبهستند. :: Ei sz [2] 8] ‎|e‏ 8 | 0 2 جواب 

صفحه 8:
مرتب سازی ادغام void mergeSort(int[] A, int start, int end) { // base case can be ignored if (start < end) { int mid = (start+end)/2; // sort left half mergeSort(A, start, mid); // sort right half mergeSort(A, mid+1, end); // now merge the two halves merge(A, start, mid, end); 

صفحه 9:
مرتب سازی ادغام void mergeSort(int[] A, int start, int end) { // base case can be ignored if (start < end) { int mid = (start+end)/2; /7 sort left half mergeSort(A, start, mid); // sort right half mergeSort(A, mid+1, end); //_now merge the two halves merge(A, start, mid, end)] 

صفحه 10:
مرتب سازی ادغام void mergeSort(int[] A, int start, int end) { // base case can be ignored if (start < end) { int mid = (start+end)/2; /7 sort left half mergeSort(A, start, mid)|; 8 * (We) // sort right half mergeSort(A, mid+1, end)|; merge(A, start, mid, end 

صفحه 11:
ادغام دو ليست مرتب * از ابتدای هر دو ليست شروع كنيد. * هر ليست را از جب به راست ييمايش كنيد و هر دو ليست را به ترتيب مورد نظر با هم تركيب كنيد ونتیجه را در یک آرایه موقت ذخیره کنید. *زمان اجرا چقدر است؟ 

صفحه 12:
مرتب سازی ادغام void mergeSort(int[] A, int start, int end) { // base case can be ignored if (start < end) { int mid = (start+end)/2; /7 sort left half mergeSort(A, start, mid)); © * We) // sort right half mergeSort(A, mid+1, end)); //_now merge the two halves merge(A, start, mid, end)| <=b*a 

صفحه 13:
مرتب سازی ادغام (ادامه...) public void merge(int[] a, int low,int mid,int high) { int h,i, nt b[]=new int[50]; h=low; i=low; j=mid+1; while((h id) &&(j<=high)) { iffath]<=alj]) { bfiJ=alh]; h++; } else { bliJ=alj]; j++; i++; } if(h>mid) { for(k=, =high;k++) { blil=alk]; i++; ‏واه‎ ) for(k=h;k<=mid;k++) { =alk]; i++; for(k=low;k<=high;k++) a[k]=b[k]; 

صفحه 14:
زمان اجرای مرتب سازی ادغام فرض کنید که (۲)۳ زمان اجرای متد بازگشتی باشد, و 3 و 0 دو ثابت بزرگتر از صفر هستند. می توان مرتب سازی ادغام را به صورت زیر فرموله کرد: +( * 6 > زوم ‎O(a bys)‏ = 

صفحه 15:
مرتب سازی ادغام به یک فضای اضافی نیاز دارد. "مرتب سازی ادغام بر خلاف مرتب سازی انتخابی کار را در محل انجام نمی دهد و به یک مجموعه ی موقت نیازمند است. "مصرف حافظه دو برابر بیشتر است. "خلاصه ی مرتب سازی درجی: *هر سطح از مرتب سازی درجی به !۲ مقایسه نیاز دارد. * تعداد سطوح برابر لاد۱۵9 است. * تعداد مقایسه ها برابر (0)۱1۱091 است. 

صفحه 16:
مرتب سازی سریع "یک عنصر را به عنوان محور انتخاب کنید (مثلاً اولین عنصر لیست) *آرایه را بر حسب محور به دو لیست کوچکتر تقسیم کنید. ؟ محور اکنون در جای درست خود قرار دارد. به طور بازگشتی لیستهای دو طرف محور را مرتب کنید. 

صفحه 17:
مرتب سازی سریع partition into large and small numbers recursively sort each section 6/7 |8} 

صفحه 18:
مرتب سازی سریع void quicksort(int[] A, int start, int end) { // base case can be ignored if (start < end) { // find a pivot int p = choosepivot(A, start, end); // partition and save new position // of pivot p = partition(A, start, end, p); // recursively sort quicksort(A, start, p-1); quicksort(A, p+1, end); 

صفحه 19:
مرتب سازی سریع void quicksort(int[] A, int start, int end) { // base case can be ignored if (start < end) { // find a _pivo int p = choose ot(A, start, end]; // partition and save new position //_of pivot p = partition(A, start, end, p)|; // recursively sort quicksort(A, start, p-1); quicksort(A, p+1, end); 1 ‏"تا‎ 

صفحه 20:
مرتب سازی سریع void quicksort(int[] A, int start, int end) { // base case can be ignored if (start < end) { // find a _pivo 00 int p = choosepivot(A, start, end]; // partition and save new position //_of pivot p = partition(A, start, end, p)|; // recursively sort quicksort(A, start, p-1); quicksort(A, p+1, end); <r(p) + (ov) 

صفحه 21:
مرتب سازی سریع * الگوریتم تقسیم بندی با انتخاب یکی از عناصر ‎abl‏ ‏به عنوان محور شروع می شود. ° اعداد کوچکتر یا مساوی محور وارد لیست سمت چپ و اعداد بزرگتر وارد لیست ‎crow‏ راست می شوند. * در حین اجرا الگوریتم چهار ناحیه دارد: ۰ اعداد کوچکتر مساوی محور. * اعداد بزرگتر از محور. + اعدادی که هنوز آزمایش نشده اند. خود محور. 

صفحه 22:
تقسیم بندی "ما یک عنصر محور به اسم []۸ داریم. *از یک آرایه موقت استفاده کنید. اعداد کوچکتر مساوی [۸۲0 را به سمت چپ و اعداد بزرگتر از [۸]0 را به سمت راست اضافه کنید. *آرایه ی تقسیم شده را در آرایه ی اصلی کپی کنید. *زمان اجرا چقدر است؟ 

صفحه 23:
مرتب سازی سریع void quicksort(int[] A, int start, int end) { // base case can be ignored if (start < end) { // find a pivot Int p = choosepivot(A, Start, end)} // partition and save new position //_of pivot <eb*a p = partition(A, start, end, p)|; // recursively sort quicksort(A, start, p-1); quicksort(A, p+1, end); 

صفحه 24:
‎gle wage gull‏ شرع ‏*فرض کنید که ‎r(n)‏ زمان اجرای متد بازگشتی ‏باشد. ‏“فرض كنيد كه هر بار ليست را به صورت ‏متعادل تقسيم مى كنيم: يعنى 0-1/2. در اين صورت داريم: ‎r(al) + bt‏ * 6 عه زمر ‎= O(abys) 

صفحه 25:
بدترین حالیت مرتب سازی سریع *فرض کنید که (۲)۲ زمان اجرای متد بازگشتی باشد. نامتعادل تقسیم می کنیم, یعنی 0<21. در این صورت داریم: (x) <= r() + (ed) + ‏هو‎ ‎Er(orl) + ‏میا‎ + 0)©( 

صفحه 26:
دلیل محبوبیت مرتب سازی سریع چیست؟ *اگر محور را به صورت تصادفی انتخاب کنیم, احتمال تقسیم نامتعادل در عمل خیلی کم خواهد بود. *می توانیم از خود آرایه برای تقسیم بندی استفاده کنیم و دیگر نیازی به آرایه ی موقت نداریم. " مرتب سازی سریع یکی از توابع سیستمی مرتب سازی در سیستم عاملهای یونیکس است. 

صفحه 27:
مرتب سازی سریع ° ° 3 ° هر دوی ‎Mergesort 5 Quicksort‏ از درجه ی (0)۱1۱09۱۱ هستند. کلاس 3۷3۰021:۱.۵۲۲۵۷5ز نسخه های بارگذاری شده ی متعددی از متد ایستای 50۲۲() را دارد. در مورد آرایه های انواع اصلی از مرتب سازی سریع بهینه شده استفاده می شود که احتمال وقوع بدترین حالت در آن خیلی کم است. در مورد آرایه های اشیاء از مرتب سازی ادغام استفاده می شود. ۶ تفاوت در این است که دو شی که با هم برابر هستند لزوماً یکی نیستند. آگر مرتب سازی ترتیب این گونه عناصر را به هم نزند و ترتیب آنها مثل آرایه ی اصلی باشد می گوییم که الگوریتم مرتب