Sortowanie bąbelkowe

Wprowadzenie

Sortowanie bąbelkowe (bubble sort) to jeden z najprostszych sposobów sortowania elementów tablic i list. To właśnie od niego zwykle zaczyna się naukę sposobów sortowania, ponieważ algorytm ten jest łatwy do wytłumaczenia i implementacji. Doskonale nadaje się do sortowania małych ilości danych. Ponieważ jest to algorytm klasy O(n²), tak więc stosowanie go do większej ilości danych mija się z celem. Jego nazwa wzięła się od tego, iż w tym sortowaniu liczby zachowują się jak bąbelki po kolei, jedna po drugiej idą do góry (lub w prawo, jak u mnie). Sortowanie bąbelkowe jest sortowaniem stabilnym.

Sortowanie bąbelkowe opiera się na bardzo prostej metodzie, a mianowicie po kolei porównywane są dwa sąsiednie elementy tablicy. Gdy element o mniejszym indeksie jest mniejszy od elementu o większym indeksie (gdy sortujemy tablicę rosnąco) to zamieniane są one miejscami. Porównywane są w ten sposób wszystkie elementy tablicy. Algorytm kończy się, gdy cała tablica jest uporządkowana.

Przykład

Przeanalizujmy prosty przykład. Mamy do posortowania rosnąco następującą tablicę:

Na początku porównujemy dwa pierwsze elementy tablicy, czyli 4 i 2 (są one podkreślone). Ponieważ 2 jest mniejsze od 4 więc zamieniamy te elementy miejscami i otrzymujemy:

Teraz porównujemy elementy drugi z trzecim, czyli 4 i -3. Tutaj także zamieniamy je miejscami i otrzymujemy:

Następnie porównujemy elementy trzeci z czwartym. Ponieważ 5 jest większe od 4, więc nic nie zmieniamy. Zgodnie z regułą porównujemy jeszcze elementy czwarty z piątym i piąty z szóstym. Doszliśmy do końca tablicy i w ten sposób otrzymujemy:

Proszę zauważyć, iż największy element tablicy jest już na swoim miejscu (zaznaczyłem to pogrubieniem). Można to wykorzystać i w późniejszych przebiegach nie brać go już pod uwagę. Ponieważ liczby nie są jeszcze posortowane, więc należy jeszcze raz wykonać porównanie dla tablicy. Po kolejnym przebiegu nasza tablica będzie miała postać:

W tym przypadku kolejny element, a mianowicie liczba 4 jest już na swoim miejscu. Tak więc za każdym przebiegiem kolejna liczba od końca jest na swoim miejscu. W ten sposób doszliśmy do wniosku, że maksymalna liczba przebiegów dla tablicy n-elementowej wynosi n-1 (gdy zostanie nam już tylko jeden element to nie ma go już z czym porównywać, a i tak jest on najmniejszy dlatego nie ma n, tylko n-1).

Sortowanie bąbelkowe z kresem górnym

W powyższym paragrafie użyłem stwierdzenia maksymalna liczba przebiegów. Może się przecież zdarzyć sytuacja, gdy tablica będzie już uporządkowana, zanim zrobimy n-1 przebiegów lub po k przebiegach więcej niż k liczb od końca będzie na swoim miejscu. Ten problem także da się ominąć. Wystarczy do naszego programu wprowadzić zmienną, która będzie reprezentować w której pozycji nastąpiła ostatnia zamiana elementów tablicy. Ta zmienna to jakby kres następnego przebiegu. Ten wariant sortowania nazywa się sortowaniem bąbelkowym z kresem górnym. Weźmy na przykład następującą tablicę do posortowania metodą bąbelkową:

Analogicznie do przykładu podanego wyżej po dwóch porównaniach nasza tablica ma postać:

Do końca tego przebiegu nie nastąpią już żadne zamiany. Ostatnią zamianą była zamiana elementu drugiego i trzeciego. Tak więc w naszej zmiennej kres pamiętamy liczbę 3 indeks ostatniego elementu, który uległ zamianie. W następnym przebiegu pod uwagę bierzemy liczby z indeksem od 1 do kres-1. Odejmujemy w tym przypadku liczbę 1 od zmiennej kres, ponieważ zmienna z indeksem kres jest już na swoim miejscu (zgodnie z wnioskiem podanym wyżej). Tak więc w naszym przypadku kolejny przebieg dojdzie tylko do liczby z indeksem 3-1, czyli 2. Jednak wróćmy do naszego problemu: skąd mamy wiedzieć, że nasza tablica jest już posortowana? Do tego posłuży nam nasza zmienna kres. Tablica jest posortowana, gdy zmienna kres ma wartość 1 (wtedy już nie ma co sortować: kres-1=1-1=0) lub gdy po kolejnym przebiegu zmienna kres nie ulegnie zmianie. Po prostu każdy kolejny przebieg kończy się na liczbie z indeksem kres-1. Tak więc, gdy nastąpiła jakakolwiek zamiana to zmienna kres musi przyjąć wartość mniejszą niż dotychczas. Jednak, gdy żadna zmiana nie nastąpiła (tablica jest posortowana) to zmienna kres pozostanie bez zmian.

Inną modyfikacją algorytmu sortowania bąbelkowego jest stosowanie ciągów przepisań zamiast zamian. W tej sytuacji zamiast zamieniać dwa elementy (co w większości przypadków statnowi 3 operacje przypisania) możemy zastosować zwykłe przepisanie (1 opereacja przypisania). Jednakże w drugim z tych przypadków należy zapamiętać w dodatkowej zmiennej pomocniczej wartość komórki tablicy od której zaczynaliśmy ciąg przepisań i po wykonaniu wszystkich przepisań wstawić tą zmienną w odpowiednie miejsce.