Porządkowanie zbiorów

powrót

Przą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(n log n)$$

• sortowanie przez scalanie
• sortowanie szybkie
• sortowanie przez kopcowanie

Złożoność $$O(n^2)$$

• sortowanie bąbelkowe
• sortowanie przez selekcję (przez wybór)
• sortowanie przez wstawianie

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

• sortowanie bąbelkowe
• sortowanie przez wstawianie
• sortowanie przez scalanie
• sortowanie przez zliczanie
• sortowanie kubełkowe

Algorytmy niestabilne

• sortowanie szybkie
• sortowanie przez kopcowanie

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)