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++

//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

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

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 ;)