Porządkowanie zbiorów
Porządkowanie zbiorów polega na układaniu ich rosnąco lub malejąco w zależności od potrzeb programu. Układać możemy liczby, znaki oraz ciągi znaków. Te ostatnie nazywamy sortowaniem leksykograficznym. Sortować możemy także obiekty i struktury według ściśle ustalonych zasad.
Algorytmy sortujące możemy podzielić ze względu na złożoność czasową:
Złożoność O(n)
- sortowanie przez zliczanie
- sortowanie pozycyjne
- sortowanie kubełkowe
Złożoność O(nlogn)
Złożoność O(n^2)
Dzielimy także ze względu na stabilność (sortowanie stabilne to takie, w którym elementy o takich samych wartościach nie będą ze sobą zamieniane):
Algorytmy stabilne
Algorytmy sortujące, które dla elementów o tej samej wartości zachowują w tablicy końcowej kolejność tablicy wejściowej, nazywamy algorytmami stabilnymi
- sortowanie bąbelkowe
- sortowanie przez wstawianie
- sortowanie przez scalanie
- sortowanie przez zliczanie
- sortowanie kubełkowe
Algorytmy niestabilne
Algorytmy, do działania których nie jest potrzebna większa niż stała pamięć dodatkowa (elementy sortowane przechowywane są przez cały czas w tablicy wejściowej), nazywane są algorytmami działającymi w miejscu
Podczas sortowania dobrze jest przyjrzeć się zachowaniu algorytmów dla różnego rodzaju zbiorów, czyli jak szybko posortowany zostanie jeden z trzech zbiorów:
- zbiór częściowo posortowany lub posortowany
- zbiór posortowany pesymistycznie (na przykład posortowany malejąco a musimy posortować rosnąco)
- zbiór losowy (pseudolosowy)