Sortowanie bąbelkowe
CZEGO DOWIESZ SIĘ Z TEJ LEKCJI?
- Jak przebiega sortowanie bąbelkowe?
- Jaka jest złożoność czasowa sortowania bąbelkowego?
- Jak wygląda implementacja sortowania bąbelkowego w pseudokodzie oraz wybranych językach programowania?
- Dlaczego warto dobrze poznać sortowanie bąbelkowe?
NA CO POZWALA SORTOWANIE BĄBELKOWE?
Sortowanie bąbelkowe pozwala na uporządkowanie zbioru danych.
Na maturze musisz znać co najmniej jeden algorytm sortowania. Koncepcja oraz implementacja sortowania bąbelkowego jest dość prosta, dlatego zachęcam Cię do tego, żeby naprawdę dobrze opanować właśnie ten algorytm.
JAK PRZEBIEGA ALGORYTM?
Porządkowanie zbioru danych odbywa się poprzez porównywanie dwóch kolejnych elementów. Jeżeli elementy te zaburzają porządek w naszym zbiorze – należy zamienić ze sobą ich kolejność.
Na przykłady, jeśli sortujemy dane rosnąco to para liczb 5 oraz 4 zaburza nasz porządek. Liczba 4 powinna być przed liczbą 5. W związku z tym należy zamienić ich kolejność.
I w taki sposób należy przeanalizować cały nasz zbiór. Spróbujmy posortować rosnąco poniższą tablicę, zgodnie z zasadami sortowania bąbelkowego, żeby lepiej zrozumieć jego schemat.
TABLICA WEJŚCIOWA: A = [44, 19, 7, 15] 1. porównanie: [44, 19, 7, 15] 44 > 19 -> ZAMIANA 2. porównanie: [19, 44, 7, 15] 44 > 7 -> ZAMIANA 3. porównanie: [19, 7, 44, 15] 44 > 15 -> ZAMIANA Po 1. przejściu przez tablicę: [19, 7, 15, 44] Zielonym kolorem oznaczam wszystkie elementy, dla których mamy pewność, że znajdują się na odpowiedniej pozycji. Zauważ, że teraz ostatni element w tablicy jest największy. Łatwo skojarzyć - największy bąbelek wypłynął już na powierzchnię. 😉 W związku z tym przy następnym przejściu przez możemy wykonać jedno porównanie mniej. Ostatnia liczba jest już na pewno na poprawnej pozycji. 4. porównanie: [19, 7, 15, 44] 19 > 7 -> ZAMIANA 5. porównanie: [7, 19, 15, 44] 19 > 15 -> ZAMIANA Po 2. przejściu przez tablicę: [7, 15, 19, 44] Kolejny największy bąbelek wypłynął na powierzchnię. Przy następnej iteracji możemy wykonać jedno porównanie mniej. 6. porównanie: [7, 15, 19, 44] 7 < 15 -> BRAK ZAMIANY Po 3. przejściu przez tablicę: [7, 15, 19, 44]
ZŁOŻONOŚĆ CZASOWA
- Zewnętrzną, odpowiadającą za wyznaczenie niezbędnej liczby przejść przez tablicę.
- Jest ich zawsze n – 1, gdzie n oznacza liczba elementów w tablicy.
- Wewnętrzną, umożliwiającą wykonanie odpowiednich porównań par liczb.
- W pierwszej iteracji mamy n – 1 porównań.
- W każdej kolejnej iteracji liczba niezbędnych porównań zmniejsza się o 1.
Podsumowując, algorytm wykonuje n – 1 przejść, a w każdym z nich wykonuje n – i porównań (gdzie i = 1, 2, …, n – 1). Pozwala nam to wywnioskować, że złożoność czasowa tego algorytmu to O(n^2).
✍️ IMPLEMENTACJA – PSEUDOKOD (SORT. ROSNĄCE)
📊 DANE: • A[1..n] - tablica liczb całkowitych, którą należy posortować, • n - liczba całkowita dodatnia. 🙌 WYNIK: • A[1..n] - posortowana rosnąco tablica liczb całkowitych. 📚 ALGORYTM: funkcja sortowanie_bąbelkowe(A, n) dla i = 1, 2, ..., n - 1 wykonuj dla j = 1, 2, ..., n - i wykonuj jeżeli A[j] > A[j + 1] pom = A[j] A[j] = A[j + 1] A[j + 1] = pom
Jak należałoby zmodyfikować powyższy fragment kodu, aby posortować zbiór malejąco? 🤔
🐍 IMPLEMENTACJA – PYTHON (SORT. ROSNĄCE)
def sortowanie_bąbelkowe(tablica): liczba_elementów = len(tablica) # Wykonanie niezbędnej liczby przejść przez tablicę for i in range (0, liczba_elementów - 1): # Wykonanie odpowiedniej liczby porównań for j in range(0, liczba_elementów - i - 1): if tablica[j] > tablica[j + 1]: # Jeżeli elementy zaburzają porządek to należy je ze sobą zamienić tablica[j], tablica[j + 1] = tablica[j + 1], tablica[j]
🔬 IMPLEMENTACJA – C++ (SORT. ROSNĄCE)
void sortowanieBabelkowe(int tablica[], int liczbaElementow) { // Wykonanie niezbędnej liczby przejść przez tablicę for (int i = 0; i < liczbaElementow - 1; i++) { // Wykonanie odpowiedniej liczby porównań for (int j = 0; j < liczbaElementow - i - 1; j++) { if (tablica[j] > tablica[j + 1]) { // Jeżeli elementy zaburzają porządek to należy je ze sobą zamienić int pom = tablica[j]; tablica[j] = tablica[j+1]; tablica[j+1] = pom; } } } }
☕ IMPLEMENTACJA – JAVA (SORT. ROSNĄCE)
void sortowanieBabelkowe(int tablica[]) { int liczbaElementow = tablica.length; // Wykonanie niezbędnej liczby przejść przez tablicę for (int i = 0; i < liczbaElementow - 1; i++) { // Wykonanie odpowiedniej liczby porównań for (int j = 0; j < liczbaElementow - i - 1; j++) { if (tablica[j] > tablica[j + 1]) { // Jeżeli elementy zaburzają porządek to należy je ze sobą zamienić int pom = tablica[j]; tablica[j] = tablica[j+1]; tablica[j+1] = pom; } } } }
MATERIAŁ WIDEO
Jeżeli masz jakiekolwiek pytania dot. sortowania bąbelkowego zostaw proszę komentarz.
Chętnie odpowiem na wszystkie Twoje pytania! 😌
2 komentarzy
Hejka! Czy na maturze pojawiają się tak duże zbiory, w których sortowanie bąbelkowe jest niewydajne? Jeśli tak, to czy jakiego innego sposobu sortowania najbardziej opłaca się nauczyć? Z góry dziękuję za pomoc 😀
Cześć! Jak do tej pory nie było takiego zadania, z którym sortowanie bąbelkowe sobie by nie poradziło w rozsądnym czasie (do kilku sekund). Zbiory danych w części praktycznej to maksymalnie kilka tysięcy wartości, więc nie powinno być żadnego problemu. Jeżeli potrzebujesz czegoś, co na 100% będzie wydajne to zachęcam do zerknięcia na Sortowanie szybkie lub Sortowanie przez scalanie. Moim zdaniem przez scalanie jest nieco łatwiejsze 😊
Potencjalnie bardziej pozostałe algorytmy mogą przydać się w części teoretycznej. Ale tam będzie to bardziej wynikało z faktu, że autorzy zadania chcą konkretny rodzaj sortowania, a nie dlatego że bąbelkowe sobie nie poradzi.
Także warto poznać wszystkie sortowania, ale bąbelkowe powinno w praktycznej części wystarczyć spokojnie 😊