Sortowanie przez wybieranie

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ą.

nr iteracji (wartość i)	tablica	minimum
0	[9,1,6,8,4,3,2,0]	0
1	[0,1,6,8,4,3,2,9]	1 (element znajduje się na właściwej pozycji)
2	[0,1,6,8,4,3,2,9]	2
3	[0,1,2,8,4,3,6,9]	3
4	[0,1,2,3,4,8,6,9]	4 (...)
5	[0,1,2,3,4,8,6,9]	6
6	[0,1,2,3,4,6,8,9]	8 (...)

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

 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));
}