Sortowanie bąbelkowe

Sortowanie bąbelkowe (ang. bubble sort) to jedna z najprostszych metod sortowania danych w tablicy lub liście. Nazwa tej metody pochodzi od sposobu, w jaki większe elementy "wypływają" na powierzchnię tablicy, podobnie jak bąbelki powietrza w wodzie. Poniżej znajduje się szczegółowy opis metody sortowania bąbelkowego, jej algorytm oraz przykłady.

Metoda sortowania bąbelkowego

Sortowanie bąbelkowe polega na porównywaniu kolejnych par sąsiadujących ze sobą elementów w tablicy i zamienianiu ich miejscami, jeśli są w niewłaściwej kolejności. Proces ten jest powtarzany wielokrotnie, aż do momentu, gdy cała tablica będzie posortowana.

Algorytm sortowania bąbelkowego

  1. Przejdź przez całą tablicę
  2. Porównaj każdy element z jego następnikiem.
  3. Jeśli bieżący element jest większy niż następny, zamień je miejscami.
  4. Powtarzaj kroki powyżej, dopóki nie wykonasz pełnego przejścia przez tablicę bez żadnej zamiany.

Przykład sortowania bąbelkowego

Tablica do posortowania: [5, 3, 8, 4, 2]

Pierwsze przejście algorytmu

  • Porównaj 5 i 3, zamień, wynik [3, 5, 8, 4, 2]
  • Porównaj 5 i 8, bez zmiany, wynik [3, 5, 8, 4, 2]
  • Porównaj 8 i 4, zamień, wynik [3, 5, 4, 8, 2]
  • Porównaj 8 i 2, zamień, wynik [3, 5, 4, 2, 8]

Drugie przejście algorytmu

  • Porównaj 3 i 5, bez zmiany, wynik [3, 5, 4, 2, 8]
  • Porównaj 5 i 4, zamień, wynik [3, 4, 5, 2, 8]
  • Porównaj 5 i 2, zamień, wynik [3, 4, 2, 5, 8]

Po pierwszym przejściu 8 jest już na właściwym miejscu, więc nie musimy jej porównywać i mamy jedno porównanie mniej.

Trzecie przejście algorytmu

  • Porównaj 3 i 4, bez zmiany, wynik [3, 4, 2, 5, 8]
  • Porównaj 4 i 2, zamień, wynik [3, 2, 4, 5, 8]

Po dwóch przejściach 5 i 8 są już na właściwym miejscu, więc nie musimy ich porównywać i mamy 2 porównania mniej.

Czwarte przejście algorytmu

  • Porównaj 3 i 2, zamień, wynik [2, 3, 4, 5, 8]

Pozostałe elementy są już na właściwym miejscu.

Po czterech przejściach tablica 5-elementowa jest posortowana, wynik [2, 3, 4, 5, 8].

Złożoność obliczeniowa algorytmu bąbelkowego

  • w najgorszym przypadku O(n²)
  • w najlepszym przypadku O(n) (wówczas gdy tablica jest już posortowana)
  • średnia złożoność O(n²)

Zalety i wady sortowania bąbelkowego

Zalety

  • łatwe do zrozumienia i zaimplementowania,
  • działa dobrze dla małych tablic.

Wady

  • bardzo nieefektywne dla dużych zbiorów danych,
  • duża liczba porównań i zamian, nawet jeśli tablica jest prawie posortowana.

Implementacja sortowania bąbelkowego w różnych językach programowania

Sortowanie bąbelkowe w języku C++

#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        for (int j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Zamiana miejscami
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
    }
}
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}
int main() {
    int arr[] = {5, 3, 8, 4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << "Nieposortowana tablica: ";
    printArray(arr, n);
    bubbleSort(arr, n);
    cout << "Posortowana tablica: ";
    printArray(arr, n);
    return 0;
}

Sortowanie bąbelkowe w języku Python

def bubble_sort(arr):
    n = len(arr)
    for i in range(n-1):
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                # Zamiana miejscami
                arr[j], arr[j+1] = arr[j+1], arr[j]
def print_array(arr):
    for i in arr:
        print(i, end=" ")
    print()
# Przykładowa tablica
arr = [5, 3, 8, 4, 2]
print("Nieposortowana tablica:", end=" ")
print_array(arr)
bubble_sort(arr)
print("Posortowana tablica:", end=" ")
print_array(arr)

Sortowanie bąbelkowe w języku Java

public class BubbleSort {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = 0; j < n-i-1; j++) {
                if (arr[j] > arr[j+1]) {
                    // Zamiana miejscami
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
    static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 4, 2};
        System.out.println("Nieposortowana tablica:");
        printArray(arr);
        bubbleSort(arr);
        System.out.println("Posortowana tablica:");
        printArray(arr);
    }
}

Sortowanie bąbelkowe w języku JavaScript

function bubbleSort(arr) {
    let n = arr.length;
    for (let i = 0; i < n-1; i++) {
        for (let j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Zamiana miejscami
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
}
function printArray(arr) {
    console.log(arr.join(" "));
}
// Przykładowa tablica
let arr = [5, 3, 8, 4, 2];
console.log("Nieposortowana tablica:");
printArray(arr);
bubbleSort(arr);
console.log("Posortowana tablica:");
printArray(arr);

Wyjaśnienia powyższych kodów

Język C++

Funkcja bubbleSort przyjmuje tablicę arr oraz jej długość n. Przechodzi przez tablicę, porównując kolejne pary elementów i zamieniając je, jeśli są w niewłaściwej kolejności. Funkcja printArray służy do wyświetlania elementów tablicy. W main tworzymy przykładową tablicę, wyświetlamy ją przed i po sortowaniu.

Język Python

Funkcja bubble_sort działa podobnie jak w C++. Przechodzi przez listę arr, porównując i zamieniając elementy, jeśli są w niewłaściwej kolejności. Funkcja print_array służy do wyświetlania elementów listy. Tworzymy przykładową listę, wyświetlamy ją przed i po sortowaniu.

Język Java

Klasa BubbleSort zawiera metodę bubbleSort, która sortuje tablicę arr oraz metodę printArray do wyświetlania tablicy. W metodzie main tworzona jest przykładowa tablica, która jest wyświetlana przed i po sortowaniu.

Język JavaScript

Funkcja bubbleSort przyjmuje tablicę arr i sortuje ją. Funkcja printArray wyświetla elementy tablicy jako ciąg znaków. Przykładowa tablica jest sortowana i wyświetlana przed i po sortowaniu.

Wszystkie ww. implementacje działają zgodnie z opisanym wcześniej algorytmem sortowania bąbelkowego. Sortowanie bąbelkowe, mimo swoich ograniczeń, jest często używane jako przykład do nauki podstaw algorytmów sortowania i ich analizy.

Komentarze