در این جلسه، تیم کدگیت را با آموزش مرتب سازی انتخابی در جاوا همراهی کنید. پیش نیاز این آموزش کار با آرایه و متد در جاوا است.
مرتب سازی انتخابی
مرتبسازی انتخابی یکی از انواع الگوریتم مرتبسازی میباشد که جزو دسته الگوریتمهای مرتبسازی مبتنی بر مقایسهاست. این الگوریتم دارای پیچیدگی زمانی از درجهٔ (O(n2 است که به همین دلیل اعمال آن روی مجموعه بزرگی از اعداد کارا به نظرنمی رسدو به طور عمومی ضعیفتر از نوع مشابهش که مرتبساز درجی است عمل میکند. این مرتبسازی به دلیل سادگی اش قابل توجهاست. کارایی آن برحسب تعداد ورودیها در نمودار زیر نشان داده شدهاست(ویکیپدیا).
نحوه عملکرد
این الگوریتم اینگونه عمل میکند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا میکنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا میکنیم و این روند را برای n-1 عدد اول تکرار میکنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم میکنیم. زیرلیست اول که قبلاً مرتب کردهایم و سایر اعضای لیست که هنوز مرتب نشدهاست. در جدول زیر مثالی از پیادهسازی این روال بر روی ۶ عدد آمدهاست(ویکیپدیا)
پیاده سازی مرتب سازی انتخابی در جاوا
برای پیاده سازی مرتب سازی انخابی در جاوا ما از یک متد به نام selection sort استفاده میکنیم. کل کاری که این متد انجام میدهد این است که یک آرایه را ورودی میگیرد و آن ورودی را مرتب کرده و به عنوان خروجی بر میگرداند.
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 تا خانه آخر آرایه دنبال عنصر کوچتر میگردیم).
تست برنامه
برای تست برنامه کد زیر را بزنید.
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();
}
خروجی برنامه به صورت زیر است.
0, 1, 2, 4, 6, 9, 12, 23, 34,