Menu Zamknij

Algorytmy służące do porządkowania ciągu elementów

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 nk 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. 1.wyszukaj minimalną wartość z tablicy spośród elementów od i do końca tablicy
  2. 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
(powtórzenia)
[i]

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