Sortowanie bąbelkowe

kategoria: Zadania z programowania

Sortowanie bąbelkowe to prosta metoda sortowania, pozwalająca poukładać elementy danej tablicy w kolejności rosnącej lub malejącej. Elementami tablicy mogą być cyfry lub litery. Algorytm sortowania bąbelkowego porównuje dwa sąsiadujące elementy tablicy. Jeżeli element n jest większy od elementu n+1, wtedy zostają one zamienione miejscami. Algorytm powtarza się w koło do czasu, kiedy nie zajdą żadne zmiany, czyli do czasu kiedy tablica nie zostanie posortowana.

Sortowanie bąbelkowe

Sortowanie bąbelkowe to algorytm całkowicie podstawowy i należy go znać. W rozbudowanych projektach używany jest dość rzadko, ze względy na prostą budowę. Aby posortować dane, algorytm bąbelkowy wykonuje n-1 porównań, a więc np. dla tablicy 8 elementowej posortuje ją przechodząc 7 razy.

Za jego pomocą możemy sortować tablice liczb a także tablice zawierające litery. Wynika to z faktu, że każdej literze odpowiada jakiś kod ASCII, więc kompilator automatycznie bierze pod uwagę te kody podczas sortowania.

Algorytm poprawnie sortuje także litery zapisane w zmiennej string nie tablicowej. Wynika to z faktu, że zmienną string można potraktować jako tablicę liter i odwoływać się do jej elementów tak jak do elementów tablicy (kwadratowymi nawiasami).

Sortowanie bąbelkowe ma złożoność czasową: \(O(n^{n})\) oraz pamięciową: \(O(1)\).

Kod w C++ (sortowanie tekstu)

Sortowanie tekstu jest możliwe, ponieważ każda litera posiada odpowiadający jej kod ASCII. Kody ASCII ułożone są rosnąco zgodnie z alfabetem, dzięki temu sortowanie ciągu znaków działa.

#include <cstdlib>
#include <iostream>
#include <string>

using namespace std;

int main()
{
    string litery = "zaqwsxcderfvbgtyhnmjuiklop";

    for (int i=0; i<litery.length()-1; i++)
    {
        for (int j=0; j<litery.length()-1; j++)
        {
            if (litery[j]>litery[j+1])
            {
                swap(litery[j], litery[j+1]);
            }
        }
    }

    cout << litery << endl << endl;

    system("PAUSE");
    return 0;
}

Kod w C++ (sortowanie tablicy)

Równie prosto można posortować tablicę elementów:

#include <cstdlib>
#include <iostream>

using namespace std;

int main()
{
    int tablica[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};

    for (int i=0; i<9; i++)
    {
        for (int j=0; j<9; j++)
        {
            if (tablica[j]>tablica[j+1])
            {
                swap(tablica[j], tablica[j+1]);
            }
        }
    }

    for (int i = 0; i<10; i++)
    {
        cout << tablica[i] << " ";
    }

    system("PAUSE >nul");
    return 0;
}