I_P_W14_M11 Sortowanie metodą bąbelkową
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.
Przedstaw działanie algorytmu sortowania bąbelkowego na nieuporządkowanym ciągu liczb. Dane powinny zostać posortowane niemalejąco. Ciąg do posortowania zapisany został w tablicy w następującej postaci: [6, 7, 3, 1, 4, 2, 8, 5].
Specyfikacja problemu:
Dane:
n– liczba elementów ciągu do posortowania (rozmiar tablicy)tablica[]– tablica z nieposortowanym ciągiem wybranych liczb naturalnych
Wynik:
tablica[]– ciąg liczb przechowywany w tablicy, posortowany niemalejąco
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.
Krok 1
Porównujemy ze sobą dwie pierwsze liczby – czyli 6 i 7.
Liczba 6 jest mniejsza od 7, więc nie następuje zamiana.
Krok 2
Teraz porównujemy liczby 7 i 3.
Liczba 7 jest większa od 3, więc następuje zamiana.
Krok 3
Następnie porównujemy liczby 7 i 1.
Liczba 7 jest większa od 1, więc następuje zamiana.
Krok 4
Dalej porównujemy liczby 7 i 4.
Liczba 7 jest większa od 4, więc następuje zamiana.
Krok 5
Teraz porównujemy liczby 7 i 2.
Liczba 7 jest większa od 2, więc następuje zamiana.
Krok 6
Następnie porównujemy liczby 7 i 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.
Liczba 8 jest większa od 5, więc następuje zamiana.
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 porównań, gdzie:
– rozmiar tablicy, która ma zostać posortowana,
– 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:
Pętla zewnętrzna odpowiada za wykonanie kolejnych cykli sortowania. Pętla ta zostanie wykonana razy, gdzie 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 (pierwszego elementu sortowanej tablicy) i kończy na indeksie (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 , żeby pętla wewnętrzna mogła się wykonać we wszystkich iteracjach pętli zewnętrznej (dla zawartość również się wykona, w wyniku czego otrzymamy 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.
Algorytm można usprawnić, dodając do niego flagę, która będzie informowała, czy w danym cyklu dokonała się choć jedna zamiana. Jeżeli flaga poinformuje nas, że nie została dokonana żadna zmiana, będzie to sygnał, że ciąg jest już posortowany i możemy przerwać dalsze wykonywanie algorytmu. Przekłada się to na skrócenie jego czasu działania.
Do przedstawionego wcześniej algorytmu dodaliśmy flagę, która na początku każdego obiegu pętli zewnętrznej przyjmuje wartość fałsz. Ustawiając taką wartość flagi, zakładamy, że ciąg jest już posortowany, a następnie sprawdzamy prawdziwość tego stwierdzenia. Jeżeli okaże się, że elementy ciągu nie są posortowane i istnieje potrzeba ich zamiany miejscami, zmieniamy wartość flagi na prawda. Sygnalizujemy w ten sposób, że w tym obiegu pętli zewnętrznej została zmieniona kolejność elementów ciągu. Jeżeli po przejściu całej pętli wewnętrznej domyślna wartość flagi nie zmieniła się, oznacza to, że elementy ciągu są posortowane i możemy zakończyć wykonywanie algorytmu.