:~$ newsletter --subscribe
cat ~/artykuly/algorytmy/sortowanie-babelkowe-algorytm-klasy-on2.md

Sortowanie bąbelkowe, algorytm klasy O(N2)

Algorytm sortowania „bąbelkowego” jest jednym z najprostszych algorytmów służących do sortowania liczb, o złożoności czasowej O(N2) i pamięciowej O(1).

Jego nazwa wzięła się od „pęcherzyków powietrza”, które ulatywały w górę tuby wypełnionej wodą. Jeżeli tablicę danych potraktujemy jak pojemnik z wodą, a zawarte w niej dane jako pęcherzyki powietrza, to najszybciej do góry będą lecieć najlżejsze, czyli liczby o najmniejszej wartości.

Algorytm ten opiera się na zasadzie „maximum”. To znaczy, że każda liczba jest mniejsza lub równa w stosunku do liczby maksymalnej. Kiedy będziemy porównywać kolejno liczby, to możemy wyznaczyć największą z nich. Następnie pozostałe dane możemy skrócić o znalezioną wcześniej liczbę i po raz kolejny szukać największej liczby. Ten element będziemy powtarzać do momentu kiedy zostanie nam tylko jedna liczba. Dzięki czemu ciąg liczb będzie uporządkowany.

Kod będzie wykonywał n-1 przejść, a w każdym przejściu n-1 porównań. Więc jego teoretyczna złożoność czasowa będzie wynosić O(n2).

Przykład działania

Załóżmy, że mamy ciąg wejściowy [4,2,5,1,7], a każdy kolejny wiersz znajdujący się na poniższej ilustracji symbolizuje wypchnięcie największego elementu na koniec:

Niebieski fragment, oznacza posortowane liczby
Niebieski fragment, oznacza posortowane liczby. Fot: Wikipedia.

Przykładowy program wykorzystujący algorytm sortowania bąbelkowego (napisany w języku Pascal):

pascal
program sortowanieBabelkowe;
USES crt;
VAR
    liczby:array[1..6] of integer;
    i,j,tmp:integer;
BEGIN
    clrscr;
    {wypełniamy tablice liczbami}
    writeln('Podaj 6 liczb, które chcesz posortować:');
    for i:= 1 to 6 do
        readln(liczby[i]); {zapisujemy liczby}

    {sortowanie}
    for i:=1 to 5 do
         for j:=1 to 5 do
              if liczby[j] > liczby[j+1] then
                   begin
                   tmp := liczby[j];
                   liczby[j] := liczby[j+1];
                   liczby[j+1] := tmp;
                   end;

     {wyświetlamy posortowane liczby}
     writeln('Posortowane liczby:');
     for i:=1 to 6 do
          writeln(liczby[i]);

     repeat until keypressed;
END.

Przebieg sortowania krok po kroku

Prześledźmy jeden pełny przebieg na tablicy [5, 1, 4, 2]. Porównujemy sąsiadów i zamieniamy, gdy lewy jest większy:

PorównanieTablica po krokuZamiana?
5 i 1[1, 5, 4, 2]tak
5 i 4[1, 4, 5, 2]tak
5 i 2[1, 4, 2, 5]tak

Po pierwszym przebiegu największa liczba „wypłynęła” na koniec, dokładnie jak bąbelek z nazwy algorytmu. Kolejne przebiegi robią to samo dla coraz krótszego fragmentu, aż tablica będzie posortowana: po drugim przebiegu mamy [1, 2, 4, 5] i koniec.

Implementacja w C++ z optymalizacją

cpp
#include <iostream>
using namespace std;

int main() {
    int tab[] = {5, 1, 4, 2, 8, 3};
    int n = 6;

    for (int i = 0; i < n - 1; i++) {
        bool zamiana = false;                 // optymalizacja: flaga
        for (int j = 0; j < n - 1 - i; j++) { // koniec juz posortowany
            if (tab[j] > tab[j + 1]) {
                swap(tab[j], tab[j + 1]);
                zamiana = true;
            }
        }
        if (!zamiana) break;   // caly przebieg bez zamian = posortowane
    }

    for (int i = 0; i < n; i++) cout << tab[i] << " ";
    return 0;
}

Dwie rzeczy poprawiają tu podstawową wersję. Wewnętrzna pętla kończy się na n - 1 - i, bo końcówka tablicy jest już posortowana po wcześniejszych przebiegach. Flaga zamiana pozwala wyjść wcześniej: przebieg bez ani jednej zamiany oznacza, że dane są już uporządkowane. Dzięki fladze posortowana tablica kosztuje tylko jeden przebieg, czyli O(n) w najlepszym przypadku.

To samo w Pythonie

python
def sortowanie_babelkowe(tab):
    n = len(tab)
    for i in range(n - 1):
        zamiana = False
        for j in range(n - 1 - i):
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
                zamiana = True
        if not zamiana:
            break
    return tab


print(sortowanie_babelkowe([5, 1, 4, 2, 8, 3]))   # [1, 2, 3, 4, 5, 8]

Skąd bierze się złożoność O(n²) i czy to dużo?

Dwie zagnieżdżone pętle po tablicy dają w najgorszym przypadku około n·n/2 porównań, a stałe w notacji pomijamy, stąd O(n²). Co to znaczy w praktyce, opisałem szerzej we wpisie o złożoności obliczeniowej: przy tysiącu elementów to już milion operacji, podczas gdy dobre sortowania (przez scalanie, quicksort) potrzebują około dziesięciu tysięcy. Dlatego sortowanie bąbelkowe ma dziś wartość głównie dydaktyczną: jest świetne do nauki myślenia algorytmicznego, ale w realnym kodzie sortujemy funkcją biblioteczną (std::sort, sorted()).

Wersje w Javie i C#

Java:

java
import java.util.Arrays;

public class Main {

    public static void sortowanieBabelkowe(int[] tab) {
        for (int i = 0; i < tab.length - 1; i++) {
            boolean zamiana = false;
            for (int j = 0; j < tab.length - 1 - i; j++) {
                if (tab[j] > tab[j + 1]) {
                    int tmp = tab[j];
                    tab[j] = tab[j + 1];
                    tab[j + 1] = tmp;
                    zamiana = true;
                }
            }
            if (!zamiana) break;   // brak zamian = posortowane
        }
    }

    public static void main(String[] args) {
        int[] liczby = {5, 1, 4, 2, 8, 3};
        sortowanieBabelkowe(liczby);
        System.out.println(Arrays.toString(liczby));   // [1, 2, 3, 4, 5, 8]
    }
}

C#:

csharp
using System;

class Program
{
    static void SortowanieBabelkowe(int[] tab)
    {
        for (int i = 0; i < tab.Length - 1; i++)
        {
            bool zamiana = false;
            for (int j = 0; j < tab.Length - 1 - i; j++)
            {
                if (tab[j] > tab[j + 1])
                {
                    (tab[j], tab[j + 1]) = (tab[j + 1], tab[j]);
                    zamiana = true;
                }
            }
            if (!zamiana) break;
        }
    }

    static void Main()
    {
        int[] liczby = {5, 1, 4, 2, 8, 3};
        SortowanieBabelkowe(liczby);
        Console.WriteLine(string.Join(" ", liczby));   // 1 2 3 4 5 8
    }
}
Łukasz Dudziński
Łukasz Dudziński · założyciel i autor
Pasjonat informatyki, a zwłaszcza programowania. Zwariowany maniak na tle nowych technologii oraz komputerów. W wolnych chwilach bloger... więcej-o-mnie →
ls ~/artykuly/powiazane --limit 3
komentarze --count 1
rss dla komentarzy →
Łukasz Kosiński2017-04-23 ·

Lepiej znać tak sobie wydajne sortowanie, aniżeli żadne :)

dodaj-komentarz

Komentarze są moderowane. Podane dane przetwarzamy wyłącznie w celu publikacji komentarza (polityka prywatności).