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:

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:

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}.

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

• Kod źródłowy Implementacja

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

• Kod źródłowy Zadanie 1