Sortowanie bąbelkowe
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;
}
