Sortowanie szybkie – Quick Sort

Sortowanie szybkie (ang. Quick Sort) – jest jednym z najpopularniejszych i najbardziej efektywnych algorytmów sortowania. Dowiesz się, dlaczego Quick Sort jest tak ważny, jak działa oraz kiedy warto go stosować.

Java – Quick Sort – wprowadzenie

Z tego materiału dowiesz się:

• Czym jest Quick Sort?
• Jak działa Quick Sort?
• Jak zaimplementować algorytm Quick Sort?
• Jakie są zalety i wady Quick Sort?
• Jak Java korzysta z algorytmu Quick Sort?

Quick Sort – Sortowanie szybkie

Quick Sort wykorzystuje prostą, ale potężną koncepcję. Algorytm dzieli zestaw danych na mniejsze podzbiory, sortuje każdy z nich i łączy wyniki w jedną uporządkowaną całość. Należy jednak pamiętać, że Quick Sort nie jest stabilnym algorytmem sortowania. Oznacza to, że elementy o tych samych wartościach mogą zmienić swoją względną kolejność w wynikowym zbiorze (wrócimy do tego tematu jeszcze za chwilę).

Quick Sort – Zasada działania

Idea „dziel i zwyciężaj” polega na podziale problemu na mniejsze podproblemy, rozwiązaniu ich i połączeniu wyników w rozwiązanie ogólnego problemu. W przypadku Quick Sort oznacza to wybór elementu jako „pivot” (punkt odniesienia), podział zbioru danych na dwie grupy (mniejsze i większe od „pivota”), sortowanie tych dwóch grup i łączenie ich w jedną, uporządkowaną listę.

Algorytm Quick Sort

Przedstawiony poniżej algorytm sortuje liczby całkowite dostarczone w tablicy.

static void quickSort(int[] arr) {
	if (arr == null || arr.length == 0) {
		return;
	}

	int high = arr.length - 1;
	quickSort(arr, 0, high);
}

static void quickSort(int[] arr, int begin, int end) {
	if (begin < end) {
		int pivotIndex = partition(arr, begin, end);

		quickSort(arr, begin, pivotIndex - 1);
		quickSort(arr, pivotIndex + 1, end);
	}
}

static int partition(int[] arr, int begin, int end) {
	int pivot = arr[end];
	int i = (begin - 1);

	for (int j = begin; j < end; j++) {
		if (arr[j] <= pivot) {
			i++;

			int swapTemp = arr[i];
			arr[i] = arr[j];
			arr[j] = swapTemp;
		}
	}

	int swapTemp = arr[i + 1];
	arr[i + 1] = arr[end];
	arr[end] = swapTemp;

	return i + 1;
}

1. Metoda quickSort() jest punktem wejściowym dla użytkownika. Sprawdza, czy przekazana tablica nie jest pusta ani nie ma zerowej długości, a następnie wywołuje wersję tej samej metody z dodatkowymi parametrami.
2. Metoda ta implementuje rekurencyjny algorytm Quick Sort.
3. Warunek begin < end oznacza, że podtablica, którą sortujemy, zawiera więcej niż jeden element.
4. Wywołujemy metodę partition(), aby uzyskać indeks osi (pivotIndex), a następnie rekurencyjnie sortujemy dwie podtablice: od begin do pivotIndex -1 i od pivotIndex + 1 do end.
5. Metoda partition() wyznacza indeks osi (pivotIndex) dla danej podtablicy.
6. Używa dwóch wskaźników (i oraz  j), które przemieszczają się w stronę siebie, zamieniając elementy, jeśli są na niewłaściwych miejscach względem osi.
7. Po zakończeniu pętli zwraca indeks, który jest teraz pozycją osi w posortowanej tablicy.

W wyniku tego algorytmu, rekurencyjnie dzieląc i sortując tablicę, wszystkie elementy na lewo od osi będą mniejsze, a te po prawej stronie będą większe. Algorytm kończy działanie, gdy każda podtablica zawiera jeden element lub jest pusta.

➡ ZOBACZ 👉: Rekurencja ➿ rekursja ➿ rekurencja

Zalety i wady Quick Sort

Zalety:

• Optymalna średnia złożoność czasowa: QuickSort ma średnią złożoność czasową O(n log n), co czyni go jednym z najszybszych algorytmów sortowania dla ogólnej klasy problemów. To oznacza, że w większości przypadków, nawet dla dużych zbiorów danych, QuickSort działa wyjątkowo szybko.
• Dobre wykorzystanie pamięci podręcznej: QuickSort wykazuje lepsze wykorzystanie pamięci podręcznej procesora w porównaniu z innymi algorytmami sortowania, takimi jak Merge Sort czy Heap Sort. Dzieje się tak ze względu na lokalność odwołań, która jest wynikiem dzielenia danych na mniejsze podzbiory.
• Skalowalność: QuickSort jest bardzo skalowalny i efektywny dla dużych zbiorów danych. Jego zdolność do szybkiego sortowania dużych ilości danych czyni go użytecznym w zastosowaniach przemysłowych, takich jak bazy danych i systemy przetwarzania transakcji.
• Elastyczność w wyborze pivota: Możliwość wyboru różnych strategii dla wyboru pivota (np. pierwszy element, ostatni element, mediana, losowy element) pozwala na dostosowanie algorytmu do specyficznych wymagań danych wejściowych, co może zwiększać jego wydajność w różnych scenariuszach.
• Dobry do danych rozproszonych: QuickSort jest szczególnie efektywny w przypadku danych, które są rozproszone (nieuporządkowane) lub mają losowy rozkład, ponieważ takie warunki minimalizują ryzyko najgorszego przypadku działania algorytmu (O(n^2)).

Wady:

Pomimo licznych zalet algorytmu QuickSort, ważne jest również zwrócenie uwagi na potencjalne wady, takie jak:

• Problem uporządkowanych danych, czyli najgorszy przypadek złożoności czasowej O(n^2):
  W najgorszym scenariuszu, gdy dane wejściowe są już posortowane lub prawie posortowane (lub w każdym innym przypadku, gdy pivot jest wybierany niefortunnie), złożoność czasowa QuickSorta degraduje do O(n^2). Jest to znacznie mniej wydajne w porównaniu ze średnią złożonością O(n log n). Optymalna sytuacja dla QuickSort występuje, gdy pivot dzieli dane na dwie mniej więcej równe części, co zapewnia efektywność późniejszego sortowania. Jednak w przypadku danych, które są już częściowo lub całkowicie posortowane, wybór pivota może prowadzić do tworzenia bardzo nierównych podziałów. Na przykład, jeśli pivotem zostanie wybrany element z jednego z końców już posortowanego zbioru, jedna z części po podziale może zawierać większość elementów, a druga bardzo niewiele lub żadnych. Taka sytuacja prowadzi do niewydajności, ponieważ algorytm musi wykonać więcej rekurencyjnych wywołań dla większej części, co nie jest optymalne.
• Niestabilność algorytmu sortowania 
  Algorytm sortowania jest określany jako „niestabilny”, gdy kolejność równych elementów wejściowych może ulec zmianie po zastosowaniu algorytmu.
  Innymi słowy, jeśli mamy dwa elementy A i B o tej samej wartości klucza w oryginalnym zestawie danych, a algorytm sortowania zmienia ich wzajemne położenie, mówimy, że jest to algorytm niestabilny.
  W przypadku sortowania liczb całkowitych nie ma to większego znaczenia – liczba 1 jest zawsze liczbą 1 i nie ma znaczenia, czy zapiszemy to jako 11, czy jako 11 😉
  Może to mieć jednak znaczenie, gdy np. sortujemy naszych klientów po nazwisku i np. raz jako pierwszy na liście będzie Jan Kowalski z Gdańska, a innym razem Jan Kowalski z Warszawy.
• Brak gwarancji stałej wydajności: Ponieważ wydajność QuickSorta zależy od danych wejściowych i wyboru pivota, trudno jest zagwarantować stałą wydajność w różnych zastosowaniach. W niektórych przypadkach inne algorytmy sortowania mogą być bardziej przewidywalne i niezawodne.

Quick Sort – Java – Arrays.sort()

Na szczęście w świecie Javy zazwyczaj nie musisz samodzielnie implementować algorytmów sortowania, między innymi dzięki wbudowanej funkcji Array.sort().
Korzysta ona automatycznie z algorytmu Quick Sort, eliminując potrzebę ręcznej implementacji.

➡ ZOBACZ 👉: Arrays – Twój prywatny kombajn do zarządzania tablicami! 🚜👨‍🌾

Java – Quick Sort – Podsumowanie

Sortowanie szybkie, znane jako Quick Sort, to zaawansowany algorytm sortowania, który jest efektywny i przydatny w wielu sytuacjach. Niezależnie od poziomu  Twojego zaawansowania, warto poznać i zrozumieć ten algorytm, aby poszerzyć swoją wiedzę w zakresie algorytmów i sortowania danych.