Sortowanie bąbelkowe
Sortowanie bąbelkowe (algorytm bąbelkowy, ang. bubble sort) – polega na porównywaniu dwóch kolejnych elementów i zamianie ich kolejności, jeżeli zaburza ona porządek, w jakim się sortuje tablicę.
Sortowanie kończy się, gdy podczas kolejnego przejścia nie dokonano żadnej zmiany.
Algorytm wykonuje n-1 przejść, a w każdym przejściu wykonuje n–k porównań (gdzie k = 1, 2 … n-1 to numer przejścia), przez co jego teoretyczna złożoność czasowa wynosi O(n2).
W podstawowej wersji algorytmu nie można tego czasu skrócić, a każda permutacja powoduje, że algorytm jest wykonywany w czasie pesymistycznym.
Ciąg wejściowy [4, 2, 5, 1, 7] . Każdy wiersz symbolizuje wypchnięcie kolejnego największego elementu na koniec („wypłynięcie największego bąbelka”). Niebieskim kolorem oznaczono końcówkę ciągu już posortowanego.
Implementacja w języku Python tego algorytmu wygląda następująco:
Więcej informacji o sortowaniu bąbelkowym znajdziesz na:
www.swistak.codes
Kanał o Wszystkim
Sortowanie przez wybieranie
Sortowanie przez wybieranie jedna z prostszych metod sortowania o złożoności O(n2). Polega na wyszukaniu elementu mającego się znaleźć na żądanej pozycji i zamianie miejscami z tym, który jest tam obecnie. Operacja jest wykonywana dla wszystkich indeksów sortowanej tablicy.
Algorytm ten jest niestabilny. Przykładowa tej niestabilności przedstawia ta oto lista: [2a,2b,1] → [1,2b,2a] (gdzie 2b=2a)
Sortowanie przez wybieranie jest już bardziej wydajnym algorytmem sortowania, A niżeli sortowanie bąbelkowe. Idea jego działania polega na wybieraniu z podzbioru danych zbioru elementu najmniejszego (znajdowania minimum) i zamianie jego położenia z początkowym elementem podzbioru. Następnie zakres poszukiwania zostaje zawężony do podzbioru danych znajdujących się po posortowanych już elementach (co krok zbiór będzie mniejszy o 1).
Algorytm przedstawia się następująco:
- 1.wyszukaj minimalną wartość z tablicy spośród elementów od i do końca tablicy
- 2.zamień wartość minimalną, z elementem na pozycji i
Gdy zamiast wartości minimalnej wybierana będzie maksymalna, wówczas tablica będzie posortowana od największego do najmniejszego elementu.
|
numer iteracji |
lista | minimalny element |
|---|---|---|
| 0 | [7, 4, 8, 2, 6, 1] | 1 |
| 1 | [1, 4, 8, 2, 6, 7] | 2 |
| 2 | [1, 2, 8, 4, 6, 7] | 4 |
| 3 | [1, 2, 4, 8, 6, 7] | 6 |
| 4 | [1, 2, 4, 6, 8, 7] | 7 |
| 5 | [1, 2, 4, 6, 7, 8] | 8 |
Algorytm można znacznie przyspieszyć, gdy tablica będzie wypełniana z obu końców, tj. wyszukiwane jest równocześnie minimum i maksimum.
W języku Python ten algorytm może wyglądać w następujący sposób:
Więcej informacji o sortowaniu przez wybieranie znajdziesz na:
www.swistak.codes
Kanał o Wszystkim
Inne algorytmy służące do sortowania
- sortowanie przez wstawianie
- sortowanie przez scalanie
- sortowanie przez zliczanie