Sortowanie bąbelkowe to prosty algorytm sortowania, który wielokrotnie przegląda listę, porównuje sąsiednie elementy i zamienia je, jeśli są w niewłaściwej kolejności. Nazywa się to „Sortowanie bąbelkowe”, ponieważ mniejsze elementy „bąbelkowe” pojawiają się na górze listy. Chociaż nie jest to najbardziej wydajny algorytm sortowania, jest łatwy do zrozumienia i wdrożenia, co czyni go dobrym punktem wyjścia do nauki o algorytmach sortowania. W tym artykule zagłębimy się w koncepcję sortowania bąbelkowego, przedstawimy implementację Pythona z wynikami i omówimy złożoność czasową algorytmu.

Zrozumienie sortowania bąbelkowego

Podstawową ideą sortowania bąbelkowego jest wielokrotna iteracja po liście, porównywanie sąsiadujących elementów i zamiana ich, jeśli nie są uporządkowane. Proces jest kontynuowany, dopóki nie będą już potrzebne żadne wymiany, co oznacza, że ​​lista jest teraz posortowana. Algorytm wziął swoją nazwę od sposobu, w jaki mniejsze elementy stopniowo przemieszczają się na górę listy, podobnie jak bąbelki unoszące się na powierzchnię.

Rozłóżmy kroki algorytmu sortowania bąbelkowego:

1. Iteruj po liście: Zacznij od początku listy i porównaj każdą parę sąsiadujących elementów.
2. Porównaj i zamień: Jeśli elementy są w niewłaściwej kolejności, zamień je. Dzięki temu większy element „bąbelkuje” w górę, a mniejszy przesuwa się w dół.
3. Kontynuuj iterację: powtarzaj proces dla każdej pary sąsiadujących elementów, aż dojdziesz do końca listy.
4. Powtarzaj aż do posortowania: Kontynuuj iterację po liście, aż nie będą już potrzebne żadne zamiany. W tym momencie lista jest posortowana.

Chociaż sortowanie bąbelkowe jest łatwe do zrozumienia, nie jest to najskuteczniejszy algorytm sortowania, szczególnie w przypadku dużych zbiorów danych. Jego złożoność czasowa wynosi w najgorszym przypadku O(n^2), gdzie „n” to liczba elementów na liście. Ta kwadratowa złożoność czasowa sprawia, że ​​jest ona mniej odpowiednia w przypadku dużych zbiorów danych w porównaniu z bardziej zaawansowanymi algorytmami sortowania.

Implementacja sortowania bąbelkowego w Pythonie

Zaimplementujmy teraz sortowanie bąbelkowe w Pythonie i obserwujmy jego zachowanie na przykładowej liście:

 def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list) 

W tej implementacji funkcja bubble_sort przyjmuje jako parametr listę (arr) i sortuje ją w miejscu. Zagnieżdżona pętla porównuje sąsiednie elementy i zamienia je, jeśli są w niewłaściwej kolejności. Zewnętrzna pętla zapewnia powtarzanie procesu do momentu posortowania całej listy.

Dane wyjściowe i wyjaśnienie

Uruchommy dostarczony kod Pythona z przykładową listą i obserwujmy wynik:

 Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90] 

Tutaj oryginalna lista [64, 34, 25, 12, 22, 11, 90] została pomyślnie posortowana przy użyciu algorytmu Bubble Sort, w wyniku czego powstała posortowana lista [11, 12, 22, 25, 34, 64, 90].

Algorytm wielokrotnie przegląda listę, porównując i zamieniając elementy, aż cała lista zostanie posortowana. W każdym przejściu największy nieposortowany element „unosi się” do właściwej pozycji. Proces ten trwa do momentu, gdy nie są już potrzebne żadne wymiany, co oznacza, że ​​lista jest w pełni posortowana.

Chociaż sortowanie bąbelkowe skutecznie sortuje listę, należy pamiętać, że jego złożoność czasowa sprawia, że ​​jest mniej wydajna w przypadku dużych zbiorów danych w porównaniu z innymi algorytmami sortowania, takimi jak sortowanie przez scalanie lub sortowanie szybkie.

Złożoność czasowa sortowania bąbelkowego

Zrozumienie złożoności czasowej algorytmu ma kluczowe znaczenie dla oceny jego efektywności, szczególnie w przypadku dużych zbiorów danych. Złożoność czasowa sortowania bąbelkowego wynosi w najgorszym przypadku O(n^2), gdzie „n” to liczba elementów na liście.

Rozłóżmy analizę złożoności czasowej:

• Zewnętrzna pętla działa dla „n” iteracji, gdzie „n” to liczba elementów na liście.
• W najgorszym przypadku pętla wewnętrzna również wykonuje „n” iteracji. Jednak w miarę postępu algorytmu liczba iteracji w pętli wewnętrznej maleje, ponieważ w każdym przejściu największy nieposortowany element jest umieszczany na właściwym miejscu.
• W najgorszym przypadku liczba porównań i zamian jest proporcjonalna do kwadratu liczby elementów na liście, co daje złożoność czasową O(n^2). To sprawia, że ​​sortowanie bąbelkowe jest nieefektywne w przypadku dużych zbiorów danych, a w rzeczywistych zastosowaniach często preferowane są bardziej zaawansowane algorytmy sortowania o większej złożoności czasowej.

Wniosek

W tym artykule omówiliśmy koncepcję sortowania bąbelkowego, prostego algorytmu sortowania, który wielokrotnie porównuje i zamienia sąsiadujące elementy, aż do posortowania całej listy. Udostępniliśmy implementację sortowania bąbelkowego w języku Python, uruchomiliśmy ją z przykładową listą i przeanalizowaliśmy wyniki. Dodatkowo omówiliśmy złożoność czasową sortowania bąbelkowego, podkreślając jego złożoność czasową w najgorszym przypadku O(n^2) i jej konsekwencje dla wydajności.