Programowanie i algorytmy

KONKURS FRAKTAL

fraktal

VI edycja konkursu programistycznego

FRAKTAL

19-20 listopad 2016

czytaj więcej

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ść {tex}O(n){/tex}

  • sortowanie przez zliczanie
  • sortowanie pozycyjne
  • sortowanie kubełkowe

Złożoność {tex}O(n log n){/tex}

Złożoność {tex}O(n^2){/tex}

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)