Strona główna » Algorytmy » Sortowanie » Sortowanie Bąbelkowe
 

Sortowanie Bąbelkowe

O sortowaniu

Sortowanie bąbelkowe (ang. bubble sort) polega na ustawianiu każdego elementu w odpowiednim miejscu poprzez porównywanie kolejnych elementów listy L. Na początku bierzemy pod uwagę wszystkie elementy listy L czyli od indeksu 0 do n-1. Porównujemy każdą parę elementów: 1 z 2, 2 z 3, ..., n-2 z n-1. Elementy w każdej parze zamieniamy jeśli pierwsze jest mniejszy od drugiego w przypadku sortowania rosnąco. W przypadku sortowania malejąco elementy przestawiamy kiedy w parze pierwszy element jest mniejszy od drugie. Po zakończeniu iteracji wykonujemy sortowanie na liście bez ostatniego elementu listy, ponieważ znajduje się tam już elementy największy / najmniejszy w zależności od sortowania. Czynności powtarzamy, aż otrzymamy do posortowania listę mającą tylko jeden element.

Przykład

Weźmy przykładowo listę L={5, 3, 4, 1, 2}. Będziemy sortować elementy rosnąco. Zaczynamy od pełnej listy L. W każdym porównaniu pogrubione zostały elementy, które porównujemy, a kursywą zostały zaznaczone elementy zamienione miejscami:

ListaPorównanieOperacja
5, 3, 4, 1, 25 > 3zamiana 5 z 3
3, 5, 4, 1, 25 > 4zamiana 5 z 4
3, 4, 5, 1, 25 > 1zamiana 5 z 1
3, 4, 1, 5, 25 > 2zamiana 5 z 2
3, 4, 1, 2, 5--

Wykonaliśmy jedną pełną pętle zamiany elementów. W tym momencie największy element znalazł się na końcu listy czyli będziemy teraz sortować elementy od indeksu 0 do n-2:

ListaPorównanieOperacja
3, 4, 1, 23 < 4nie zamieniamy
3, 4, 1, 24 > 1zamieniamy 4 z 1
3, 1, 4, 24 > 2zamieniamy 4 z 2
3, 1, 2, 4--

Posortowaliśmy pod listę i na ostatnim miejscu znów mamy największy element, który możemy odłożyć na bok i posortować listę bez dwóch ostatnich elementów czyli {3, 1, 2}.

ListaPorównanieOperacja
3, 1, 23 > 1zamiana 3 z 1
1, 3, 23 > 2zamiana 3 z 2
1, 2, 3--

Aktualnie pełna lista wygląda tak: {1, 2, 3, 4, 5} co oznacza, że lista została posortowana, ale nasz algorytm o tym nie wie, dlatego wykona jeszcze jedną operacje porównania bez zamiany dla podlisty {1, 2}. Tu właśnie tkwi problem z algorytmem - niezależnie od postaci listy zostanie wykonane tyle samo operacji porównania. Co najwyżej zostanie wykonanych mniej operacji zamiany.

Ustaliliśmy już, że liczba operacji dla dowolnej listy długości n jest stała, więc możemy obliczyć złożoność czasową: , dlatego złożoność algorytmu jest rzędu . Istnieje możliwości napisania algorytmu tak, że jeśli nie wykryje zamiany w danym kroku to oznacza, że ciąg jest już posortowany. Pozwoliłoby to zaoszczędzić nieco czasu.

Implementacja

Załóżmy, że chcemy posortować ciąg liczb rzeczywistych typu double. Do funkcji przekażemy wskaźnik na listę L oraz liczbę całkowitą n - długość listy L:

  1. void sort(double* L, int n){
  2.   double t;
  3.   for(int i = 0; i < n - 1; i++){
  4.     for(int j = 0; j < n - i - 1; j++){
  5.       if(L[j] > L[j + 1]){
  6.         t = L[j];
  7.         L[j] = L[j + 1];
  8.         L[j + 1] = t;
  9.       }
  10.     }
  11.   }
  12. }

(2.) Deklarujemy zmienna pomocniczą t do zamiany miejscami danych. (3.) Rozpoczynamy n-1 pętli dla których (4.) wyliczamy jak długą listę porównujemy. (5.) Jeśli kiedykolwiek zachodzi, że w parze element ja miejscu j jest większy od elementu na j+1 to (6. - 8.) zamieniamy je miejscami.

Testowanie funkcji

Po uruchomieniu programu należy wpisać liczbę n jak długa jest lista, a potem n elementów.

  1. int main () {
  2.   int n;
  3.   cin >> n;
  4.   double* L = new double[n];
  5.   for(int i = 0; i < n; i++)
  6.     cin >> L[i];
  7.   sort(L, n);
  8.   for(int i = 0; i < n; i++)
  9.     cout << L[i] << " ";
  10.   delete[] L;
  11.   system("pause");
  12.   return 0;
  13. }

Przykładowo dla listy [5 3 4 1 2] otrzymamy:

  1. 1 2 3 4 5

Zadania

Zadanie 1

Zmodyfikuj kod źródłowy, aby funkcja sort() sortowała malejąco liczby całkowitoliczbowe.

Przykładowo dla listy [5 3 4 1 2] program wypisze na ekran:

  1. 5 4 3 2 1