quicksort java algorithm
Ten samouczek wyjaśnia algorytm QuickSort w Javie, jego ilustracje, implementację QuickSort w Javie z pomocą przykładów kodu:
Technika sortowania Quicksort jest szeroko stosowana w aplikacjach. Quicksort wykorzystuje strategię dziel i rządź, taką jak sortowanie przez scalanie.
W algorytmie quicksort najpierw wybierany jest specjalny element o nazwie „pivot”, a tablica lub lista, o której mowa, jest dzielona na dwa podzbiory. Podzbiory podzielone na partycje mogą, ale nie muszą, mieć taki sam rozmiar.
=> Przeczytaj serię szkoleń Easy Java.
Przegrody są takie, że wszystkie elementy mniejsze niż element obrotowy znajdują się po lewej stronie czopa, a elementy większe niż czop znajdują się po prawej stronie czopa. Funkcja Quicksort rekurencyjnie sortuje dwie listy podrzędne. Quicksort działa wydajnie, a także szybciej, nawet w przypadku większych tablic lub list.
Czego się nauczysz:
- Quicksort Partition Java
- Quicksort Algorithm Java
- Pseudokod do szybkiego sortowania
- Ilustracja
- Implementacja Quicksort w Javie
- Często Zadawane Pytania
- Wniosek
- rekomendowane lektury
Quicksort Partition Java
Partycjonowanie jest kluczowym procesem w technice Quicksort. Więc co to jest partycjonowanie?
Mając tablicę A, wybieramy wartość x zwaną pivot taką, że wszystkie elementy mniejsze niż x znajdują się przed x, a wszystkie elementy większe niż x są po x.
bąbelkowy kod sortowania c ++
Wartość obrotu może być dowolną z następujących wartości:
- Pierwszy element w tablicy
- Ostatni element w tablicy
- Środkowy element tablicy
- Dowolny losowy element w tablicy
Ta wartość obrotu jest następnie umieszczana w odpowiednim miejscu w tablicy przez podzielenie tablicy. Zatem wynikiem procesu „podziału” jest wartość obrotu w odpowiednim położeniu oraz elementy mniejsze niż obroty po lewej stronie i elementy większe niż obroty po prawej stronie.
Rozważ poniższy diagram, który wyjaśnia proces partycjonowania.
Powyższy diagram przedstawia proces partycjonowania tablicy poprzez wielokrotne wybieranie ostatniego elementu tablicy jako przestawnej. Na każdym poziomie zwróć uwagę, że dzielimy tablicę na dwie pod-tablice, umieszczając oś obrotu we właściwej pozycji.
Następnie podajemy algorytm i pseudokod dla techniki quicksort, która obejmuje również procedurę partycjonowania.
Quicksort Algorithm Java
Ogólny algorytm szybkiego sortowania jest podany poniżej.
quicksort(Arr, low, high) begin Declare array Arr[N] to be sorted low = 1st element; high = last element; pivot if(low Poniżej podano pseudokod dla techniki quicksort.
Pseudokod do szybkiego sortowania
Poniżej znajduje się pseudokod do techniki szybkiego sortowania. Zauważ, że udostępniliśmy pseudokod dla procedury szybkiego sortowania i partycjonowania.
//pseudocode for quick sort main algorithm procedure quickSort(arr[], low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low Ilustracja
Zobaczmy ilustrację algorytmu szybkiego sortowania. Weź następującą tablicę jako przykład. Tutaj wybraliśmy ostatni element jako pivot.
Jak pokazano, pierwszy element jest oznaczony jako niski, a ostatni element jest wysoki.
Jak widać na powyższej ilustracji, istnieją dwa wskaźniki, wysoki i niski, które wskazują odpowiednio ostatni i pierwszy element tablicy. Oba te wskaźniki są przesuwane wraz z postępem szybkiego sortowania.
Gdy element wskazywany przez dolną wskazówkę staje się większy niż element obrotowy, a element wskazywany przez górną wskazówkę jest mniejszy niż element obracany, wymieniamy elementy wskazywane przez dolną i górną wskazówkę, a każdy wskaźnik przesuwa się o 1 pozycję.
Powyższe kroki są wykonywane, dopóki oba wskaźniki nie przecinają się w tablicy. Po ich przecięciu element pivot przyjmuje właściwą pozycję w tablicy. W tym momencie tablica jest podzielona na partycje i teraz możemy sortować każdą pod-tablicę niezależnie, rekurencyjnie stosując algorytm szybkiego sortowania do każdej z pod-macierzy.
Implementacja Quicksort w Javie
Technikę QuickSort można zaimplementować w Javie przy użyciu rekursji lub iteracji. W tej sekcji zobaczymy obie te techniki.
Rekurencyjne szybkie sortowanie
Wiemy, że podstawowa technika szybkiego sortowania zilustrowana powyżej wykorzystuje rekursję do sortowania tablicy. W rekursywnym sortowaniu szybkim po podzieleniu tablicy, procedura szybkiego sortowania jest wywoływana rekurencyjnie w celu posortowania tablic podrzędnych.
Poniższa implementacja przedstawia technikę szybkiego sortowania wykorzystującą rekursję.
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray[], int low, int high) { int pi = intArray[high]; int i = (low-1); // smaller element index for (int j=low; j Wynik:
Oryginalna tablica: [4, -1, 6, 8, 0, 5, -3]
Posortowana tablica: [-3, -1, 0, 4, 5, 6, 8]
Iteracyjne szybkie sortowanie
W iteracyjnym quicksort używamy pomocniczego stosu do umieszczania parametrów pośrednich zamiast rekurencji i sortowania partycji.
Poniższy program Java implementuje iteracyjne szybkie sortowanie.
import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray[], int low, int high) { int pivot = numArray[high]; // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray[j] <= pivot) { i++; // swap the elements int temp = numArray[i]; numArray[i] = numArray[j]; numArray[j] = temp; } } // swap numArray[i+1] and numArray[high] (or pivot) int temp = numArray[i + 1]; numArray[i + 1] = numArray[high]; numArray[high] = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray[], int low, int high) { //auxillary stack int[] intStack = new int[high - low + 1]; // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack[++top] = low; intStack[++top] = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack[top--]; low = intStack[top--]; // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack[++top] = low; intStack[++top] = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1 Wynik:
Oryginalna tablica: [3, 2, 6, -1, 9, 1, -6, 10, 5]
Posortowana tablica: [- 6, -1, 1, 2, 3, 6, 9, 10, 5]
kod c ++ drzewa binarnego
Często Zadawane Pytania
P # 1) Jak działa Quicksort?
Odpowiedź: Quicksort stosuje strategię dzielenia i zwycięstwa. Quicksort najpierw dzieli tablicę wokół wybranego elementu przestawnego i generuje pod-tablice, które są sortowane rekurencyjnie.
P # 2) Jaka jest złożoność czasowa Quicksort?
Odpowiedź: Złożoność czasowa szybkiego sortowania wynosi średnio O (nlogn). W najgorszym przypadku jest to O (n ^ 2) to samo, co sortowanie przez wybór.
P # 3) Gdzie jest używany Quicksort?
Odpowiedź: Quicksort jest najczęściej używany w aplikacjach rekurencyjnych. Quicksort jest częścią biblioteki C. Ponadto prawie języki programowania, które używają wbudowanego sortowania, implementują quicksort.
P # 4) Jaka jest zaleta Quicksort?
Odpowiedź:
- Quicksort to wydajny algorytm, który z łatwością może posortować nawet ogromną listę elementów.
- Jest to sortowanie na miejscu, dlatego nie wymaga dodatkowej przestrzeni ani pamięci.
- Jest szeroko stosowany i zapewnia skuteczny sposób sortowania zestawów danych o dowolnej długości.
P # 5) Dlaczego szybkie sortowanie jest lepsze niż sortowanie przez scalanie?
Odpowiedź: Głównym powodem, dla którego sortowanie szybkie jest lepsze niż sortowanie przez scalanie, jest to, że sortowanie szybkie jest metodą sortowania na miejscu i nie wymaga dodatkowej pamięci. Sortowanie przez scalanie wymaga dodatkowej pamięci do sortowania pośredniego.
Wniosek
Quicksort jest uważany za najlepszy algorytm sortowania głównie ze względu na jego skuteczność w sortowaniu nawet ogromnych zbiorów danych w czasie O (nlogn).
Quicksort to także sortowanie na miejscu i nie wymaga dodatkowej pamięci. W tym samouczku widzieliśmy rekurencyjną i iteracyjną implementację quicksort.
W naszym nadchodzącym samouczku będziemy kontynuować sortowanie metod w Javie.
=> Zapoznaj się z podręcznikiem Java dla początkujących tutaj.
rekomendowane lektury
- Algorytm wyszukiwania binarnego w Javie - implementacja i przykłady
- Tablica Java - jak wydrukować elementy tablicy w języku Java?
- Sortowanie przez wybór w Javie - Algorytm sortowania przez wybór i przykłady
- Typy danych tablic - int Array, Double array, Array of Strings itp.
- Java Array - Deklaruj, twórz i inicjuj tablicę w Javie
- Samouczek JAVA dla początkujących: ponad 100 praktycznych samouczków wideo Java
- Java Copy Array: Jak skopiować / sklonować tablicę w Javie
- Samouczek dotyczący długości tablicy w języku Java z przykładami kodu
