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
- Przejdź przez całą tablicę
- Porównaj każdy element z jego następnikiem.
- Jeśli bieżący element jest większy niż następny, zamień je miejscami.
- 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