Następny algorytm sortujący, który omówimy, ma złożoność rzędu
O(n2)
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ę:
int t[]={2,3,1,4,5,4,3,1}
#include<iostream>
#include<cstdlib>
using namespace std;
void sort_wybor(int tab[],int n)
{int mn_index;
for(int i=0;i<n-1;i++)
{ mn_index = i; for(int j=i+1;j<n;j++)
if(tab[j]<tab[mn_index]) mn_index = j;
swap(tab[i], tab[mn_index]);
}
}
int main()
{
int n;
int *tablica;
cout << ” Ilość elementów tablicy: „;
cin >> n;
srand(time(NULL));
tablica = new int [n];
for (int i=0; i<n; i++)
{
tablica [i] = rand()%50;
cout << ” Tabblica ” << i+1 << „: ” << tablica [i] << endl;
}
sort_wybor(tablica,n);
cout << ” \n Liczby posortowane: „;
for (int i=0; i<n; i++)
cout << tablica [i] << ” „;
cout << '\n’;
delete [] tablica;
}