Algorytmy
Sortowania
Spis treści:
Ø Sortowanie bąbelkowe
Ø Sortowanie przez kopcowanie
Ø Sortowanie przez scalanie
Ø Sortowanie szybkie
Sortowanie bąbelkowe to jeden z najprostszych algorytmów sortowania. Jego złożoność to O(n2) czyli jeżeli dostanie 20 liczb do posortowania, to w najgorszym przypadku będzie musiał wykonać 400 operacji. Nie jest to algorytm zbyt szybki.
No a teraz najważniejsze - jak to działa. Otóż bardzo prosto:
· Porównujemy po kolei elementy ze sobą sąsiadujące, czyli 1 z 2, 2 z 3, 3 z 4, 4 z 5, 5 z 6 itd.
· Jeżeli element po lewej jest większy od elementu po prawej to zamieniamy je ze sobą (jeżeli nie, to nic nie robimy)
· Całość powtarzamy tyle razy, ile jest elementów, lub jeżeli po porównaniu wszystkich elementów nie zamieniliśmy żadnych miejscami
Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb {5 4 3 2 1}, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.
Obieg
Zbiór
Opis operacji
1
5 4 3 2 1
Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów
4 5 3 2 1
Druga para też wymaga zamiany elementów
4 3 5 2 1
Wymagana wymiana elementów
4 3 2 5 1
Ostatnia para również wymaga wymiany elementów
4 3 2 1 5
Stan po pierwszym obiegu. Zwróć uwagę, iż najstarszy element (5) znalazł się na końcu zbioru, a najmłodszy (1) przesunął się o jedną pozycję w lewo.
2
Para wymaga wymiany
3 4 2 1 5
3 2 4 1 5
3 2 1 4 5
Elementy są w dobrej kolejności, zamiana nie jest konieczna.
Stan po drugim obiegu. Zwróć uwagę, iż najmniejszy element (1) znów przesunął się o jedną pozycję w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wędruje o jedną pozycję ku początkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce końcowe.
3
2 3 1 4 5
2 1 3 4 5
Dobra kolejność
Stan po trzecim obiegu. Wnioski te same.
4
1 2 3 4 5
Zbiór jest posortowany. Koniec
Tak, więc aby posortować nasz zbiór liczb program musiał wykonać 16 porównań
Zapis programu w Visual BASIC Schemat blokowy
Rzulu5