Java sort
مرتب سازی انتخابی (Selection Sort)
Java sort
مرتبسازی انتخابی یکی از انواع الگوریتم مرتبسازی میباشد که جزو دسته الگوریتمهای مرتبسازی مبتنی بر مقایسه‌است. این الگوریتم دارای پیچیدگی زمانی از درجهٔ (O(n2 است که به همین دلیل اعمال آن روی مجموعه بزرگی از اعداد کارا به نظرنمی رسدو به طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل میکند. این مرتبسازی به دلیل سادگی اش قابل توجه‌است. کارایی آن برحسب تعداد ورودیها در نمودار زیر نشان داده شده‌است
این الگوریتم اینگونه عمل میکند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا میکنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا میکنیم و این روند را برای n-1 عدد اول تکرار میکنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم میکنیم. زیرلیست اول که قبلاً مرتب کرده‌ایم و سایر اعضای لیست که هنوز مرتب نشده‌است.
پیاده سازی مرتب سازی انتخابی
Java sort
برای پیاده سازی مرتب سازی انخابی در جاوا ما از یک متد به نام selection sort استفاده میکنیم. کل کاری که این متد انجام میدهد این است که یک آرایه را ورودی میگیرد و آن ورودی را مرتب کرده و به عنوان خروجی بر میگرداند.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | public static void selectionSort(int[] arr) { int i, j, minIndex, tmp; int n = arr.length; for (i = 0; i < n - 1; i++) { minIndex = i; for (j = i + 1; j < n; j++) if (arr[j] < arr[minIndex]) minIndex = j; if (minIndex != i) { tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } } } |
همانطور که در کد مرتب سازی انتخابی در جاوا میبینید ما یک متغیر به نام min index داریم.حلقه دوم یک دور کل آرایه میچرخد و اگر خانه ای کوچکتر از min index بود اندیس آن را به عنوان min index قرار میدهد. سپس بعد از یک دور کامل ما اندیس کوچکترین خانه را داریم و آن را با خانه i (دور اول میشود اولین خانه آرایه) عوض میکنیم. در دور بعد نیز همین روال را ادامه میدهیم فقط دومین خانه کوچکتر را در دور بعد پیدا میکنیم(دور بعد یکی به i اضافه میشود و ما از خانه i تا خانه آخر آرایه دنبال عنصر کوچتر میگردیم).
تست برنامه
Java sort
برای تست برنامه کد زیر را بزنید.
1 2 3 4 5 6 7 8 9 10 | public static void main(String[] args) { int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 }; System.out.println("befor sort"); selectionSort(input); for (int i = 0; i < input.length; i++) { System.out.print(input[i] + ", "); } System.out.println(); } |
خروجی برنامه به صورت زیر است.
1 | 0, 1, 2, 4, 6, 9, 12, 23, 34, |
مرتب سازی سریع
Java sort
مرتب سازی سریع، یکی از الگوریتمهای مرتبسازی است که به‌دلیل مصرف حافظه کم، سرعت اجرای مناسب و پیاده‌سازی ساده بسیار مورد قبول واقع شده‌است.
هر پیاده‌سازی این الگوریتم به‌صورت کلی از دو بخش تشکیل شده‌است. یک بخش تقسیم‌بندی آرایه (partition) و قسمت مرتب کردن. روش مرتبسازی سریع (Quick Sort) یکی از الگوریتمهای مشهور مرتبسازی داده‌ها است. این الگوریتم طی مراحل بازگشتی زیر یک روش تقسیم و غلبه برای مرتب کردن داده‌ها ارائه می‌نماید:
- انتخاب عنصر محوری: یکی از عناصر آرایه به عنوان عنصر محوری (pivot) – به عنوان مثال عنصر اول – انتخاب میشود.
- تقسیم آرایه: چینش عناصر آرایه به قسمی تغییر داده میشود که تمامی عناصر کوچکتر یا مساوی محور در سمت چپ آن، و تمامی عناصر بزرگتر در سمت راست آن قرار بگیرند. این دو قسمت زیر آرایه‌های چپ و راست نامیده می‌شوند.
- مرتبسازی بازگشتی: زیرآرایه‌های چپ و راست به روش مرتبسازی سریع مرتب می‌شوند
پیاده سازی مرتب سازی سریع
Java sort
برای پیاده سازی مرتب سازی سریع ما از روش بازگشتی استفاده میکنیم بدین صورت که ابتدا یک آرایه در نظر میگیریم سپس یک عنصر را به عنوان pivot در نظر میگیریم (در پیاده سازی ما همیشه آخرین عنصر در نظر میگیرد) سپس آرایه را partition میکنیم یعنی تمامی عناصر کوچکتر از pivot را به خانه های قبلی pivot میبریم و بزرگترها را به خانه های بعدی pivot سپس همین کار را برای خانه های قبلی و بعدی pivot انجام میدهیم. این کار را تا موقعی انجام میدهیم که فقط یک خانه باقی بماند.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | private static void quicksort(int[] a, int s, int e) { if(s>=e) return; int q = partition(a,s,e); quicksort(a, s, q-1); quicksort(a, q+1, e); } private static int partition(int[] a, int s, int e) { int x = a[e]; int i = s-1; for(int j = s;j<e;++j){ if(a[j]<=x){ ++i; int temp = a[i]; a[i]= a[j]; a[j]=temp; } } ++i; int temp = a[i]; a[i]= a[e]; a[e]=temp; return i; } |
کد مرتب سازی سریع در جاوا دارای دو متد میباشد
- Quicksort
- Partition
در متد quicksort ما آرایه را partition میکنیم و بر اساس pivot بقیه آرایه را مرتب میکنیم. در متد partition ابتدا عنصر آخر را pivot میگیریم سپس خانه های کوچکتر از آن را از اول آرایه شروع به چیدن میکنیم(خانه های قبل از pivot مرتب نیستند و فقط کوچکتر از pivot هستند). سپس که کل آرایه را چرخیدیم عنصر pivot را در مکان خود قرار میدهیم(pivot باید بعد از خانه هایی باشد که میدانیم از آن کوچکتر باشند متغیر i در کد بالا همین کار میکند).
تست مرتبسازی سریع
Java sort
برای اجرای برنامه بالا کد main زیر را بنویسید.
1 2 3 4 5 6 7 8 9 | public static void main(String[] args) { int a[] = {5,4,3,2,1}; quicksort(a, 0, a.length-1); System.out.println(Arrays.toString(a)); } |
خروجی برنامه
1 | [۱, ۲, ۳, ۴, ۵] |
مرتب سازی حبابی (Bubble Sort)
Java sort
روش کار این الگوریتم بسیار ساده می باشد. بطور خلاصه در این الگوریتم ابتدا دو عنصر اول آرایه با هم مقایسه می شوند. بهتر است بگوییم عنصر اول با عنصر دوم آرایه مقایسه می شود. اگر عنصر اول از عنصر دوم بزرگتر بود، جای دو عنصر فوق با یکدیگر عوض می شود. در غیر این صورت «منظور عنصر اول از دومی کوچکتر باشد» ، الگوریتم به سراغ عنصر دوم و سوم رفته و عمل مقایسه را انجام می دهد. این عمل تا آخرین خانه آرایه ادامه می یابد. سپس الگوریتم دوباره به ابتدای آرایه بازگشته و عملیات قبل را بر آرایه که اکنون در وضعیت جدیدی به سر می برد تکرار می کند. دقت کنید که در هر بار بررسی آرایه توسط الگوریتم، بزرگترین عنصر مرتب نشده آرایه در جای خود قرار می گیرد. پس در هر دور جدید بررسی آرایه برای مرتب سازی آن، الگوریتم یک خانه را نسبت به دور قبل در نظر نخواهد گرفت. مثلا اگر الگوریتم قصد مرتب سازی آرایه را برای چهارمین عنصر آرایه داشته باشد، یعنی سه عنصر بزرگتر آرایه در جای خود قرار گرفته اند و دیگر نیازی نیست تا الگوریتم آن خانه های آرایه که حاوی مقادیر فوق می باشند را بررسی نماید و در نتیجه فقط خانه های حاوی مقادیر مرتب نشده را مجددا بررسی می کند.
بررسی پیچیدگی زمانی الگوریتم
Java sort
1 2 3 4 5 | W.C : o(n2) AVG.C: o(n2) B.C: o(n) |
علت اینکه در بهترین حالت پیچیدگی زمانی وضعیت مطلوب تری نسبت به دو حالت قبل دارد آن است که ممکن است در این حالت، بخشی از آرایه مرتب شده باشد.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | public class bubbleSort{ public static void main(String a[]){ int i; int array[] = {12,9,4,99,120,1,3,10}; System.out.println("Values Before the sort:\n"); for(i = 0; i < array.length; i++) System.out.print( array[i]+" "); System.out.println(); bubble_srt(array, array.length); System.out.print("Values after the sort:\n"); for(i = 0; i <array.length; i++) System.out.print(array[i]+" "); System.out.println(); System.out.println("PAUSE"); } public static void bubble_srt( int a[], int n ){ int i, j,t=0; for(i = 0; i < n; i++){ for(j = 1; j < (n-i); j++){ if(a[j-1] > a[j]){ t = a[j-1]; a[j-1]=a[j]; a[j]=t; } } } } } |
