Sortowanie bąbelkowe - jak działają algorytm i schemat blokowy oraz przykład

Sortowanie bąbelkowe, zwane również bubble sort, to jeden z najprostszych algorytmów sortowania. Choć algorytm nie jest wydajny dla dużych zestawów danych, jego prostota sprawia, że jest popularnym wyborem na początek nauki algorytmów sortowania.

Zasada działania sortowania bąbelkowego

Sortowanie bąbelkowe działa poprzez wielokrotne porównywanie sąsiadujących elementów w liście danych. Pozwala na uporządkowanie wartości rosnąco lub malejąco. 

W każdym cyklu algorytmu każde kolejne dwie liczby są porównywane ze sobą i zamieniane miejscami, jeśli są w niewłaściwej kolejności. Proces powtarza się aż do pełnego posortowania danych. Algorytm, choć prosty, nie jest optymalnym wyborem do sortowania dużych zbiorów danych ze względu na niską efektywność przy większej liczbie elementów. Jednak często wykorzystuje się go w czasie nauki jako wprowadzenie do poznania metod sortowania.

Zalety algorytmu sortowania bąbelkowego

• Prostota - algorytm jest bardzo prosty do zrozumienia i zaimplementowania. Dzięki temu często wykorzystuje się go w celach edukacyjnych do nauki podstaw algorytmów sortujących.
• Stabilność - sortowanie bąbelkowe jest stabilne, co oznacza, że elementy o tej samej wartości pozostają w tej samej kolejności względem siebie po sortowaniu.
• Minimalne wymagania pamięci - sortowanie bąbelkowe działa "na miejscu" (in-place), co oznacza, że nie wymaga dodatkowej pamięci poza tą potrzebną do przechowywania danych.

Wady algorytmu sortowania bąbelkowego

• Wolne działanie - algorytm jest nieefektywny dla dużych zestawów danych. Jego złożoność czasowa wynosi O(n²), co czyni go znacznie wolniejszym w porównaniu do bardziej zaawansowanych algorytmów sortowania.

Przykład użycia sortowania bąbelkowego

Poniżej znajdziesz przykład sortowania listy 4, 2, 1, 7, 5 w formie grafiki GIF oraz zapisu tekstowego. Liczby są sortowane od lewej do prawej w kolejności rosnącej.

Pod spodem umieszczono przykład użycia sortowania bąbelkowego w formie zapisu tekstowego. Zapoznaj się z nim dla lepszego zrozumienia zasady jego działania.

Implementacja algorytmu sortowania bąbelkowego

Schemat blokowy i pseudokod sortowania bąbelkowego

funkcja sortowanie_babelkowe (tab, n)
dla i = 1, 2, …, n wykonuj
    dla j = 1, 2, …, n wykonuj
        jeżeli tab [j] > tab [j+1]
            pom ← tab [j]
            tab [j] ← tab [j+1]
            tab [j+1] ← pom
    zwróć tab

Komentarze do pseudokodu sortowania bąbelkowego

• 1 linia – Deklaracja funkcji oraz parametrów (zmiennych), które są do niej przekazywane.
• 2 linia – Zewnętrzna pętla, iteracja po indeksie i od 1 do n (czyli długości listy).
• 3 linia – Wewnętrzna pętla – iteracja po indeksie j od 1 do n-1 (czyli długości listy-1).
• 4 linia – Sprawdzenie warunku – porównanie bieżącego elementu z następnym (czy jest większy od kolejnego).
• 5 linia – Przechowanie wartości bieżącego elementu.
• 6 linia – Zastąpienie bieżącego elementu tab[j] następnym elementem tab[j+1].
• 7 linia – Przypisanie zapamiętanej wartości do kolejnego elementu.

tab = [5, 3, 8, 2, 1, 7]

# Algorytm sortowania babelkowego
n = len(tab)
for i in range(n):
    for j in range(n - 1):
        if tab[j] > tab[j + 1]:
            pom = tab[j]
            tab[j] = tab[j + 1]
            tab[j + 1] = pom

# Wypisanie posortowanej listy
for element in tab:
    print(element, end=" ")

#include <iostream>
using namespace std;
int main() {
	int tab[] = {5, 3, 8, 2, 1, 7};
	int n = sizeof(tab) / sizeof(tab[0]); // automatyczne wskazanie ilosci elementow danej tablicy

	// Algorytm sortowania babelkowego
	for (int i = 0; i < n - 1; i++) {
    	for (int j = 0; j < n - 1; j++) {
        	if (tab[j] > tab[j+1]) {
            	int pom = tab[j];
            	tab[j] = tab[j+1];
            	tab[j+1] = pom;
        	}
  	}
}

	// Wypisanie posortowanej tablicy
	for (int i = 0; i < n; i++) {
    	cout << tab[i] << " ";
	}
	return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] tab = {5, 3, 8, 2, 1, 7};

        // Algorytm sortowania babelkowego
        for (int i = 0; i < tab.length - 1; i++) {
            for (int j = 0; j < tab.length - 1; j++) {
                if (tab[j] > tab[j+1]) {
                    int pom = tab[j];
                    tab[j] = tab[j+1];
                    tab[j+1] = pom;
                }
            }
        }

        // Wypisanie posortowanej tablicy
        for (int element : tab) {
            System.out.print(element + " ");
            }
        }
}

Schemat blokowy i pseudokod zoptymalizowanego algorytmu sortowania bąbelkowego

funkcja zoptymalizowane_sortowanie_babelkowe (tab, n)
    dla i = 1, 2, … n - 1 wykonuj
        dla j = 1, 2, … n - i - 1 wykonuj
            jeżeli tab [j] > tab [j+1]
                pom ← tab [j]
                tab [j] ← tab [j+1]
                tab [j+1] ← pom
    zwróć tab

Komentarze do pseudokodu zoptymalizowanego sortowania bąbelkowego

Do implementacji zoptymalizowanego algorytmu konieczne jest użycie zagnieżdżonych pętli for. Pętla zewnętrzna powinna wykonywać się n - 1 razy, gdzie n to liczba elementów w sortowanym zbiorze.
Z kolei “- 1” stosowane jest, bo ostatni cykl byłby wykonywany na posortowanej tablicy/liście, co jest niepotrzebne, można więc ten krok pominąć. Natomiast druga pętla powinna działać do n - i - 1 iteracji, gdzie zmienna i jest wartością zmienianą przez zewnętrzną pętlę for.
Zapis n - i - 1 sprawia, że posortowane elementy znajdujące się na końcu listy nie są uwzględniane w kolejnych przebiegach. To istotne, bo te elementy są już prawidłowo porozmieszczane i nie ma potrzeby ponownego ich sprawdzania. Jeśli element o indeksie j jest większy od tego o indeksie j + 1, nastąpi zamiana miejscami.

tab = [5, 3, 8, 2, 1, 7]

# Kod algorytmu zoptymalizowanego sortowania bąbelkowego
n = len(tab)
for i in range(n - 1):
    for j in range(n - i - 1):
        if tab[j] > tab[j + 1]:
            pom = tab[j]
            tab[j] = tab[j + 1]
            tab[j + 1] = pom

# Wypisanie posortowanej listy
for element in tab:
    print(element, end=" ")

#include <iostream>
using namespace std;
int main() {
    int tab[] = {5, 3, 8, 2, 1, 7};
    int n = sizeof(tab) / sizeof(tab[0]); // automatyczne wskazanie ilosci elementow danej tablicy

    // Kod algorytmu zoptymalizowanego sortowania babelkowego
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (tab[j] > tab[j+1]) {
                int pom = tab[j];
                tab[j] = tab[j+1];
                tab[j+1] = pom;
            }
      }
}

    // Wypisanie posortowanej tablicy
    for (int i = 0; i < n; i++) {
        cout << tab[i] << " ";
    }
    return 0;
}

public class Main {
    public static void main(String[] args) {
        int[] tab = {5, 3, 8, 2, 1, 7};

        // Kod algorytmu zoptymalizowanego sortowania babelkowego
        for (int i = 0; i < tab.length - 1; i++) {
            for (int j = 0; j < tab.length - i - 1; j++) {
                if (tab[j] > tab[j+1]) {
                    int pom = tab[j];
                    tab[j] = tab[j+1];
                    tab[j+1] = pom;
                }
            }
        }

        // Wypisanie posortowanej tablicy
        for (int element : tab) {
            System.out.print(element + " ");
            }
        }
}

Złożoność obliczeniowa sortowania bąbelkowego

Złożoność pamięciowa sortowania bąbelkowego to O(1).

Złożoność czasowa sortowania bąbelkowego to O(n²), jeśli chodzi o wersję podstawową (bez dołączonych optymalizacji).

Algorytm sortowania bąbelkowego cechuje się niską wydajnością przy większych zbiorach danych. Przechodzi przez cały zestaw, porównując kolejne pary sąsiadujących elementów, a po zakończeniu procesu rozpoczyna nową iterację. W najbardziej niekorzystnym przypadku (sytuacja pesymistyczna) elementy są posortowane odwrotnie do wymaganego przez algorytm porządku (czy to rosnącego, czy malejącego). Ta sytuacja dotyczy jednak jedynie zoptymalizowanej wersji algorytmu, ponieważ podstawowa wersja zawsze wykonuje tę samą liczbę operacji, niezależnie od początkowego układu danych.

Sposoby optymalizacji sortowania bąbelkowego

Oprócz wcześniej przedstawionego podejścia jedną z najprostszych metod optymalizacji tego algorytmu jest wprowadzenie specjalnej flagi, która sygnalizuje, czy w danej iteracji zaszły jakiekolwiek zmiany. Jeżeli w trakcie cyklu sortowania nie doszło do przestawienia żadnego elementu, oznacza to, że zbiór danych jest już odpowiednio posortowany (czy to rosnąco, czy malejąco) i można przerwać dalsze działanie algorytmu. Choć taka zmiana nieco wydłuża czas trwania pojedynczej pętli, może znacząco ograniczyć liczbę niepotrzebnych iteracji, szczególnie w przypadku większych zbiorów danych.

Najczęściej zadawane pytania o sortowanie bąbelkowe