Na początku, czym ono w ogóle jest??
Sortowanie bąbelkowe (ang. bubble sort) to prosta metoda sortowania, o złożoności czasowej O(n2) i pamięciowej O(1). 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.
To definicja według wiki, ale z polskiego na nasze, co to robi i czym to się je??
No więc mamy jakąś tablicę, oczywiście może być nieuszeregowana, no i trzeba posortować w niej liczby. jak to robimy?? Mamy powiedzmy takie liczby:
2, 5, 7, 3, 5, 2, 3, 9
No więc patrzymy na pierwszą liczbę i porównujemy ją z kolejną. Ta druga jest większa, a więc wszystko gra, teraz "przesuwamy" się o jedno pole w prawo i porównujemy kolejne dwie liczby, 5 i 7, no i 5 < 7, więc wszystko OK, znowu się "przesuwamy" i porównujemy 7 i 3, ale 7 > 3, więc nie tak powinno być!! Co my z tym robimy?? zamieniamy je miejscami i otrzymujemy coś takiego:
2, 5, 3, 7, 5, 2, 3, 9
i teraz porównujemy 7 i 5, znowu nie tak powinno być, więc hop, zamieniamy je i tak dalej aż do końca. Co nam z tego wyszło??
2, 5, 3, 5, 2, 3, 7, 9
Wygląda nieco lepiej, ale ciągle nieposortowane do końca. Powtarzamy więc to do znudzenia aż wszystko się ustawi jak ma być ;) Tylko jak to napisać??
void sortuj(int tablica[], int n) // n to długość tablicy { bool a=1; // a odpowiada na pytanie, czy były jakieś zmiany while(a==1) //powtarzaj tak długo, jak są jakieś zmiany { a=0; for (int i=0; i<n-1; i++) if (tablica[i]>tablica[i+1]) {a=1; swap (tablica[i], tablica[i+1]);} //w przypadku, gdy napotka dwie nieposortowane liczby } //zamienia je miejscami i ustawia "a" na 1, czyli prawda } /* uwaga!!!! tu jest i < n-1, dlaczego?? bo gdyby i dojechało do ostatniej liczby w tablicy (tablica[n-1]) to porównując tą liczbę z następną liczbą (tj. tablica[n]) porównywałoby nieistniejące liczby, co mogłoby albo spowodować posypanie się programu, albo dziwne wyniki */
