Algorytm na sortowanie bąbelkowe w C++, Java i Python
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++
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>
usingnamespacestd;
voidsortuj(int*tab,intn)
{
for(inti=0,zamiany=1;i<n-1&&zamiany!=0;i++)
{
zamiany=0;
for(intj=0;j<n-1;j++)
if(tab[j]>tab[j+1])
{
swap(tab[j],tab[j+1]);
zamiany++;
}
}
}
intmain()
{
intx;
cout<<"Podaj ile elementow chcesz posortowac: ";
cin>>x;
int*elementy=newint[x];//program wykorzystuje tablice dynamiczne
cout<<"Podaj elementy:"<<endl;
for(inti=0;i<x;i++)
cin>>elementy[i];
cout<<"Oto te elementy: "<<endl;
for(inti=0;i<x;i++)
cout<<elementy[i]<<" ";
sortuj(elementy,x);
cout<<"\nOto elementy po sortowaniu: "<<endl;
for(inti=0;i<x;i++)
cout<<elementy[i]<<" ";
delete[]elementy;
system("pause");
return0;
}
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
publicclassBabelkowe{
publicstaticvoidmain(String[]args){
Scanner scanner=newScanner(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: ");
intl=scanner.nextInt();
int[]tab=newint[l];
for(inti=0;i<l;i++){
System.out.print("Podaj element o indexie "+i+" : ");
def wypiszTablice(t):#pomocnicza funkcja do szybkiego wypisania zawartosci tablicy
forel int:
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
foriinrange(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
foriinrange(n-1):#iterujemy przez tablice
ifzmian==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
forjinrange(n-1):# iterujemy poprzez pozostale elementy tablicy
iftab[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
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?
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?