Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór

Aktualna kategoria: Nauka » Informatyka » Liceum - lekcje

...

Lekcja: "Algorytmy sortujące - sortowanie przez wstawianie, sortowanie przez wybór"

Sortowanie przez wybór - Selection Sort

Jest to jedna z prostszych metod sortowania posiadająca klasę czasowej złożoności obliczeniowej równą 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:

wyszukaj minimalną wartość z tablicy spośród elementów od i+1 do końca tablicy

zamień wartość minimalną, z elementem na pierwszej pozycji (i)

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

Algorytm jest niestabilny. Sortowanie odbywa się w miejscu.

Pobierz lekcję

Udostępnij link do tej lekcji innym uczniom: