PROGRAMOWANIE I ALGORYTMY

szkoła fraktal
Zapraszamy na zajęcia przygotowujące do matury z informatyki

Serwis algorytm.edu.pl zaprasza na kompleksowe zajęcia przygotowujące do matury z informatyki (nowa podstawa programowa)

październik — kwiecień, rok szkolny 2022/2023

więcej informacji pod adresem szkola-fraktal.pl

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

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

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)