Sortowanie przez wybieranie

Sortowanie przez wybieranie
Ilustracja
Przykład działania sortowania przez wybieranie
Rodzaj Sortowanie
Struktura danych Tablica, lista
Złożoność
Czasowa O ( n 2 ) {\displaystyle O(n^{2})}

Sortowanie przez wybieranie - jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na żądanej 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 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)

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 się 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.

Sortowanie przez wybieranie w C++:

  • przez wyszukiwanie największego składnika:
  • przez wyszukiwanie najmniejszego składnika:

Sortowanie przez wybieranie w ruby

Sortowanie przez wybieranie w PHP

Sortowanie przez wybieranie w Javascript

Copyright