Sposób sortowania elementów

Wyrazy sortowanego zbioru mogą być sortowane rosnąco, niemalejąco, malejąco lub nierosnąco. Domyślnym przypadkiem jest sortowanie niemalejące lub rosnące.

Chociaż terminy kolejność niemalejąca i rosnąca oraz nierosnąca i malejąca bywają używane zamiennie, ich znaczenia nie są tożsame.

O sortowaniu rosnącym mówimy wtedy, gdy każdy kolejny posortowany element jest większy od poprzedniego – nie ma równych elementów.

0 2 5 7 13 16 34 37 51 61

O sortowaniu niemalejącym mówimy wtedy, gdy każdy kolejny posortowany element jest większy lub równy poprzedniemu (w zbiorze są równe sobie elementy).

0 2 5 7 7 16 34 51 51 61

O sortowaniu malejącym mówimy wtedy, gdy każdy kolejny posortowany element jest mniejszy od poprzedniego – nie ma równych elementów.

61 51 37 34 16 13 7 5 2 0

O sortowaniu nierosnącym mówimy wtedy, gdy każdy kolejny posortowany element jest mniejszy lub równy poprzedniemu (w zbiorze są równe sobie elementy).

61 51 51 34 16 7 7 5 2 0

Algorytmy sortowania – właściwości

Mówiąc o algorytmach sortowania, powinniśmy pamiętać o tym, jak można je scharakteryzować oraz ze względu na co podzielić.

Możemy wyróżnić działania, na których bazuje większość algorytmów sortowania, które poznamy – są to np.: wstawianie, zamiana, wybór oraz łączenie. Algorytmy najczęściej wykorzystują kilka z nich.

Sortowanie w miejscu

Algorytmy sortowania, które sortują w miejscu (in situ) to takie algorytmy, które niezależnie od tego, jaki jest rozmiar danych wejściowych, do wykonania sortowania potrzebują stałej ilości pamięci komputera.

Stabilność

Algorytmy sortowania stabilnego to takie algorytmy, w których elementy o takiej samej wartości podczas sortowania nie zmieniają kolejności względem siebie.

Złożoność obliczeniowa i pamięciowa

Informacje na temat złożoności obliczeniowej oraz pamięciowej znajdziesz w e‑podręczniku na poziomie rozszerzonym w modułach: „Jak wybrać odpowiedni algorytm sortowania” oraz „Porównanie algorytmów sortowania”.

Słownik