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

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

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

اسلاید 2: 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);elsereturn 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);elsereturn bsearch(L, k, low, mid-1);}جستجوی دودویی بازگشتیr(n) = O(logan)

اسلاید 4: مرتب سازی ادغام: راهبرد تقسیم و پیشروی

اسلاید 5: مرتب سازی ادغام بازگشتیتقسیم و پیشروی: لیست را یه طور مرتب به لیستهای کوچکتر تقسیم کنید تا تعداد عناصر هر لیست به دو عنصر برسد.این لیستهای کوچک را مرتب کنید. پیشروی: لیستهای کوچک مرتب شده را با هم ادغام کنید. 417653824176538241765382

اسلاید 6: MergeSort12345678417653824176538241765382

اسلاید 7: ادغام بازگشتیS1, S2 دو مجموعه ی مرتب هستند.53825382جوابS1S2

اسلاید 8: مرتب سازی ادغامvoid mergeSort(int[] A, int start, int end) {// base case can be ignoredif (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 ignoredif (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);}}

اسلاید 10: مرتب سازی ادغامvoid mergeSort(int[] A, int start, int end) {// base case can be ignoredif (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);}}2 * r(n/2)

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

اسلاید 12: مرتب سازی ادغامvoid mergeSort(int[] A, int start, int end) {// base case can be ignoredif (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);}}2 * r(n/2)<= b*n

اسلاید 13: مرتب سازی ادغام (ادامه...)public void merge(int[] a, int low,int mid,int high) { int h,i,j,k; int b[]=new int[50]; h=low; i=low; j=mid+1; while((h<=mid)&&(j<=high)) { if(a[h]<=a[j]) { b[i]=a[h]; h++; } else { b[i]=a[j]; j++; } i++; } if(h>mid) { for(k=j;k<=high;k++) { b[i]=a[k]; i++; } } else { for(k=h;k<=mid;k++) { b[i]=a[k]; i++; } } for(k=low;k<=high;k++) a[k]=b[k]; }

اسلاید 14: زمان اجرای مرتب سازی ادغامفرض کنید که r(n) زمان اجرای متد بازگشتی باشد، و a و b دو ثابت بزرگتر از صفر هستند.می توان مرتب سازی ادغام را به صورت زیر فرموله کرد:r(n) < = 2 * r(n/2) + b * n = O(n log n)

اسلاید 15: مرتب سازی ادغام به یک فضای اضافی نیاز دارد.مرتب سازی ادغام بر خلاف مرتب سازی انتخابی کار را در محل انجام نمی دهد و به یک مجموعه ی موقت نیازمند است.مصرف حافظه دو برابر بیشتر است.خلاصه ی مرتب سازی درجی:هر سطح از مرتب سازی درجی به N مقایسه نیاز دارد.تعداد سطوح برابر log2N است. تعداد مقایسه ها برابر O(NlogN) است.

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

اسلاید 17: مرتب سازی سریع

اسلاید 18: مرتب سازی سریعvoid quicksort(int[] A, int start, int end) {// base case can be ignoredif (start < end) {// find a pivot int p = choosepivot(A, start, end);// partition and save new position // of pivotp = 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 ignoredif (start < end) {// find a pivot int p = choosepivot(A, start, end);// partition and save new position // of pivotp = partition(A, start, end, p);// recursively sort quicksort(A, start, p-1);quicksort(A, p+1, end);}}مرتب سازی سریع

اسلاید 20: void quicksort(int[] A, int start, int end) {// base case can be ignoredif (start < end) {// find a pivot int p = choosepivot(A, start, end);// partition and save new position // of pivotp = partition(A, start, end, p);// recursively sort quicksort(A, start, p-1);quicksort(A, p+1, end);}}مرتب سازی سریعO(1)<= r(p) + r(n-p)

اسلاید 21: مرتب سازی سریعالگوریتم تقسیم بندی با انتخاب یکی از عناصر آرایه به عنوان محور شروع می شود. اعداد کوچکتر یا مساوی محور وارد لیست سمت چپ و اعداد بزرگتر وارد لیست سمت راست می شوند.در حین اجرا الگوریتم چهار ناحیه دارد:اعداد کوچکتر مساوی محور.اعداد بزرگتر از محور. اعدادی که هنوز آزمایش نشده اند. خود محور.

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

اسلاید 23: void quicksort(int[] A, int start, int end) {// base case can be ignoredif (start < end) {// find a pivot int p = choosepivot(A, start, end);// partition and save new position // of pivotp = partition(A, start, end, p);// recursively sort quicksort(A, start, p-1);quicksort(A, p+1, end);}}مرتب سازی سریع <= b * n

اسلاید 24: آنابیز مرتب سازی سریعفرض کنید که r(n) زمان اجرای متد بازگشتی باشد. فرض کنید که هر بار لیست را به صورت متعادل تقسیم می کنیم، یعنی p=n/2. در این صورت داریم:r(n) <= 2 * r(n/2) + b*n= O(n log n)

اسلاید 25: بدترین حالیت مرتب سازی سریعفرض کنید که r(n) زمان اجرای متد بازگشتی باشد.فرض کنید که هر بار لیست را به صورت نامتعادل تقسیم می کنیم، یعنی p=1. در این صورت داریم:R(n) <= r(1) + r(n-1) + b*n = r(n-1) + b*n + b O(n2)

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

اسلاید 27: مرتب سازی سریعهر دوی Quicksort و Mergesort از درجه ی O(NlogN) هستند. کلاس java.util.Arrays نسخه های بارگذاری شده ی متعددی از متد ایستای sort() را دارد. در مورد آرایه های انواع اصلی از مرتب سازی سریع بهینه شده استفاده می شود که احتمال وقوع بدترین حالت در آن خیلی کم است. در مورد آرایه های اشیاء از مرتب سازی ادغام استفاده می شود.تفاوت در این است که دو شی که با هم برابر هستند لزوماً یکی نیستند. اگر مرتب سازی ترتیب این گونه عناصر را به هم نزند و ترتیب آنها مثل آرایه ی اصلی باشد می گوییم که الگوریتم مرتب سازی پایدار است. مرتب سازی ادغام پایدار است ولی مرتب سازی سریع نه.