Wcześniej, czy później każdy natknie się na problem nieuporządkowanego zbioru elementów. Ułożenie danych w określonym porządku (np. od najmniejszej do największej liczby) brzmi banalnie prosto, ale jak to zrobić mając do posortowania w C++ tablice o naprawdę wielu elementach? Z pomocą przychodzi algorytm na sortowanie bąbelkowe.
Fakt faktem, algorytm sortowania bąbelkowego nie należy do najbardziej wydajnych algorytmów sortowania, ponieważ przy większych zbiorach danych zaczyna się, że tak to nazwę, „krztusić”. Jest po prostu mało efektywny. W każdym razie lepiej znać jeden słaby algorytm, aniżeli nie znać żadnego, a jeszcze lepiej jest umieć napisać algorytm wykonujący sortowanie bąbelkowe w C++, Java, Python 🙂
Działanie algorytmu
Sortowanie bąbelkowe polega na porównaniu dwóch elementów znajdujących się obok siebie i ewentualnej zamianie ich miejscami w przypadku, gdy liczby nie spełniają założenia kolejności jaką obraliśmy.
Na przykład, gdy chcemy uporządkować rosnąco liczby: 5, 4 i 2 to w pierwszej kolejności dokonamy porównania pary 5 i 4. Piątka jest większa od czwórki, a my przecież chcemy, by liczby ułożone były rosnąco, czyli zaczynając od liczby najmniejszej, kończąc na największej. Zatem zamieniamy miejscami piątkę i czwórkę. W rezultacie otrzymujemy: 4, 5 i 2. Teraz para 4 i 5 jest w porządku. Przechodzimy do kolejnej pary, którą będą liczby 5 i 2. Podobnie jak wcześniej piątka jest większa od dwójki, więc zamieniamy je ze sobą. Teraz nasze liczby uporządkowane są następująco: 4,2,5. Największa liczba ze zbioru, czyli 5 jest ostatnia tak jak sobie tego życzyliśmy, ale za to 4 i 2 są uporządkowane niewłaściwie. Bierzemy więc tą parę, porównujemy i zamieniamy je ze sobą miejscami. Teraz nasz zbiór jest już uporządkowany. 2,4,5 to porządek w jakim chcieliśmy zobaczyć te liczby.
Algorytm sortowania bąbelkowego
i ←0
j ← 1
dopóki i<liczba_elementów oraz zamiany!=0 wykonuj
zamiany ←0
j ←0
dopóki j<liczba_elementów-1 wykonuj
jeśli tab[j]>tab[j+1]
zamień(tab[j],tab[j+1])
zamiany←zamiany+1
j ← j+1
i ← i+1
Zmienna zamiany wskazuje na ilość zamian elementów w każdej iteracji (powtórzeniu) pętli. Jeśli w czasie jednej iteracji pętli nie dojdzie do żadnej zamiany elementów to oznacza, że tablica została już posortowana.
Sortowanie bąbelkowe – implementacje
Tak prezentują się programy z funkcją sortującą tablicę liczb całkowitych, wykorzystującą właśnie algorytm na sortowanie bąbelkowe.
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 |
//program do sortowania n-elementowej tablicy //przy pomocy algorytmu sortowania bąbelkowego //Kosiński Łukasz #include <iostream> #include <algorithm> using namespace std; void sortuj(int *tab, int n) { for(int i=0, zamiany=1; i<n-1 && zamiany!=0; i++) { zamiany=0; for(int j=0; j<n-1; j++) if(tab[j]>tab[j+1]) { swap(tab[j], tab[j+1]); zamiany++; } } } int main() { int x; cout << "Podaj ile elementow chcesz posortowac: "; cin >> x; int *elementy=new int[x];//program wykorzystuje tablice dynamiczne cout << "Podaj elementy:" << endl; for(int i=0; i<x; i++) cin >> elementy[i]; cout << "Oto te elementy: " << endl; for(int i=0; i<x; i++) cout << elementy[i] << " "; sortuj(elementy, x); cout << "\nOto elementy po sortowaniu: " << endl; for(int i=0; i<x; i++) cout << elementy[i] << " "; delete [] elementy; system("pause"); return 0; } |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
public class Babelkowe { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); // inicjalizujemy Scanner - obiekt, który będzie zczytywał dane od użytkownika System.out.println("Program sortujący tabelę metodą bąbelkową."); System.out.println("Podaj ilość elementów tablicy: "); int l = scanner.nextInt(); int[] tab = new int[l]; for(int i = 0; i < l; i++) { System.out.print("Podaj element o indexie " + i + " : "); tab[i] = scanner.nextInt(); } System.out.println(); System.out.print("Wprowadzona tablica: |"); for(int i=0; i<tab.length;i++){ System.out.print(tab[i]+ " | "); //wypisujemy tablicę } int zmiany= 1; int próba; int pomoc; while(zmiany!=0){ //Póki ani razu nie przestawimy liczb będzie działać próba=0; zmiany=0; while(próba!=tab.length-1){ //Próba przestawienia dla każdego indexu if(tab[próba]<tab[próba+1]){ zmiany++; pomoc = tab[próba]; tab[próba] = tab[próba+1]; //Jeśli index n jest mniejszy od n+1 to zamień n i n+1 tab[próba+1]= pomoc; } próba++; } } scanner.close(); // zwalniamy zasoby System.out.println(); System.out.print("Posortowana tablica: |"); for(int i=0; i<tab.length;i++){ System.out.print(tab[i]+ " | "); //wypisujemy tablicę } } } |
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def wypiszTablice(t): #pomocnicza funkcja do szybkiego wypisania zawartosci tablicy for el in t: print(el, end=" | ") print("Program sortujacy tablice metoda babelkowa") print("Podaj ilosc elementow tablicy: ") n = int(input()) #pobieramy ilosc elementow od uzytkownika tab = [] #tworzymy pusta tablice, do ktorej bedziemy dodawac kolejne elementy for i in range(n): print("Podaj element nr. " + str(i)) #pobieramy kolejne elementy od uzytkownika tab.append(float(input())) #zwroc uwage, ze pobieramy elementy typu rzeczywistego print("Wprowadzona tablica:") wypiszTablice(tab) zmian = 1 #zmienna pomocnicza for i in range(n-1): #iterujemy przez tablice if zmian == 0: #jezeli w poprzednim kroku nie dokonano zadnych zmian w tablicy(co oznacza ze jest juz posortowana) break # przerywamy jej dzialanie zmian=0 # w przeciwnym razie resetujemy licznik zmian for j in range(n-1): # iterujemy poprzez pozostale elementy tablicy if tab[j] > tab[j+1]: #jezeli element jest j jest wiekszy od elementu j+1 tab[j], tab[j+1] = tab[j+1], tab[j] #zamieniamy je miejscami zmian += 1 # i zwiekszamy ilosc zmian o 1 print("Posortowana tablica:") wypiszTablice(tab) |
Podsumowanie
Algorytm sortowania bąbelkowego warto znać przygotowując się do matury z informatyki. W podlinkowanym artykule znajdziesz również spis rzeczy, które moim zdaniem warto powtórzyć przed maturą. Jeżeli zaś chcesz poszerzyć swoją wiedzę na temat algorytmów i programowania, to zachęcam Cię do zapoznania się z poniższym tytułem. Znajdziesz w nim również inne metody sortowania i wyszukiwania 😉
msy
says:Zmienna zamiany mogłaby „pamiętać” miejsce ostatniej zamiany, a wtedy w następnym kroku algorytm mógłby nie iść dalej, bo wszystko jest tam uporządkowane.
Napisałem komentarz przy sortowaniu przez wybór, ale go tam nie widzę, nie ukazał się na stronie – czy jest zatwierdzany przez Pana?