Sortowanie bÄ…belkowe
Wykład: bubble sort, implementacja w C++, animacja
pokazująca sortowanie bąbelkowe, złożoność algorytmu
SORTOWANIE B
BELKOWE
ALGORYTM SORTOWANIA
B
BELKOWEGO
Sortowanie to polega na porównywaniu dwóch kolejnych
elementów i zamianie ich kolejności, zgodnie z zasadą:
 lżejszy bąbelek powietrza chce jako pierwszy wypłynąć na
powierzchnię wody (w sortowaniu rosnącym) lub  cięższy
bąbelek powietrza chce jako pierwszy wypłynąć na
powierzchniÄ™ wody (w sortowaniu malejÄ…cym). Za
 powierzchniÄ™ wody przyjmuje siÄ™ zerowy element tablicy.
2
Złożoność czasowa tego algorytmu: O(n )
Złożoność pamięciowa: O(1)
IMPLEMENTACJA W C++
void sortowanie_babelkowe(int *tab, int n)
{
for (int i=1; i {
for (int j=n-1; j>=1; j--)
{
if (tab[j]{
int bufor;
bufor=tab[j-1];
tab[j-1]=tab[j];
tab[j]=bufor;
}
}
}
}
PRZYKA
AD SORTOWANIA
B
BELKOWEO
Dana jest tablica, którą należy posortować rosnąco:
9 2 6 5 1 3
0 1 2 3 4 5
indeks
powierzchnia wody
0
9
1
2
2
6
3
5
4
1
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
2
6
Sortujemy rosnąco, więc
3 za każdym razem lżejszy
5
bąbelek będzie ulatywał
ku powierzchni wody
4
1
Sortowanie rozpoczynamy
od końca tablicy
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
2
6
3
5
4
1
Brak zamiany
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
2
6
3
5
Zamiana, bo 1<5
4
1
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
2
6
3
1
Zamiana, bo 1<5
4
5
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
2
6
Zamiana, bo 1<6
3
1
4
5
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
2
1
Zamiana, bo 1<6
3
6
4
5
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
2
Zamiana, bo 1<2
2
1
3
6
4
5
5
3
Indeks w tablicy
powierzchnia wody
0
9
1
1
Zamiana, bo 1<2
2
2
3
6
4
5
5
3
Indeks w tablicy
powierzchnia wody
0
9
Zamiana, bo 1<9
1
1
2
2
3
6
4
5
5
3
Indeks w tablicy
powierzchnia wody
0
1
Zamiana, bo 1<9
1
9
2
2
3
6
4
5
5
3
Indeks w tablicy
...POWTARZAĆ DO MOMENTU
POSORTOWANIA CAA
EJ TABLICY Jð
Etapy sortowania
0 1 2 3 4 5
0
9 1 1 1 1
1
1
1
2 9 2 2 2
9
2
2
6 2 9 3 3
2
3
3
5 6 3 9 5
6
5
4
1 5 6 5 9
5
6
5
3 3 5 6 6
3
9
Indeks w tablicy