Implementacja algorytmu Quicksort w Javie

1. Przegląd

W tym samouczku szczegółowo omówimy algorytm QuickSort, koncentrując się na jego implementacji w języku Java.

Omówimy również jego zalety i wady, a następnie przeanalizujemy jego złożoność czasową.

2. Algorytm QuickSort

Quicksort to algorytm sortowania, który wykorzystuje zasadę dziel i rządź. Ma średnią złożoność O (n log n) i jest jednym z najczęściej używanych algorytmów sortowania, szczególnie w przypadku dużych ilości danych.

Należy pamiętać, że Quicksort nie jest stabilnym algorytmem. Stabilny algorytm sortowania to algorytm, w którym elementy o tych samych wartościach pojawiają się w posortowanym wyniku w tej samej kolejności, w jakiej pojawiają się na liście wejściowej.

Lista wejściowa jest podzielona na dwie listy podrzędne za pomocą elementu o nazwie pivot; jedna podlista z elementami mniejszymi niż pivot i druga z elementami większymi niż pivot. Ten proces jest powtarzany dla każdej listy podrzędnej.

Na koniec wszystkie posortowane listy podrzędne łączą się, tworząc ostateczny wynik.

2.1. Kroki algorytmu

  1. Wybieramy z listy element o nazwie pivot. Użyjemy go do podzielenia listy na dwie listy podrzędne.
  2. Zmieniamy kolejność wszystkich elementów wokół pivota - te o mniejszej wartości są umieszczane przed nim, a wszystkie elementy większe niż pivot po nim. Po tym kroku oś znajduje się w ostatecznej pozycji. To jest ważny krok partycji.
  3. Powyższe kroki stosujemy rekurencyjnie do obu list podrzędnych po lewej i prawej stronie osi.

Jak widać, quicksort jest naturalnie algorytmem rekurencyjnym, podobnie jak każde podejście typu dziel i zwyciężaj.

Weźmy prosty przykład, aby lepiej zrozumieć ten algorytm.

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Załóżmy, że dla uproszczenia wybierzemy 5 jako punkt zwrotny
  2. Najpierw umieścimy wszystkie elementy mniejsze niż 5 na pierwszej pozycji tablicy: {3, 4, 5, 6, 5, 9}
  3. Następnie powtórzymy to dla lewej podtablicy {3,4}, przyjmując 3 jako oś obrotu
  4. Nie ma elementów mniejszych niż 3
  5. Stosujemy szybkie sortowanie na podtablicy po prawej stronie osi, tj. {4}
  6. Ta podtablica składa się tylko z jednego posortowanego elementu
  7. Kontynuujemy pracę z prawą częścią oryginalnej tablicy, {6, 5, 9}, aż otrzymamy ostateczną uporządkowaną tablicę

2.2. Wybór optymalnego obrotu

Kluczową kwestią w QuickSort jest wybranie najlepszego obrotu. Środkowy element jest oczywiście najlepszy, ponieważ podzieliłby listę na dwie równe podlisty.

Jednak znalezienie środkowego elementu z nieuporządkowanej listy jest trudne i czasochłonne, dlatego za punkt obrotowy przyjmujemy pierwszy element, ostatni element, medianę lub inny element losowy.

3. Implementacja w Javie

Pierwsza metoda to quickSort (), która przyjmuje jako parametry tablicę do sortowania, pierwszy i ostatni indeks. Najpierw sprawdzamy indeksy i kontynuujemy tylko wtedy, gdy są jeszcze elementy do posortowania.

Uzyskujemy indeks posortowanego pivota i używamy go do rekurencyjnego wywołania metody partition () z tymi samymi parametrami, co metoda quickSort () , ale z różnymi indeksami:

public void quickSort(int arr[], int begin, int end) { if (begin < end) { int partitionIndex = partition(arr, begin, end); quickSort(arr, begin, partitionIndex-1); quickSort(arr, partitionIndex+1, end); } }

Kontynuujmy metodę partition () . Dla uproszczenia ta funkcja przyjmuje ostatni element jako oś. Następnie sprawdza każdy element i zamienia go przed przestawieniem, jeśli jego wartość jest mniejsza.

Pod koniec podziału wszystkie elementy poniżej osi znajdują się po jego lewej stronie, a wszystkie elementy większe od osi po prawej stronie. Oś obrotu znajduje się w ostatecznej posortowanej pozycji, a funkcja zwraca tę pozycję:

private 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; }

4. Analiza algorytmów

4.1. Złożoność czasowa

In the best case, the algorithm will divide the list into two equal size sub-lists. So, the first iteration of the full n-sized list needs O(n). Sorting the remaining two sub-lists with n/2 elements takes 2*O(n/2) each. As a result, the QuickSort algorithm has the complexity of O(n log n).

In the worst case, the algorithm will select only one element in each iteration, so O(n) + O(n-1) + … + O(1), which is equal to O(n2).

On the average QuickSort has O(n log n) complexity, making it suitable for big data volumes.

4.2. QuickSort vs MergeSort

Let's discuss in which cases we should choose QuickSort over MergeSort.

Although both Quicksort and Mergesort have an average time complexity of O(n log n), Quicksort is the preferred algorithm, as it has an O(log(n)) space complexity. Mergesort, on the other hand, requires O(n) extra storage, which makes it quite expensive for arrays.

Quicksort requires to access different indices for its operations, but this access is not directly possible in linked lists, as there are no continuous blocks; therefore to access an element we have to iterate through each node from the beginning of the linked list. Also, Mergesort is implemented without extra space for LinkedLists.

In such case, overhead increases for Quicksort and Mergesort is generally preferred.

5. Conclusion

Quicksort to elegancki algorytm sortowania, który jest bardzo przydatny w większości przypadków.

Zwykle jest to algorytm „na miejscu”, ze średnią złożonością czasową O (n log n).

Innym interesującym punktem, o którym należy wspomnieć, jest to, że metoda Arrays.sort () języka Java używa funkcji Quicksort do sortowania tablic prymitywów. Implementacja wykorzystuje dwa pivoty i działa znacznie lepiej niż nasze proste rozwiązanie, dlatego w przypadku kodu produkcyjnego zwykle lepiej jest używać metod bibliotecznych.

Jak zawsze kod do implementacji tego algorytmu można znaleźć w naszym repozytorium GitHub.