مرتب سازی انتخابی در سی پلاس پلاس (Selection Sort)

در این جلسه تیم کدگیت را با آموزش مرتب سازی انتخابی در سی پلاس پلاس همراهی کنید. پیش نیاز این آموزش کار با آرایه و تابع در سی پلاس پلاس است.

مرتب سازی انتخابی

مرتب‌سازی انتخابی یکی از انواع الگوریتم مرتب‌سازی می‌باشد که جزو دسته  الگوریتمهای مرتب‌سازی مبتنی بر مقایسه‌است. این الگوریتم دارای پیچیدگی زمانی از درجهٔ( O(n² است که به همین دلیل اعمال آن روی مجموعه بزرگی از اعداد کارا به نظرنمی رسدو به طور عمومی ضعیفتر از نوع مشابهش که مرتب‌ساز درجی است عمل می‌کند. این مرتب‌سازی به دلیل سادگی اش قابل توجه‌است. کارایی آن برحسب تعداد ورودیها در نمودار زیر نشان داده شده‌است(ویکیپدیا).

نحوه عملکرد

این الگوریتم اینگونه عمل می‌کند: ابتدا کوچکترین عنصر مجموعه اعداد را یافته با اولین عدد جابجا می‌کنیم. سپس دومین عنصر کوچکتر را یافته با دومین عدد جابجا می‌کنیم و این روند را برای n-1 عدد اول تکرار می‌کنیم. در حقیقت در هر مرحله ما لیست خود را به دو بخش تقسیم می‌کنیم. زیرلیست اول که قبلاً مرتب کرده‌ایم و سایر اعضای لیست که هنوز مرتب نشده‌است. در جدول زیر مثالی از پیاده‌سازی این روال بر روی ۶ عدد آمده‌است(ویکیپدیا)

پیاده سازی مرتب سازی انتخابی در سی پلاس پلاس

برای پیاده سازی مرتب سازی انخابی در سی پلاس پلاس ما از یک تابع به نام selection sort استفاده می‌کنیم. کل کاری که این متد انجام می‌دهد این است که یک آرایه را ورودی می‌گیرد و آن ورودی را مرتب کرده و به عنوان خروجی بر می‌گرداند.

void selectionSort(int arr[], int n) {

    int i, j, minIndex, tmp;



    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 تا خانه آخر آرایه دنبال عنصر کوچتر می‌گردیم).

تست برنامه

برای تست برنامه کد زیر را بزنید.

int main() {

    int size = 9;

    int input[] = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };

    cout << " Befor Sorting .." << endl;

    printNumbers(input, size);

    selectionSort(input, size);



    cout << " Befor Sorting .." << endl;

    printNumbers(input, size);



    return 0;

}

خروجی برنامه به صورت زیر است.

Befor Sorting ..

4, 2, 9, 6, 23, 12, 34, 0, 1,

 after Sorting ..

0, 1, 2, 4, 6, 9, 12, 23, 34,

پسورد: www.codegate.ir