Porządkowanie zbiorów

powrót

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

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 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)