Zaczynam od lewej strony. Porównuję po dwie sąsiednie liczby.
1
2
3
4
5
6
7
for(leti=0;i<n-1;i++){
for(letj=0;j<n-1-i;j++){
if(t[j]>t[j+1]){
[t[j],t[j+1]]=[t[j+1],t[j]];
}
}
}
Sortowanie i wyszukiwanie krok po kroku: bąbelkowe, przez wybór, binarne
Algorytmy sortowania proste różnią się tym, co robią w jednym przebiegu. Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je miejscami, przez co największa wartość w każdym przebiegu wędruje na koniec. Sortowanie przez wybór szuka w pozostałej części najmniejszego elementu i wstawia go na właściwe miejsce. Sortowanie przez wstawianie bierze kolejny element i przesuwa go w lewo, aż trafi między mniejszy a większy.
Liczba operacji zależy nie tylko od algorytmu, ale i od ułożenia danych na wejściu. Zbiór już posortowany, zbiór losowy i zbiór ułożony odwrotnie dają zupełnie inne liczby porównań i zamian, dlatego opisując złożoność, mówi się osobno o przypadku optymistycznym i pesymistycznym. Liczniki pod animacją pokazują te wartości wprost, więc porównanie algorytmów nie sprowadza się do zapamiętania jednej liczby.
Wyszukiwanie liniowe sprawdza element po elemencie i działa na dowolnym zbiorze. Wyszukiwanie binarne wymaga zbioru uporządkowanego, za to w każdym kroku odrzuca połowę pozostałego zakresu, przez co w tysiącu elementów odnajduje wartość po około dziesięciu porównaniach. Ten warunek uporządkowania jest najczęstszą pułapką w pytaniach: bez niego algorytm binarny po prostu nie ma prawa działać.
Przykład: jeden przebieg sortowania bąbelkowego
1
Weź zbiór 5, 3, 8, 1 i porównaj pierwszą parę. Pięć jest większe od trzech, więc następuje zamiana: 3, 5, 8, 1.
2
Kolejna para to 5 i 8. Są w dobrej kolejności, więc zamiany nie ma.
3
Ostatnia para to 8 i 1. Po zamianie zbiór wygląda tak: 3, 5, 1, 8.
4
Po jednym przebiegu największa wartość stoi na końcu i w kolejnym przebiegu nie bierze już udziału w porównaniach.
Najczęstsze pytania
Tylko wtedy, gdy zbiór jest uporządkowany. Algorytm porównuje szukaną wartość ze środkiem zakresu i odrzuca tę połowę, w której szukanej wartości być nie może. Na zbiorze nieuporządkowanym taka decyzja nie miałaby podstaw.
Bąbelkowe porównuje i zamienia sąsiednie elementy, więc zamian bywa bardzo dużo. Przez wybór najpierw znajduje najmniejszy element w pozostałej części, a zamianę wykonuje raz na przebieg.
Około dziesięciu, bo każdy krok zmniejsza zakres o połowę, a dwa do potęgi dziesiątej to 1024. Wyszukiwanie liniowe w najgorszym przypadku wykona ich tysiąc.
Wśród algorytmów prostych żaden nie jest bezwzględnie najlepszy: sortowanie przez wstawianie wygrywa na danych prawie uporządkowanych, a bąbelkowe wypada najsłabiej na danych ułożonych odwrotnie. Do dużych zbiorów stosuje się algorytmy szybsze, jak sortowanie szybkie czy przez scalanie.
To opis tego, jak szybko rośnie liczba operacji, gdy przybywa danych. Przy O(n) dwa razy więcej elementów oznacza około dwa razy więcej pracy, tak działa wyszukiwanie liniowe. Przy O(n^2) dwa razy więcej elementów to około cztery razy więcej pracy, tak zachowują się proste sortowania z dwiema zagnieżdżonymi pętlami.