Algorytm Selection Sort – porządkowanie przez wybór

Algorytm Selection Sort – porządkowanie przez wybór

Specyfikacja:
Dane: Liczba naturalna n i ciąg n liczb x1, x2, …, xn
Wynik: Uporządkowane dane ciągu liczb od najmniejszej do największej, czyli ciąg wynikowy spełnia nierówność x1<= x2<= …<= xn (Uwaga! Elementy ciągu danego i wynikowego oznaczamy tak samo, gdyż porządkowanie odbywa się in situ, czyli „w miejscu”. ) Algorytm:
Krok 1: Dla i=1, 2, 3,…, n-1 wykonaj kroki 2 i 3, a następnie zakończ algorytm.
Krok 2: Znajdź k takie, xk jest najmniejszym elementem w ciągu xi,…, xn.
Krok 3: Zamień miejscami elementy xi oraz xk.


Zadanie: Zrealizuj powyższy problem dla wybranego n. Elementy losuj z zakresu
od -50 do 50.


Realizacja w C++ (kompilator Code::Blocks)

#include <iostream>

using namespace std;

int n;

int min_i(int tab[], int od)
{
    int min_in = 0;
    int min = 1000;

    for (int i = od; i<n; i++)
    {
        if (tab[i]<min)
        {
            min_in = i;
            min = tab[i];
        }

    }
    return min_in;
}


int main()
{
    srand(time(NULL));
    cout << "Podaj ilosc liczb do posortowania:";
    cin >>n;
    int tab[n];

    for (int i = 0 ; i < n ; i ++ )
    {
        tab[i] = rand()%101 -50 ;  // losujemy 101 liczb (od -50 do 50)
         cout.width(2);
        cout << i <<": " <<tab[i]<<endl;
    }



    cout <<endl <<"Po sortowaniu:" << endl;

    int k;
    for (int i = 0; i< n-1 ; i++ )
    {

        k = min_i(tab, i);
        swap(tab[i],tab[k]);
    }


    for (int i = 0 ; i < n ; i++ )
    {
        cout.width(2);
        cout << i <<": " <<tab[i]<<endl;
    }

    return 0;
}