Następny algorytm sortujący, który omówimy, ma złożoność rzędu $$O(n^2)$$ . Podobnie jak sortowanie bąbelkowe nie poradzi sobie przy porządkowaniu większych zbiorów.
Strategia sortowania przez wybór jest bardzo prosta. Szukamy najmniejszego elementu w zbiorze i zamieniamy go z elementem stojącym na pozycji pierwszej. Następnie szukamy znowu elementu najmniejszego w zbiorze pominiętym o pierwszy element i wstawiamy go na pozycję drugą. Czynności powtarzamy do momentu otrzymania jednoelementowego podzbioru. Rozpatrzmy przykład liczb:
$$3,\ 2,\ 4,\ 3,\ 1,\ 2,\ 0$$
Przeanalizujmy porządkowanie tych liczb metodą przez selekcję:
$$\overbrace{3}^{zamiana\ z\ 0},\ 2,\ 4,\ 3,\ 1,\ 2,\ 0$$
$$0,\ \overbrace{2}^{zamiana\ z\ 1},\ 4,\ 3,\ 1,\ 2,\ 3$$
$$0,\ 1,\ \overbrace{4}^{zamiana\ z\ 2},\ 3,\ 2,\ 2,\ 3$$
$$0,\ 1,\ 2,\ \overbrace{3}^{zamiana\ z\ 2},\ 4,\ 2,\ 3$$
$$0,\ 1,\ 2,\ 2,\ \overbrace{4}^{zamiana\ z\ 3},\ 3,\ 3$$
$$0,\ 1,\ 2,\ 2,\ 3,\ \overbrace{4}^{zamiana\ z\ 3},\ 3$$
$$0,\ 1,\ 2,\ 2,\ 3,\ 3,\ 4$$
Rozwiązanie w C++:
//algorytm.edu.pl
#include<iostream>
using namespace std;
void selection_sort(int tab[],int n) //n - ilość elementów do posortowania
{
int mn_index; //zmienna pomocnicza przechowująca indeks komórki
//z minimalną wartością
for(int i=0;i<n-1;i++)
{
mn_index = i;
for(int j=i+1;j<n;j++) //pętla wyszukuje najmniejszy element w podzbiorze nieposortowanym
if(tab[j]<tab[mn_index])
mn_index = j;
//zamiana elementu najmniejszego w podzbiorze z pierwszą pozycją nieposortowaną
swap(tab[i], tab[mn_index]);
}
}
int main()
{
int *tab, n;
cout<<"Ile liczb chcesz posortować? ";
cin>>n;
tab = new int [n];
for(int i=0;i<n;i++)
cin>>tab[i]; //wczytanie liczb do posortowania
selection_sort(tab,n); //sortowanie przez selekcję
for(int i=0;i<n;i++)
cout<<tab[i]<<" "; //wypisanie posortowanych elementów
cout<<endl;
system("pause");
return 0;
}