Sortowanie przez selekcję (przez wybór)

powrót

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++:

#include<iostream>
#include<cstdlib>
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;
}