Wprowadzenie do algorytmów szybkiego sortowania w Javie
Szybkie sortowanie w Javie, znane również jako sortowanie według podziału partycji, jest algorytmem dzielenia i zdobywania. Szybkie sortowanie jest dobrym przykładem algorytmu, który najlepiej wykorzystuje pamięci podręczne procesora, ze względu na jego podział i podbój natury. Algorytm Quicksort jest jednym z najczęściej używanych algorytmów sortowania, szczególnie do sortowania dużych list, a większość języków programowania go zaimplementowała. W algorytmie Quicksort oryginalne dane są dzielone na dwie części, które są indywidualnie sortowane, a następnie łączone w celu uzyskania posortowanych danych.
Rozważmy, że tablica (8, 6, 3, 4, 9, 2, 1, 7) musi zostać posortowana za pomocą szybkiego sortowania.
Kroki wdrażania algorytmów szybkiego sortowania
1. Wybierz element o nazwie pivot z tablicy. Zasadniczo środkowy element jest wybierany jako oś obrotu. Weźmy 4 za oś.
2. Zmień układ tablicy na dwie części, tak aby elementy mniejsze niż oś obrotu znajdowały się przed osią obrotu, a elementy większe niż oś obrotu pojawiły się po osi obrotu. Wykonano następujące kroki:
- Wybierz skrajnie lewy element, tj. 8, ponieważ 4 to oś obrotu, a 8 to więcej niż 4, 8 należy przesunąć na prawo od 4, po prawej stronie zostawiamy 7, ponieważ jest on większy niż 4 i wybieramy 1 do zamiany z 8 stąd po zamianie tablica staje się: 1, 6, 3, 4, 9, 2, 8, 7
- Wybierz następny lewy element, tj. 6, ponieważ 4 to oś obrotu, a 6 to więcej niż 4, 6 należy przesunąć na prawo od 4, po prawej stronie pozostawiamy 7, 8, ponieważ są większe niż 4 i wybieramy 2 za zamianę z 6 stąd po zamianie tablica staje się: 1, 2, 3, 4, 9, 6, 8, 7
- Teraz, ponieważ wszystkie elementy po lewej stronie osi obrotu są mniejsze niż oś obrotu, a wszystkie elementy po prawej stronie osi obrotu są większe niż oś obrotu, otrzymujemy 4 jako oś obrotu.
3. Rekurencyjnie zastosuj kroki 1 i 2 dla lewej pod-tablicy (tablica z elementami mniejszymi niż oś) i dla prawej pod-tablicy (tablica z elementami więcej niż oś). Jeśli tablica zawiera tylko jeden lub zero elementów, wówczas tablica jest uważana za dobraną.
Program do implementacji algorytmów szybkiego sortowania
Oto program Java do sortowania tablicy liczb całkowitych przy użyciu algorytmu szybkiego sortowania.
Kod:
import java.lang.*;
import java.util.*;
public class Main (
private int array();
private int length;
public void sort(int() inputArrayArr) (
if (inputArrayArr == null || inputArrayArr.length == 0) (
return;
)
this.array = inputArrayArr;
length = inputArrayArr.length;
performQuickSort(0, length - 1);
)
private void performQuickSort(int lowerIndex, int higherIndex) (
int i = lowerIndex;
int j = higherIndex;
// calculate pivot number
// middle element taken as pivot
int pivot = array(lowerIndex+(higherIndex-lowerIndex)/2);
// Divide into two subarrays
while (i <= j) (
/**
* In each iteration, find an element from left side of the pivot which
* is greater than the pivot value, and also find an element
* From right side of the pivot which is less than the pivot value. Once the search
* is complete, we exchange both elements.
*/
while (array(i) < pivot) (
i++;
)
while (array(j) > pivot) (
j--;
)
if (i <= j) (
swapNumbers(i, j);
//move index to next position on both sides
i++;
j--;
)
)
// call performQuickSort() method recursively
if (lowerIndex < j)
performQuickSort(lowerIndex, j);
if (i < higherIndex)
performQuickSort(i, higherIndex);
)
private void swapNumbers(int i, int j) (
int temp = array(i);
array(i) = array(j);
array(j) = temp;
)
public static void main(String args())(
Main quickSort = new Main();
int() inputArray = (8, 6, 3, 4, 9, 2, 1, 7);
quickSort.sort(inputArray);
System.out.println("Sorted Array " + Arrays.toString(inputArray));
)
)
Wynik:
Zalety algorytmów szybkiego sortowania
Oto zalety algorytmu szybkiego sortowania:
- Doskonała lokalizacja odniesienia: Lokalizacją odniesienia jest zdolność procesora do powtarzalnego uzyskiwania dostępu do tej samej lokalizacji pamięci w krótkim okresie czasu. Szybkie sortowanie w Javie zapewnia doskonałą lokalizację odwołania ze względu na bardzo małą liczbę braków pamięci podręcznej, co w nowoczesnych architekturach ma kluczowe znaczenie dla wydajności.
- Szybkie sortowanie jest możliwe do zrównoleglenia: po ukończeniu wstępnego etapu dzielenia tablicy na mniejsze regiony, wszystkie pojedyncze pod-tablice można sortować niezależnie równolegle. Z tego powodu szybkie sortowanie działa lepiej.
Analiza złożoności szybkiego sortowania
Quicksort to szybki i rekurencyjny algorytm działający według zasady dziel i zwyciężaj. Oto jego analiza złożoności w najlepszym, średnim i najgorszym przypadku:
- Najlepsza złożoność przypadku : jeśli tablica lub lista zawiera n elementów, to pierwsze uruchomienie będzie wymagało O (n). Teraz sortowanie pozostałych dwóch podrzędnych zajmuje 2 * O (n / 2). To kończy złożoność O (n logn) w najlepszym przypadku.
- Średnia złożoność przypadku: średni przypadek szybkiego sortowania wynosi O (n log n).
- Złożoność najgorszego przypadku: wybranie pierwszego lub ostatniego spowodowałoby najmniejszą wydajność w przypadku prawie posortowanych lub prawie odwróconych danych. Szybkie sortowanie wykonuje O (n 2) w najgorszym przypadku.
W Javie Tablice. Metoda sort () wykorzystuje algorytm szybkiego sortowania do sortowania tablicy.
Polecane artykuły
Jest to przewodnik po szybkich algorytmach sortowania w Javie. Tutaj omawiamy kroki do wdrożenia, zalety i analizę złożoności algorytmu szybkiego sortowania w Javie wraz z programem. Możesz także przejrzeć następujące artykuły, aby dowiedzieć się więcej -
- Sortowanie według wstawiania w Javie
- pętla do-while w Javie
- JComponent w Javie
- Kwadraty w Javie
- Zamiana w PHP
- Sortowanie w C #
- Sortowanie w Pythonie
- Algorytm C ++ | Przykłady algorytmu C ++