|
Sortownie bąbelkowe (ang. Bubble sort)
Często zachodzi potrzeba posortowania tablicy liczbowej.
Można do tego celu wykorzystać gotowe funkcje komponentów, np ListBox.
Ale warto samemy poznać przynajmniej jedną metodę "surowego" sortowania.
Przedstawiam metodę sortowania bąbelkowego. Po pierwsze dlatego że jest najprostsza.
Po drugie, dobrze (czyt. w miarę szybko) radzi sobie z tablicami liczbowymi do
1000 elementów.
Gdy tablica zawiera n-elementów, złożonośc obliczeniowa algorytmu wynosi Q(n^2).
Opis algorytmu
Przy każdym przejściu następuje porównanie liczby n-tej oraz (n+1)-tej.
Gdy liczba z lewej strony jest większa (zależy od porządku sortowania) niż liczba
z prawej strony, następuje ich zamiana. W przeciwnym wypadku nie dokonuje się żadnej zmiany.
Proces sortowania kończy się, jeśli podczas zewnętrznego przejścia algorytmu (int i) nie dokonała się żadna zamiana, tzw. "pusty przebieg".
Nazwa bierze się stąd, że przy każdym porównaniu następuję "wypłynięcie największego bąbelka".
Przykład
Sortowanie tablicy 10 liczb. Do tego celu użyjemy funkcji BubbleSort, którą napisałem. Owa funkcja przyjmuje za argument
tablicę liczb, a zwraca także tablicę liczb, tyle że uporządkowaną.
Dodatkowo na kompoentach Label1 oraz Label2 wyświetla skrajne wartości (2 Labele muszą być na formie).
double __fastcall TForm1::BubbleSort(double data[], int n, TLabel *L1, TLabel *L2)
{
for(int i=0;i<n;i++)
{
for(int j=0;j<n-1;j++)
{
if(data[j]<data[j+1])
{
int tmp;
tmp = data[j];
data[j] = data[j+1];
data[j+1] = tmp;
}
}
}
L1->Caption = data[0];
L2->Caption = data[n-1];
}
|
Aby funkcja była "widziana" przez kompilator, należy dodać jej deklarację
do sekcji published pliku h. double __fastcall BubbleSort(double data[], int n, TLabel *L1, TLabel *L2);
|
oraz sama funkcja "w akcji" double liczby[10] = {115, 23, 18, 3, 59, 99, 7, 64, 55, 8 };
BubbleSort(liczby, 10, Label1, Label2); |
Parametr int n podaje wielkość tablicy liczbowej. Poniżej przebieg algorytmu w postaci grafów. 
|
