Sortowanie bąbelkowe to prosty algorytm używany do sortowania podanego zestawu n elementy podane w postaci tablicy z n liczbą elementów. Sortowanie bąbelkowe porównuje wszystkie elementy jeden po drugim i sortuje je na podstawie ich wartości.
Jeśli dana tablica ma być posortowana w kolejności rosnącej, sortowanie bąbelkowe rozpocznie się od porównania pierwszego elementu tablicy z drugi element, jeśli pierwszy element jest większy niż drugi, zamieni oba elementy, a następnie przejdzie do porównania drugiego i trzeciego elementu itd.
Jeśli mamy total n, a następnie musimy powtórzyć ten proces n-1 razy.
Jest to znane jako sortowanie bąbelkowe, ponieważ z każdą pełną iteracją największy element w danej tablicy bąbelkuje w kierunku ostatniego miejsca lub najwyższego indeksu, tak jak bąbelek wody unosi się na powierzchnię wody.
Sortowanie odbywa się poprzez przejście przez wszystkie elementy jeden po drugim i porównując je z sąsiednimi elementami i zamieniając je w razie potrzeby.
UWAGA: Jeśli nie jesteś zaznajomiony z sortowaniem w strukturze danych, powinieneś: najpierw dowiedz się, czym jest sortowanie, aby dowiedzieć się o podstawach sortowania.
Implementowanie algorytmu sortowania bąbelkowego
Poniżej przedstawiono kroki związane z sortowaniem bąbelkowym (do sortowania podanej tablicy w porządku rosnącym):
- Rozpoczynając od pierwszego elementu (indeks = 0), porównaj bieżący element z następnym elementem tablicy.
- Jeśli bieżący element jest większy niż następny element tablicy, zamień je.
- Jeśli bieżący element jest mniejszy niż następny, przejdź do następnego elementu. Powtórz krok 1.
Rozważmy tablicę z wartościami {5, 1, 6, 2, 4, 3}
Poniżej mamy obrazkowa reprezentacja tego, jak sortowanie bąbelkowe posortuje podaną tablicę.
Jak widać na powyższym przykładzie, po w pierwszej iteracji 6 jest umieszczany na ostatnim indeksie, który jest dla niego prawidłową pozycją.
Podobnie po drugiej iteracji 5 będzie na przedostatnim indeksie i tak dalej.
Czas na napisanie kodu dla sortowania bąbelkowego:
Chociaż powyższa logika posortuje nieposortowaną tablicę, nadal powyższy algorytm nie jest wydajny, ponieważ zgodnie z powyższą logiką zewnętrzne for będzie wykonywana przez 6 iteracji, nawet jeśli tablica zostanie posortowana po drugiej iteracji.
Możemy więc wyraźnie zoptymalizować nasz algorytm.
Zoptymalizowany algorytm sortowania bąbelkowego
Aby zoptymalizować nasz bubb le sort, możemy wprowadzić flag, aby monitorować, czy elementy są zamieniane wewnątrz wewnętrznej pętli for.
Dlatego w wewnętrznej for pętli sprawdzamy, czy za każdym razem ma miejsce zamiana elementów.
Jeśli dla określonej iteracji nie było zamiany place, oznacza to, że tablica została posortowana i możemy wyskoczyć z pętli for, zamiast wykonywać wszystkie iteracje.
Rozważmy tablicę z wartościami {11, 17, 18, 26, 23}
Poniżej znajduje się obrazkowa reprezentacja tego, jak zoptymalizowane sortowanie bąbelkowe posortuje daną tablicę.
Jak widać, w pierwszej iteracji nastąpiła zamiana, dlatego zaktualizowaliśmy naszą flag wartość do 1, w rezultacie wykonanie ponownie wchodzi do pętli for. Jednak w drugiej iteracji zamiana nie nastąpi, dlatego wartość flag pozostanie 0, a wykonanie wyrwie się z pętli.
W powyższym kodzie, w funkcji bubbleSort, jeśli pojedynczy pełny cykl j iteracji (wewnętrzna for pętla), nie ma zamiany, a następnie flag pozostanie 0, a następnie wyrwiemy się z pętli for, ponieważ tablica została już posortowana.
Analiza złożoności sortowania bąbelkowego
W sortowaniu bąbelkowym n-1 porównania będą wykonywane w pierwszym przebiegu, n-2 w drugim przebiegu, n-3 w trzecim przebiegu i tak dalej. Zatem całkowita liczba porównań będzie wynosić,
(n-1) + (n-2) + (n-3) + ….. + 3 + 2 + 1Sum = n (n- 1) /2i.e O (n2)
Stąd złożoność czasowa sortowania bąbelkowego wynosi O (n2).
Główną zaletą sortowania bąbelkowego jest prostota algorytmu.
Złożoność przestrzeni dla sortowania bąbelkowego wynosi O (1), ponieważ wymagana jest tylko jedna dodatkowa pamięć, tj. dla zmiennej temp.
Ponadto najlepszą złożonością czasową przypadku będzie O (n), wtedy lista jest już posortowana.
Poniżej przedstawiono złożoność czasu i przestrzeni dla algorytmu sortowania bąbelkowego.
Teraz, gdy poznaliśmy algorytm sortowania bąbelkowego, możesz sprawdzić te algorytmy sortowania i ich zastosowania:
- Sortowanie przez wstawianie
- Sortowanie przez wybór
- Szybkie sortowanie
- sortowanie scalane
- Sortowanie na stosach
- Sortowanie według liczenia
