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

مرتب سازی انتخابی، یکی از انواع الگوریتم های مرتب سازی می باشد که بدین گونه عمل می کند: در اولین گام کوچکترین عدد آرایه را پیدا می کنیم و با اولین عنصر آرایه جا به جا می نماییم. در گام دوم، دومین عدد کوچک را می یابیم و با عنصر دوم آرایه جا به جا می کنیم و این روند را برای n-1 خانه آرایه به طور مشابه انجام می دهیم. در نهایت آرایه مذکور را به شیوه انتخابی مرتب کرده ایم.

1- برنامه ای بنویسید که تعدادی عدد را از ورودی خوانده، آن ها را به روش انتخابی مرتب می کند و نتیجه را در خروجی چاپ می کند.

#include <iostream>

using namespace std;

void selection_in(int [], int);
void selection_sort(int [], int);
void selection_out(int [], int);
int main()
{
    int n;
    cout<<"Enter a number for n :";
    cin>>n;
    int selection[n];
    selection_in(selection, n);
    selection_sort(selection, n);
    selection_out(selection, n);
    return 0;
}

void selection_in(int selection[], int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<"Enter a number : ";
        cin>>selection[i];
    }
}

void selection_sort(int selection[], int n)
{
    int item, min_index;

    for(int i=0; i<n-1; i++)
    {
        min_index = i;
        for(int j=i+1; j<n; j++)
            if(selection[j] < selection[min_index])
                min_index = j;

        item = selection[i];
        selection[i] = selection[min_index];
        selection[min_index] = item;

    }
}

void selection_out(int selection[], int n)
{
    cout<<"sorted array : ";
    for(int i=0; i<n; i++)
        cout<<selection[i]<<" ";
}

این برنامه شامل 3 تابع می باشد. وقتی در بدنه اصلی برنامه تابع selection_in صدا زده می شود، این تابع فراخوانی می گردد و اعداد را از ورودی می گیرد و در آرایه selection قرار می دهد.

void selection_in(int selection[], int n)
{
    for(int i=0; i<n; i++)
    {
        cout<<"Enter a number : ";
        cin>>selection[i];
    }
}

دومین دستور فراخوانی در تابع ()main، تابع selection_sort را صدا می زند. این تابع آرایه را به روش انتخابی مرتب می کند.

void selection_sort(int selection[], int n)
{
    int item, min_index;

    for(int i=0; i<n-1; i++)
    {
        min_index = i;
        for(int j=i+1; j<n; j++)
            if(selection[j] < selection[min_index])
                min_index = j;

        item = selection[i];
        selection[i] = selection[min_index];
        selection[min_index] = item;

    }
}

به عنوان مثال، فرض کنید آرایه int selection[5] = {20, 3, 35, 11, 2} را به تابع selection_sort ارسال و به روش انتخابی مرتب می کنیم. در هر مرحله، در حلقه داخلی، j از i+1 تا 5 مقدار می گیرد که به ازای j = 5 شرط حلقه غلط و کار حلقه داخلی تمام می شود. در حلقه داخلی و به کمک دستور تصمیم if(selection[j] < selection[min_index]) اندیس کوچیکترین عنصر آرایه پیدا  و به کمک دستورات جا به جایی، عنصر این اندیس با عنصر اندیس i جا به جا می شود و بدین ترتیب در هر محله کوچکترین عدد به سمت چپ آرایه هدایت می گردد. این روند تا زمانی که شرط حلقه بیرونی غلط نشده ادامه می یابد. در پایین روند شناسایی کوچکترین عنصر آرایه و جا به جایی آن با عنصر اندیس i را، مرحله به مرحله مشاهده می کنید.

سومین دستور فراخوانی در تابع ()main، تابع selection_sort را فراخوانی و این تابع، آرایه مرتب شده selection را در خروجی چاپ می کند.

void selection_out(int selection[], int n)
{
    cout<<"sorted array : ";
    for(int i=0; i<n; i++)
        cout<<selection[i]<<" ";
}

برای مشاهده فهرست آموزش برنامه نویسی در ++C کلیک کنید.