ALGORYTMY SORTOWANIA
Sortowanie przez wstawianie
Sortowanie przez wstawianie należy do prostych algorytmów
sortowania o złożoności O(n2).
Polega ono na tym, że bierzemy kolejne elementy do posortowania i
wstawiamy je pomiędzy posortowane już elementy na odpowiedniej
pozycji.
Wez
my przykładową tablicę o elementach [3,9,5,2,4].
Zaczynamy od drugiego elementu tablicy i sprawdzamy czy jest on
mniejszy od elemetu po lewej stronie. Jeśli tak to zamieniamy je
miejscami i sprawdzamy następny, aż napotkany element będzie miał
wartość mniejszą od obecnie wstawianego.
Po pierwszym kroku 9-tka pozostanie na swojej pozycji ponieważ nie
jest mniejsza od swojego lewego sąsiada.
Teraz bierzemy 5-tke i sprawdzamy czy jest mniejsza od poprzedniego
elementu. Ponieważ jest to zamieniamy miejscami te elementy.
Następnie sprawdzamy czy znowu 5-tka jest mniejsza od poprzednika -
nie jest a więc zostaje na tej pozycji (tablica wygląda tak [3,5,9,2,4]).
Następnie bierzemy kolejny element (2-ke) i dopóki poprzednie
elementy są większe od 2-ki to zamieniamy je miejscami. Tablica zmieni
się następująco:
[3,5,9,2,4] -> [3,5,2,9,4] -> [3,2,5,9,4] -> [2,3,5,9,4]
Ostatni element podobnie zamieniamy miejscami z poprzednikami, aż
ich wartość będzie niewiększa od wstawianego elementu.
[2,3,5,9,4] -> [2,3,5,4,9] -> [2,3,4,5,9]
Sortowanie przez wybieranie
Jednym z najprostszych algorytmów sortowania jest sortowanie przez
wybieranie (selekcję).
Polega ono na wyszukaniu najmniejszego elementu spośród
nieposortowanych elementów i ustawieniu go na pierwszej pozycji.
Następnie znowu wyszukujemy najmniejszy element i ustawiamy go na
drugiej pozycji, itd...
Złożoność obliczniowa O(n2).
Sortowanie bąbelkowe
Sortowanie bąbelkowe to prosty algorytm sortowania o złożoności O(n2).
Niestety jest to algorytm mało wydajny i nie stosuje się go do dużych tablic (np.
powyżej 1000 elementów).
Sortowanie bąbelkowe polega na porównywaniu dwóch sąsiednich elementów. Jeśli
ich kolejność jest niepoprawna to są zamieniane miejscami.
Przykładowa tablica o elementach [3, 9, 5, 2, 4].
Zaczynamy od ostatniego elementu i sprawdzamy czy jest on mniejszy od
poprzedniego. W tym przypadku 4>2 więc porównujemy następną parę. 2<5 a więc
zamieniamy je miejscami ([3, 9, 2, 5, 4]). Sprawdzamy kolejną parę - 9 i 2. Ich kolejność
jest "zła" więc zamieniamy ([3, 2, 9, 5, 4]). Ostatnia para także jest w złej kolejności.
Tablica w tym momencie wygląda następująco [2, 3, 9, 5, 4].
Zaczynamy sprawdzanie od początku (tym razem już jednak nie sprawdzamy ostatniej
pary). Tablica będzie kolejno zmieniać się:
[2, 3, 9, 4, 5] -> [2, 3, 4, 9, 5] -> [2, 3, 4, 9, 5]
[2, 3, 4, 5, 9] -> [2, 3, 4, 5, 9]
[2, 3, 4, 5, 9]