Sortowanie bąbelkowe

Sortowanie bąbelkowe to jeden ze sposobów sortowania serii danych, które można zaimplementować w dowolnym języku programowania. W kolejnych cyklach działania algorytmu największe wartości zostają przesunięte w prawo, na koniec serii danych. Operacja ta powtarza się, aż wszystkie wartości zostaną ułożone w zadanej kolejności, tzn. nierosnąco lub niemalejąco. Po przeanalizowaniu złożoności tego algorytmu dowiesz się, że prostota jego zapisu nie idzie jednak w parze z szybkością działania, dlatego najlepiej używać go do sortowania niewielkich zestawów danych.

Przykład realizacji algorytmu

Nauczyciel informatyki poprosił chętnych o zgłoszenie się do udziału w konkursie programowania. Uczniowie wpisywali się na listę, podając swój numer z dziennika szkolnego. Lista zawierała następujące liczby: 6, 7, 3, 1, 4, 2, 8, 5.

Naszym zadaniem jest posortowanie listy chętnych rosnąco. Użyjemy do tego celu sortowania bąbelkowego.

Zaczynamy od zapisania numerów w odpowiedniej strukturze danych, np. w tablicy lub liście.

R11uwPrczUYZ7

Ilustracja przedstawia rząd liczb, kolejno od lewej strony do prawej: 6, 7, 3, 1, 4, 2, 8, 5.

Krok 1

Porównujemy ze sobą dwie pierwsze liczby – czyli 6 i 7.

RJ2hduvkBzFSp

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 7, 3, 1, 4, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 6, 7.

Liczba 6 jest mniejsza od 7, więc nie następuje zamiana.

Krok 2

Teraz porównujemy liczby 7 i 3.

RLvki8yhexyQs

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 7, 3, 1, 4, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 7, 3.

Liczba 7 jest większa od 3, więc następuje zamiana.

R1WgzuwNSrKdt

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 7, 1, 4, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 3, 7.

Krok 3

Następnie porównujemy liczby 7 i 1.

RoT8kF2TwuLaO

Ilustracja przedstawia tablicę wypełnioną liczbami: 6, 3, 7, 1, 4, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 7, 1.

Liczba 7 jest większa od 1, więc następuje zamiana.

RPUWVMyAiqbCp

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 7, 4, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 1, 7.

Krok 4

Dalej porównujemy liczby 7 i 4.

R16KGV4Wqph5o

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 7, 4, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 7, 4.

Liczba 7 jest większa od 4, więc następuje zamiana.

RsGl2hU9zVN4d

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 4, 7, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 4, 7.

Krok 5

Teraz porównujemy liczby 7 i 2.

R15MYawMqgXZI

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 4, 7, 2, 8, 5. Czerwonym okręgiem zaznaczono liczby: 7, 2.

Liczba 7 jest większa od 2, więc następuje zamiana.

R9ES2VN6rqhtX

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 4, 2, 7, 8, 5. Czerwonym okręgiem zaznaczono liczby: 2, 7.

Krok 6

Następnie porównujemy liczby 7 i 8.

RjaMaX0QTbSob

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 4, 2, 7, 8, 5. Czerwonym okręgiem zaznaczono liczby: 7, 8.

Liczba 7 jest mniejsza od 8, więc nie następuje zamiana.

Krok 7

Na koniec porównujemy dwie ostatnie liczby: 8 i 5.

RedSDr6ytNZ8e

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 4, 2, 7, 8, 5. Czerwonym okręgiem zaznaczono liczby: 8, 5.

Liczba 8 jest większa od 5, więc następuje zamiana.

R8zSLndhA4L6a

Ilustracja przedstawia rząd liczb, kolejno od lewej do prawej strony: 6, 3, 1, 4, 2, 7, 5, 8. Czerwonym okręgiem zaznaczono liczby: 5, 8.

Po zakończeniu ostatniego kroku liczba 8, czyli największa liczba w rozważanym ciągu, znajdzie się na ostatnim miejscu w tablicy, a więc na swoim miejscu docelowym. Ponieważ pozostałe elementy tablicy (poza liczbą 8) wciąż nie są posortowane, należy wrócić do początku tablicy i ponownie wykonywać po kolei wszystkie porównania.

W każdym kolejnym cyklu przeglądany ciąg będzie krótszy, dlatego w poszczególnych cyklach zostanie wykonane $n-i$ porównań, gdzie:

• $n$ – rozmiar tablicy, która ma zostać posortowana,

• $i$ – kolejny numer wykonywanego cyklu.

Po każdym cyklu algorytmu największy element obecnie analizowanego ciągu zostanie umieszczony na końcu, co oznacza, że w każdym przebiegu kolejna liczba znajdzie się na prawidłowej pozycji (elementy ciągu nierozważane w trakcie obiegu są już posortowane). Algorytm powinien wykonywać się do momentu, gdy wszystkie wartości zostaną posortowane.

Poniżej zostały przedstawione dwie wersje algorytmu sortowania bąbelkowego zapisane przy użyciu pseudokodu: podstawowa (nieuwzględniająca wcześniejszego zakończenia wykonywania algorytmu) i usprawniona (mogąca zakończyć się wcześniej w przypadku posortowania ciągu).

Pseudokod algorytmu sortowania bąbelkowego

Proces sortowania metodą bąbelkową można zapisać za pomocą następującego pseudokodu:

Sortowanie_babelkowe(tablica, n)
	Dla i = 0, 1, 2, ... n - 2, wykonuj
		Dla j = 0, 1, 2, ... n - i - 2, wykonuj
			Jeżeli tablica[j] > tablica[j + 1], to
            	pomocnicza ← tablica[j + 1]
                tablica[j + 1] ← tablica[j]
				tablica[j] ← pomocnicza

• Pętla zewnętrzna odpowiada za wykonanie kolejnych cykli sortowania. Pętla ta zostanie wykonana $n-1$ razy, gdzie $n$ to liczba elementów sortowanego ciągu. W ostatnim cyklu sortowania elementy ciągu będą już posortowane.

• W pętli wewnętrznej porównywane są kolejne wartości, począwszy od lewej strony (mniejszych indeksów tablicy). Pętla ta zaczyna się od indeksu $0$ (pierwszego elementu sortowanej tablicy) i kończy na indeksie $n-i-2$ (przedostatnim elemencie nieposortowanej jeszcze części tablicy). Jest to spowodowane tym, że porównujemy obecny i następny element tablicy. W ograniczeniu pętli odejmujemy 2 od wartości $n-i$, żeby pętla wewnętrzna mogła się wykonać we wszystkich iteracjach pętli zewnętrznej (dla $j=n-i-2$ zawartość również się wykona, w wyniku czego otrzymamy $n-i-1$ wykonań kodu zawartego w pętli wewnętrznej, na obieg pętli zewnętrznej). Następnie w pętli wewnętrznej porównywane są kolejne pary elementów. Jeśli poprzedni element jest większy od następującego po nim, zostaje wykonana zamiana.

Sortowanie_babelkowe(tablica, n)
  Dla i = 0, 1, 2, ... n - 2, wykonuj
  	flaga ← fałsz
  	Dla j = 0, 1, 2, ... n - i - 2, wykonuj
  		Jeżeli tablica[j] > tablica[j + 1], to
  			pomocnicza ← tablica[j + 1]
  			tablica[j + 1] ← tablica[j]
  			tablica[j] ← pomocnicza
  			flaga ← prawda
  	Jeżeli flaga = fałsz
  		zakończ wykonywanie pętli

Sortowanie_babelkowe(tablica, n)
  Dla i = 0, 1, 2, ... n - 2, wykonuj
  	flaga ← fałsz
  	Dla j = 1, 2, 3 ... n - i - 1, wykonuj
  		Jeżeli tablica[j - 1] > tablica[j], to
  			pomocnicza ← tablica[j - 1]
  			tablica[j - 1] ← tablica[j]
  			tablica[j] ← pomocnicza
  			flaga ← prawda
  	Jeżeli flaga = fałsz
  		zakończ wykonywanie pętli

Złożoność czasowa i pamięciowa algorytmu

W rozważanym algorytmie operacją dominującą (elementarną) jest porównanie wartości sąsiednich elementów.

Złożoność czasowa przypadku pesymistycznego

Przypadek pesymistyczny to najgorszy z punktu widzenia programu zestaw danych, czyli taki, dla którego program wykona najwięcej porównań.

W przypadku pesymistycznym sortować będziemy tablicę uporządkowaną odwrotnie, czyli np. posortujemy niemalejąco tablicę zawierająca liczby uporządkowane nierosnąco. W takiej sytuacji wykonamy najwięcej zamian i maksymalną liczbę porównań.

Wykona się więc $n-1$ cykli po $n-i$ porównań, gdzie $i$ to numer cyklu.

Przybliżona liczba operacji porównania (operacji dominujących) wykonanych przez algorytm będzie wynosić: ${\mathrm{n}}^2$. Zatem złożoność czasowazłożoność czasowazłożoność czasowa wyniesie: $O\left({\mathrm{n}}^2\right)$.

Złożoność czasowa przypadku optymistycznego

Przypadek optymistyczny to najlepszy z punktu widzenia programu zestaw danych, czyli taki, dla którego program wykona najmniej porównań.

Jeżeli poprawimy algorytm tak, żeby kończył działanie, gdy w ostatnim przebiegu (iteracji pętli zewnętrznej) nie została wykonana żadna zamiana, to będziemy w stanie ograniczyć liczbę wykonywanych operacji elementarnych. Rozwiązanie to pozwoli usprawnić działanie algorytmu, a tym samym zaoszczędzić czas poprzez ograniczenie liczby iteracji. Przykładowo, przy rozważaniu przypadku optymistycznego (czyli od razu posortowanej tablicy) będziemy mogli zakończyć działanie algorytmu po pierwszym obiegu zewnętrznej pętli. Najczęściej rozwiązanie to implementowane jest w postaci zmiennej pełniącej rolę flagi, która jest podnoszona przy dokonywaniu zamiany. Jeżeli pod koniec obiegu pętli zewnętrznej flaga nie jest podniesiona, oznacza to, że nie została dokonana żadna zamiana i można zakończyć działanie algorytmu.

Wykona się więc 1 cykl wykonujący $n-1$ porównań (liczba elementów sortowanych zmniejszona o 1, czyli liczba kolejnych par elementów sortowanych). Jeśli przy sortowaniu tablicy, na której przykładzie omówiliśmy algorytm, zaistniałby przypadek optymistyczny, liczba porównań wynosiłaby 7.

Zatem przybliżona liczba operacji porównania (operacji dominujących) wykonana przez algorytm będzie wynosić: ${\mathrm{n}}^{}$, czyli jego złożoność czasowa to: $O\left({\mathrm{n}}^{}\right)$.

Można zauważyć, że w tej sytuacji algorytm pesymistyczny wykona się n razy wolniej niż optymistyczny.

Bez flagi zaprezentowany algorytm będzie miał złożoność czasową kwadratową, czyli $O\left({\mathrm{n}}^2\right)$. Wynika to z faktu, że algorytm, mimo że nie dokonuje zamian i tak zrealizuje wszystkie cykle. Wykona się więc $n-1$ cykli po $n-i$ porównań.

Złożoność pamięciowa algorytmu

Sortowanie bąbelkowe wykonywane jest w jednej tablicy poprzez przestawianie jej elementów, więc potrzebuje tylko tyle miejsca w pamięci, ile zajmą elementy tablicy. Algorytm ten nie zajmuje dodatkowej pamięci, zatem złożoność pamięciowazłożoność pamięciowazłożoność pamięciowa tego algorytmu jest stała i zależna od liczby sortowanych elementów. Taka złożoność pamięciowa oznaczana jest symbolem $O\left(1\right)$. Jest to tzw. algorytm sortowania w miejscu.

Słownik