quicksort java algorithm
Acest tutorial explică algoritmul Quicksort în Java, ilustrațiile sale, implementarea QuickSort în Java cu ajutorul exemplelor de cod:
Tehnica de sortare Quicksort este utilizată pe scară largă în aplicațiile software. Quicksort folosește o strategie de divizare și cucerire, cum ar fi sortarea fuzionării.
În algoritmul quicksort, este selectat mai întâi un element special numit „pivot” și matricea sau lista în cauză este partiționată în două subseturi. Subseturile partiționate pot avea sau nu dimensiuni egale.
=> Citiți seria Easy Training Java.
Partițiile sunt astfel încât toate elementele mai mici decât elementul pivot sunt spre stânga pivotului și elementele mai mari decât pivotul se află în dreapta pivotului. Rutina Quicksort sortează recursiv cele două sub-liste. Quicksort funcționează eficient și, de asemenea, mai rapid, chiar și pentru tablouri sau liste mai mari.
Ce veți învăța:
- Quicksort Partition Java
- Algoritm Quicksort Java
- Pseudocod pentru sortare rapidă
- Ilustrare
- Implementare Quicksort în Java
- întrebări frecvente
- Concluzie
- Lectură recomandată
Quicksort Partition Java
Partiționarea este procesul cheie al tehnicii Quicksort. Deci, ce este partiționarea?
Având în vedere o matrice A, alegem o valoare x numită pivot astfel încât toate elementele mai mici decât x să fie înaintea lui x și toate elementele mai mari decât x să fie după x.
O valoare pivot poate fi oricare dintre următoarele:
- Primul element din matrice
- Ultimul element din matrice
- Elementul de mijloc din matrice
- Orice element aleatoriu din matrice
Această valoare pivot este apoi plasată la poziția corectă în matrice partiționând matricea. Astfel, rezultatul procesului de „partiționare” este valoarea pivotului în poziția corectă și elementele mai mici decât pivotul din stânga și elementele mai mari decât un pivot în dreapta.
Luați în considerare următoarea diagramă care explică procesul de partiționare.
Diagrama de mai sus arată procesul de partiționare a matricei selectând în mod repetat ultimul element din matrice ca pivot. La fiecare nivel, rețineți că partiționăm matricea în două sub-tablouri plasând pivotul în poziția corectă.
Apoi, enumerăm algoritmul și pseudo-codul pentru tehnica quicksort care include și rutina de partiție.
Algoritm Quicksort Java
Algoritmul general pentru quicksort este dat mai jos.
site-uri anime pentru a viziona anime gratuit
quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low Mai jos este pseudo-codul pentru tehnica quicksort.
Pseudocod pentru sortare rapidă
Urmează pseudo-codul pentru o tehnică de sortare rapidă. Rețineți că am furnizat pseudo-codul pentru rutina rapidă și partiționare.
//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 Ilustrare
Să vedem ilustrația algoritmului rapid. Luați ca exemplu următoarea matrice. Aici am selectat ultimul element ca pivot.
După cum se arată, primul element este etichetat scăzut, iar ultimul element este ridicat.
După cum este evident în ilustrația de mai sus, există două indicatoare, înaltă și joasă, care indică respectiv ultimul și primul element al matricei. Ambele indicații sunt mutate pe măsură ce rapidul rapid progresează.
Când elementul indicat de indicatorul de jos devine mai mare decât elementul pivot și elementul indicat de indicatorul înalt este mai mic decât elementul pivot, schimbăm elementele îndreptate de indicatorul de jos și de înalt și fiecare indicator avansează cu 1 poziție.
Etapele de mai sus sunt efectuate până când ambele indicatoare se încrucișează în matrice. Odată ce se încrucișează, elementul pivot își obține poziția corectă în matrice. În acest moment, matricea este partiționată și acum putem sorta fiecare sub-matrice independent aplicând recursiv un algoritm de sortare rapidă la fiecare dintre sub-matrice.
Implementare Quicksort în Java
Tehnica QuickSort poate fi implementată în Java folosind fie recursivitate, fie iterație. În această secțiune, vom vedea ambele tehnici.
Quicksort recursiv
Știm că tehnica de bază a quicksort ilustrată mai sus folosește recursivitatea pentru sortarea matricei. În quicksortul recursiv după partiționarea matricei, rutina quicksort este apelată recursiv pentru a sorta sub-tablourile.
Implementarea de mai jos demonstrează tehnica quicksort folosind recursivitatea.
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 Ieșire:
Matrice originală: (4, -1, 6, 8, 0, 5, -3)
Matrice sortată: (-3, -1, 0, 4, 5, 6, 8)
Iterative Quicksort
În quicksort iterativ, folosim stiva auxiliară pentru a plasa parametrii intermediari în loc să folosim recursie și sortare partiții.
Următorul program Java implementează rapid rapid iterativ.
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 Ieșire:
Matrice originală: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Matrice sortate: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)
întrebări frecvente
Q # 1) Cum funcționează un Quicksort?
Răspuns: Quicksort folosește o strategie de divizare și cucerire. Quicksort prima partiționează o matrice în jurul unui element pivot selectat și generează sub-tablouri care sunt sortate recursiv.
Q # 2) Care este complexitatea timpului Quicksort?
Răspuns: Complexitatea în timp a rapidului rapid în medie este O (nlogn). În cel mai rău caz, este O (n ^ 2) la fel ca sortarea de selecție.
Î # 3) Unde se utilizează Quicksort?
Răspuns: Quicksort este utilizat mai ales în aplicații recursive. Quicksort face parte din biblioteca C. De asemenea, aproape limbajele de programare care utilizează sortarea încorporată implementează quicksort.
Q # 4) Care este avantajul Quicksort?
Răspuns:
- Quicksort este un algoritm eficient și poate sorta cu ușurință chiar și o listă uriașă de elemente.
- Este sortat în loc și, prin urmare, nu are nevoie de spațiu sau memorie suplimentară.
- Este utilizat pe scară largă și oferă un mod eficient de sortare a seturilor de date de orice lungime.
Q # 5) De ce este Quicksort mai bun decât sortarea de îmbinare?
Răspuns: Motivul principal pentru care quicksort este mai bun decât sortarea de îmbinare este că quicksort este o metodă de sortare în loc și nu necesită spațiu de memorie suplimentar. Sortarea Merge necesită memorie suplimentară pentru sortarea intermediară.
Concluzie
Quicksort este considerat cel mai bun algoritm de sortare, în principal datorită eficienței sale de a sorta chiar și un set imens de date în timp O (nlogn).
Quicksort este, de asemenea, un tip de instalare și nu necesită spațiu de memorie suplimentar. În acest tutorial, am văzut implementarea recursivă și iterativă a quicksort.
În viitorul nostru tutorial, vom continua cu metodele de sortare în Java.
=> Consultați aici Ghidul pentru începători Java.
Lectură recomandată
- Algoritm de căutare binară în Java - Implementare și exemple
- Java Array - Cum se imprimă elemente ale unui array în Java?
- Sortare selecție în Java - Algoritm sortare selecție și exemple
- Tipuri de date matrice - matrice int, matrice dublă, matrice de șiruri etc.
- Java Array - Declarați, creați și inițializați o matrice în Java
- Tutorial JAVA pentru începători: peste 100 de tutoriale video Java practice
- Java Copy Array: Cum să copiați / clonați un array în Java
- Tutorial Java Array Length cu exemple de cod
