Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n²). Polega na wyszukaniu elementu mającego się znaleźć na zadanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.

Algorytm przedstawia się następująco:

1. wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy
2. zamień wartość minimalną, z elementem na pozycji i

Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.

Algorytm jest niestabilny . Przykładowa lista to: [2a,2b,1] → [1,2b,2a] (gdzie 2b=2a)

Przykład

Posortowana zostanie tablica 8-elementowa [9,1,6,8,4,3,2,0]. W tablicy pogrubione zostaną te elementy wśród których wyszukuje sie wartość minimalną.

Algorytm można nieco przyspieszyć, gdy tablica jest wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.

Implementacja

Sortowanie przez wybieranie w C++:

• przez wyszukiwanie największego składnika:

 int Max_element_indeks(int n)   {     int max = 0;     for (int i = 1; i < n; i++)       if (t[i] > t[max])         max = i;     return max;   }   void Selection_sort(int n)  {    for (int i = n; i >= 2; i--)    {      int max = Max_element_indeks(i);      if (max != i - 1)        swap(t[i - 1], t[max]);    }  }

template<typename It>void selection_sort(It begin, It end){  for (; begin != end; ++begin)    std::iter_swap(begin, std::min_element(begin, end));}

• przez wyszukiwanie najmniejszego składnika:

#include <cstdlib>#include <iostream> using namespace std; void selection_sort(int n, int t[]); int main(void){   int tab[20];   srand(time(NULL));   for(int i=0; i<20; i++) {      tab[i] = rand()%100;      cout << tab[i] << " ";   }   cout << endl;   selection_sort(20, tab);   for(int i=0; i<20; i++) cout << tab[i] << " ";   cout << endl;   return 0;} void selection_sort(int n, int t[]){   int i, j, k;   for(i=0; i<n; i++) {      k=i;      for(j=i+1; j<n; j++) if(t[j]<t[k]) k=j;      swap(t[k], t[i]);   }}

Sortowanie przez wybieranie w ruby

#!/usr/bin/ruby # sortowanie przez wybor  def wsort(list)for i in 0...(list.size - 1)min = ifor j in (i+1)...(list.size)if list[j] <= list[min]min = jendlist[i], list[min] = list[min], list[i]endendreturn listend list = []puts "podaj dane do posortowania CTRL-D - koniec"while line = $stdin.gets  list << line.to_iendputs "Dane posortowane"puts wsort(list)