Sortowanie bąbelkowe – Bubble Sort

Sortowanie bąbelkowe (ang. Bubble Sort) – „4,23,2,11,12,3,54” – ile zajmie Ci uporządkowanie tych kilku liczb? A co gdyby było ich sto albo tysiąc? Już na samą myśl układania tego „ręcznie” kręci mi się w głowie 🤯

Po co się jednak przemęczać skoro istnieją już „gotowe” rozwiązania sortowania?

Jednym z najprostszych i najbardziej znanych algorytmów sortowania jest Bubble Sort, czyli sortowanie bąbelkowe. Dlatego warto bliżej się mu przyjrzeć 🧐

Sortowanie bąbelkowe – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest sortowanie?
• Na czym polega sortowanie bąbelkowe?
• Jaka jest historia Bubble Sort?
• Kiedy stosować sortowanie bąbelkowe?
• Jak zaimplementować algorytm Bubble Sort?

Sortowanie

Sortowanie to po prostu uporządkowanie zbioru danych względem pewnych cech charakterystycznych elementów w zbiorze. Istnieją różne algorytmy sortowania, które w zależności od potrzeb, można zastosować, chcąc posortować elementy w kolekcji.

Algorytm sortowania (ang. Sorting Algorithm)

Algorytm sortowania to algorytm, który umieszcza elementy listy lub tablicy w określonej kolejności – zwykle w porządku numerycznym lub leksykograficznym. Istnieje wiele dostępnych algorytmów sortowania, z których każdy ma swoje zalety i wady pod względem wydajności, prostoty i wykorzystania pamięci.

Jeżeli dopiero stawiasz swoje pierwsze kroki w programowaniu, to zapraszam do naszego darmowego kursu Java:

➡ ZOBACZ 👉: Kurs Java | Darmowy Kurs Programowania w Javie

Jeżeli natomiast myślisz o pracy jako programista i chcesz zostać Junior Developerem, zobacz ten materiał:

➡ ZOBACZ 👉: Młodszy programista (Junior developer) – jak zostać?, CV, zarobki, praca

Sortowanie bąbelkowe (ang. Bubble Sort)

Sortowanie bąbelkowe polega na wielokrotnym przejściu przez listę, podczas którego porównujemy sąsiadujące elementy kolekcji i zamieniamy ich pozycje, jeśli znajdują się w złej kolejności. Ten algorytm sortowania otrzymał swoją nazwę od sposobu, w jaki mniejsze elementy „bąbelkują” na górze listy, gdy większe elementy „toną” na dole.

Sortowanie bąbelkowe – Historia

Sortowanie bąbelkowe uważane jest za jeden z najstarszych algorytmów sortowania.
Po raz pierwszy został opisany przez Johna W. Mauchly’ego i J. Prespera Eckerta w 1949 roku, jako część projektu komputera ENIAC.
Sortowanie bąbelkowe było czasami określane jako „sortowanie tonące”.

Sortowanie bąbelkowe – Kiedy stosować?

• Sortowanie bąbelkowe jest jednym z prostszych do zrozumienia i wdrożenia algorytmów sortowania.
• Ze względu na swoją prostotę, sortowanie bąbelkowe jest często używane podczas nauki, do wprowadzenia pojęcia algorytmu, lub algorytmu sortowania.
• Działa dobrze, gdy wejściowa kolekcja jest mała i prawie posortowana. W takich przypadkach może być szybszy niż bardziej złożone algorytmy sortowania.
• Ze względu na jego złożoność czasową O(n^2), może być powolny i nieefektywny dla dużych list lub tablic i zazwyczaj nie jest używany w kodzie produkcyjnym.
• W przypadku dużych kolekcji lepiej sprawdzą się inne bardziej wydajne algorytmy sortowania, takie jak Quick Sort, Merge Sort lub Heap Sort – zwykle są preferowane w takich przypadkach.

➡ ZOBACZ 👉: Sortowanie szybkie – Quick Sort
➡ ZOBACZ 👉: Sortowanie przez wstawianie, Insertion Sort

Sortowanie bąbelkowe (ang. Bubble Sort) – Java

public class BubbleSort {

	public static void sort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			for (int j = 0; j < arr.length - i - 1; j++) {
				if (arr[j] < arr[j + 1]) {
					swap(arr, j, j + 1);
				}
			}
		}
	}

private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
}

W powyższym kodzie zapętlamy tablicę i porównujemy sąsiadujące elementy.
Zwróć uwagę, że stosuję 2 zagnieżdżone pętlę for. Pętla zewnętrzna biegnie od pierwszego elementu do przedostatniego, natomiast pętla wewnętrzna od pierwszego elementu do przedostatniego elementu nieposortowanej części tablicy.
Jeśli elementy nie są ustawione w odpowiedniej kolejności, wywołujemy metodę swap, aby zamienić ich pozycje.
Metoda swap pobiera tablicę oraz indeksy dwóch elementów, które mają zostać zamienione i używa zmiennej tymczasowej temp do wykonania zamiany.

Sortowanie bąbelkowe – Podsumowanie

Sortowanie bąbelkowe to prosty i intuicyjny algorytm sortowania, który działa poprzez wielokrotne zamienianie sąsiednich elementów w tablicy.

Dzięki swojej prostocie jest to świetny algorytm do stawiania pierwszych kroków w tematyce samych algorytmów, jak i algorytmów sortowania.