Sortowanie bąbelkowe
Stronę tą wyświetlono już: 5740 razy
Najprostsza wersja tego algorytmu umożliwia sortowanie danych w n2 krokach, gdzie n oznacza liczbę elementów sortowanych. Można zredukować liczbę niezbędnych kroków wiedząc, że po każdym przejściu na pozycji i ≥ n - k znajdują się maksymalne wartości już posortowane. Przy czym k określa numer kolejnego przejścia przez tablicę sortowanych wartości. Zasada działania algorytmu jest następująca:
- zaczynając od elementu 0 a kończąc na elemencie n - k sprawdzam czy ai > ai + 1, jeżeli tak to zamieniam je miejscami;
- dopóki n - k > 1 lub w danym przejściu nie wykonano żadnej zamiany wartości wykonuj kolejne przejście z punktu 1
Zasadę działania tego algorytmu można zobaczyć na poniższej animacji wykonanej z wykorzystaniem dynamicznie tworzonego wykresu słupkowego z strony Programowanie → Projekty JavaScript → Skrypt JavaScript tworzący wykres słupkowy w formacie SVG.
- czerwony - elementy tablicy, których wartości są zamieniane miejscami;
- niebieski - elementy tablicy, których wartości zostały porównane i nie są zamieniane miejscami;
- zielony - pozostałe elementy tablicy;
W najgorszym przypadku liczba kroków niezbędnych do wykonania w implementacji z powyższej animacji wynosi:
Tytuł:
Algorytmy. Ilustrowany przewodnik
Autor:
Aditya Bhargava
Tytuł:
Algorytmy. Struktury danych i złożoność obliczeniowa
Autor:
Feliks Kurp
Tytuł:
Algorytmy w Pythonie. Techniki programowania dla praktyków
Autor:
Piotr Wróblewski
Tytuł:
Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie
Autor:
Ryan T. White, Archana Tikayat Ray
Tytuł:
Algorytmy kryptograficzne w Pythonie. Wprowadzenie
Autor:
Shannon W. Bray
Tytuł:
Algorytmy sztucznej inteligencji. Ilustrowany przewodnik
Autor:
Rishal Hurbans
Tytuł:
Algorytmy bez tajemnic
Autor:
Thomas H. Cormen
Tytuł:
Algorytmy dla bystrzaków
Autor:
John Paul Mueller, Luca Massaron
Tytuł:
Algorytmy Data Science. Siedmiodniowy przewodnik. Wydanie II
Autor:
David Natingga
Tytuł:
Algorytmy uczenia maszynowego. Zaawansowane techniki implementacji
Autor:
Giuseppe Bonaccorso