Wprowadzenie do szybkiego sortowania w Javie
Poniższy artykuł Szybkie sortowanie w Javie zawiera zarys algorytmu szybkiego sortowania w Javie. Algorytm szybkiego sortowania jest jednym z algorytmów sortowania, który jest wydajny i podobny do algorytmu sortowania po scaleniu. Jest to jeden z najczęściej używanych algorytmów do sortowania w czasie rzeczywistym. Złożoność tego algorytmu w najgorszym przypadku to O (n 2), złożoność w średnim czasie to O (n log n), a złożoność w najlepszym przypadku to O (n log n).
Złożoność przestrzeni, jeśli O (n log n) gdzie n jest rozmiarem danych wejściowych. Proces sortowania obejmuje dzielenie danych wejściowych, iteracje rekurencyjne i oznaczanie kluczowego elementu dla każdej rekurencji. Rodzaj sortowania w tym algorytmie obejmuje iteracyjne porównanie sąsiednich elementów.
Jak działa Szybkie sortowanie w Javie?
Algorytm szybkiego sortowania można zaimplementować w Javie, tworząc pseudo kod z sekwencją kroków zaprojektowanych i wykonanych w efektywny sposób.
- Główna zasada działania algorytmu szybkiego sortowania opiera się na podejściu dziel i zwyciężaj, a także jest wydajnym algorytmem sortowania.
- Tablica wejściowa jest podzielona na pod-tablice, a podział oparty jest na elemencie przestawnym, który jest elementem centralnym. Pod-tablice po obu stronach elementu przestawnego są głównymi obszarami, w których faktycznie odbywa się sortowanie.
- Centralny element przestawny jest podstawą do podzielenia tablicy na dwie przegrody, w których lewa połowa elementów tablicy jest mniejsza niż element pivot, a prawa połowa elementów tablicy jest większa niż element pivot.
- Przed rozważeniem elementu przestawnego może nim być każdy z elementów tablicy. Zwykle jest to uważane za środkowe, pierwsze lub ostatnie, aby ułatwić zrozumienie. Element przestawny może być losowy z dowolnego elementu tablicy.
- W naszym przykładzie ostatni element tablicy jest uważany za element przestawny, w którym partycjonowanie podtablic rozpoczyna się od prawego końca tablicy.
- Wreszcie element przestawny znajdzie się w swojej rzeczywistej pozycji sortowania po zakończeniu procesu sortowania, gdzie główny proces sortowania leży w logice podziału algorytmu sortowania.
- Wydajność algorytmu zależy od wielkości pod-macierzy i sposobu ich zrównoważenia. Im bardziej pod-tablice są niezrównoważone, tym bardziej złożoność czasu doprowadzi do złożoności w najgorszym przypadku.
- Losowy wybór elementów przestawnych powoduje w wielu przypadkach najlepszą złożoność czasu zamiast wybierania określonych indeksów początkowych, końcowych lub środkowych jako elementów przestawnych.
Przykłady implementacji szybkiego sortowania w Javie
Algorytm QuickSort został zaimplementowany przy użyciu języka programowania Java jak poniżej, a kod wyjściowy został wyświetlony pod kodem.
- Kod początkowo pobiera dane wejściowe za pomocą metody quickSortAlgo () z argumentem tablica, indeks początkowy i indeks końcowy, tj. Długość tablicy.
- Po wywołaniu metody quickSortAlgo () sprawdza, czy indeks początkowy jest mniejszy niż indeks końcowy, a następnie wywołuje metodę arrayPartition () w celu uzyskania wartości elementu przestawnego.
- Element podziału zawiera logikę rozmieszczania coraz mniejszych elementów wokół elementu przestawnego w oparciu o wartości elementu.
- Po uzyskaniu indeksu elementu przestawnego po wykonaniu metody partycji metoda quickSortAlgo () jest wywoływana sama przez się rekurencyjnie, dopóki wszystkie pod-tablice nie zostaną całkowicie podzielone na partycje.
- W logice podziału ostatni element jest przypisany jako element przestawny, a pierwszy element jest porównywany z elementem przestawnym, tj. Ostatni, w którym elementy są zamieniane w zależności od tego, czy są mniejsze, czy większe.
- Ten proces rekurencji ma miejsce, dopóki wszystkie elementy tablicy nie zostaną podzielone na partycje i nie zostaną posortowane, a końcowym wynikiem będzie połączona posortowana tablica.
- Elementy są zamieniane wewnątrz iteracji dla pętli tylko w przypadku, gdy element jest mniejszy lub równy elementowi przestawnemu.
- Po zakończeniu procesu iteracji ostatni element jest zamieniany, tzn. Wartość elementu przestawnego jest przenoszona na lewą stronę, dzięki czemu tworzone są nowe partycje, a ten sam proces powtarza się w formie rekurencji, co powoduje szereg operacji sortowania na różnych możliwych partycjach jako formacja pod-tablic z podanych elementów tablicy.
- Poniższy kod można uruchomić na dowolnym IDE, a dane wyjściowe można zweryfikować, zmieniając wartość tablicy w main () Metoda główna jest używana tylko w celu uzyskania danych wyjściowych w konsoli. W ramach standardów kodowania Java podstawową metodę można usunąć poniżej, a także można utworzyć obiekt i wywołać poniższe metody, czyniąc je niestatycznymi.
Implementacja kodu algorytmu szybkiego sortowania w Javie
/*
* Quick Sort algorithm - Divide & Conquer approach
*/
public class QuickSortAlgorithm (
public static void main(String() args) (
int() array = ( 99, 31, 1, 3, 5, 561, 1, 342, 345, 454 );
quickSortAlgo(array, 0, array.length - 1);
for (int ar : array) (
System.out.print(ar + " ");
)
)
public static int arrayPartition(int() array, int start, int end) (
int pivot = array(end);
int i = (start - 1);
for (int ele = start; ele < end; ele++) (
if (array(ele) <= pivot) (
i++;
int swap = array(i);
array(i) = array(ele);
array(ele) = swap;
)
)
// Swapping the elements
int swap = array(i + 1);
array(i + 1) = array(end);
array(end) = swap;
return i + 1;
)
public static void quickSortAlgo(int() arrayTobeSorted, int start, int end) (
if (start < end) (
int pivot = arrayPartition(arrayTobeSorted, start, end);
quickSortAlgo(arrayTobeSorted, start, pivot - 1);
quickSortAlgo(arrayTobeSorted, pivot + 1, end);
)
)
)
Wynik:
Wniosek
Algorytm szybkiego sortowania jest wydajny, ale niezbyt stabilny w porównaniu do innych technik sortowania. Wydajność algorytmów szybkiego sortowania spada w przypadku większej liczby powtarzających się elementów, co jest wadą. Złożoność przestrzeni jest zoptymalizowana w tym algorytmie szybkiego sortowania.
Polecane artykuły
Jest to przewodnik po Szybkim sortowaniu w Javie. Tutaj omawiamy działanie szybkiego sortowania w Javie wraz z przykładem i implementacją kodu. Możesz także przejrzeć nasze inne sugerowane artykuły, aby dowiedzieć się więcej -
- Sortuj sterty w Javie
- Co to jest drzewo binarne w Javie?
- Bit Manipulation w Javie
- Omówienie sortowania scalonego w JavaScript
- Omówienie szybkiego sortowania w JavaScript
- Sortuj sterty w Pythonie
- Top 6 algorytm sortowania w JavaScript