algorytmy sortujące

Do czego służą?

Algorytmy sortujące służą do posortowania (ustawienia w kolejności od najmniejszej do największej lub od największej do najmniejszej) danego ciągu liczb. Poniżej przedstawię kilka z nich.

Sortowanie przez wybieranie

Dla sortowania od najmniejszej do największej (w odwrotnej kolejności zamiast najmniejszej bierze się największą itd.): W danym ciągu najpierw znajdujemy najmniejszą liczbę (przechodząc po całym ciągu) i ustawiamy ją na początek. Następnie w tym ciągu znowu szukamy najmniejszej, ale wykluczając pierwszy element(nie psujmy już tego co jest posortowane) i ustawiamy go za poprzednim. Czyli przykładowo dla ciągu 7 2 6 4 1 będzie to wyglądać tak (posortowany fragment ciągu jest zaznaczony na zielono):
7 2 6 4 1
1 7 2 6 4
1 2 7 6 5
1 2 5 7 6
1 2 5 6 7
tutaj zauważamy, że ciąg jest już posortowany, więc kończymy nasz algorytm.

złożoność:

Sortowanie przez zliczanie

Na początku zliczamy wystąpienia każdego elementu, gdzie otrzymujemy tablicę z informacją ile jest liczb o danej wartości, a następnie przeglądamy tę tablicę. Jeśli sortujemy niemalejąco to zaczynamy od początku tablicy, a w przeciwnym wypadku od końca. Do posortowanego ciągu dodajemy tyle liczb o danej wartości, ile wstazuje tablica. Czyli przykładowo dla ciągu 3 3 7 5 2 6 4 1 będzie to wyglądać tak:
tablica:
1 2 3 4 5 6 7 (indeksy)
1 1 2 1 1 1 1
tworzenie posortowanego ciągu:
1
1 2
1 2 3 3
1 2 3 3 4
1 2 3 3 4 5
1 2 3 3 4 5 6
1 2 3 3 4 5 6 7
Przy tym sposobie sortowania trzeba zwracać uwagę na zakres liczb. Bo jeżeli liczby są z zakresu 0 - k, to ka musi być wystarczająco małe, żeby dało się stworzyć tablicę o rozmiarze k.

złożoność:

Quick sort

Sortowanie szybkie oparte jest na technice zwanej "dziel i zwyciężaj". Dany ciąg dzielony jest (po przestawieniu pewnych jej elementów) na dwa mniejsze ciągi. Dowolny element pierwszego ciągu nie może być większy od dowolnego elementu drugiego ciągu. Liczbą, w oparciu, o którą dokonuje się podziału stanowi najczęściej pierwszy element ciągu. W następnym kroku dla dwóch utworzonych podciągów wykonywany jest w rekurencyjny sposób ten sam algorytm. Wywołania te kończą się w momencie, gdy któryś z podciągów będzie jednoelementowy.

złożoność:

Sortowanie w praktyce

Zarówno w python jak i w c++ są wbudowane specjalne funkcje sortujące (najczęściej quick sort). Są one szybkie i zdecydowanie lepiej ich używać niż męczyć się z pisaniem własnego sorta - jak się pomylimy, to nie będziemy wiedzieli czy mamy złego sorta czy może mamy zły pomysł? Jeśli chcemy posortować niestandardowo, to wbudowane funkcje mają możliwości zmienienia dla danego przypadku 😉.