quicksort java algorithm
millors llocs d'anime per veure l'anime
Aquest tutorial explica l'algorisme Quicksort a Java, les seves il·lustracions, la implementació QuickSort a Java amb l'ajut d'exemples de codi:
La tècnica d’ordenació Quicksort s’utilitza àmpliament en aplicacions de programari. Quicksort utilitza una estratègia de divisió i conquesta com ara la classificació per combinació.
A l'algorisme quicksort, primer es selecciona un element especial anomenat 'pivot' i la matriu o llista en qüestió es divideix en dos subconjunts. Els subconjunts particionats poden tenir o no la mateixa mida.
=> Llegiu la sèrie de formació Java fàcil.
Les particions són tals que tots els elements inferiors a l'element pivot es troben cap a l'esquerra del pivot i els elements més grans que el pivot es troben a la dreta del pivot. La rutina Quicksort ordena recursivament les dues sub-llistes. Quicksort funciona de manera eficient i també més ràpida, fins i tot per a matrius o llistes més grans.
Què aprendreu:
- Quicksort Partition Java
- Quicksort Algorithm Java
- Pseudocodi per ordenació ràpida
- Il·lustració
- Implementació de Quicksort a Java
- Preguntes freqüents
- Conclusió
- Lectura recomanada
Quicksort Partition Java
El particionament és el procés clau de la tècnica Quicksort. Llavors, què és el particionament?
Donada una matriu A, escollim un valor x anomenat pivot tal que tots els elements menors de x siguin anteriors a x i tots els elements majors de x siguin posteriors a x.
Un valor pivot pot ser qualsevol dels següents:
- El primer element de la matriu
- L'últim element de la matriu
- L'element mitjà de la matriu
- Qualsevol element aleatori de la matriu
Aquest valor pivot es col·loca a la seva posició correcta a la matriu particionant la matriu. Per tant, la sortida del procés de 'particionament' és el valor de pivot a la seva posició adequada i els elements inferiors a pivot a l'esquerra i elements més grans que un pivot a la dreta.
Penseu en el diagrama següent que explica el procés de particionament.
El diagrama anterior mostra el procés de partició de la matriu seleccionant repetidament l’últim element de la matriu com a pivot. A cada nivell, tingueu en compte que particionem la matriu en dues sub-matrius col·locant el pivot a la seva posició correcta.
A continuació, llistem l'algoritme i el pseudocodi per a la tècnica quicksort que també inclou la rutina de particions.
Quicksort Algorithm Java
A continuació es mostra l’algorisme general per a quicksort.
quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low A continuació es mostra el pseudocodi per a la tècnica quicksort.
Pseudocodi per ordenació ràpida
A continuació es mostra el pseudocodi d’una tècnica d’ordenació ràpida. Tingueu en compte que hem proporcionat el pseudocodi per a la rutina de particions ràpida i ràpida.
//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 Il·lustració
Vegem la il·lustració de l’algoritme de ràpida velocitat. Agafeu la matriu següent com a exemple. Aquí hem seleccionat l’últim element com a pivot.
Com es mostra, el primer element s’etiqueta baix i l’últim element és alt.
Com és evident a la il·lustració anterior, hi ha dos indicadors, alt i baix, que apunten respectivament a l'últim i primer element de la matriu. Tots dos indicadors es mouen a mesura que avança el ràpid.
Quan l’element apuntat pel punter baix es fa més gran que l’element pivot i l’element apuntat pel punter alt és menor que l’element pivot, intercanviem els elements apuntats pel punter baix i alt i cada punter avança en 1 posició.
Els passos anteriors es duen a terme fins que els dos punteres es creuen a la matriu. Un cop es creuen, l'element pivot obté la seva posició correcta a la matriu. En aquest moment, la matriu està particionada i ara podem ordenar cada subarraia independentment aplicant recursivament un algorisme d'ordenació ràpida a cadascun dels subarrays.
Implementació de Quicksort a Java
La tècnica QuickSort es pot implementar a Java mitjançant recursivitat o iteració. En aquesta secció, veurem aquestes dues tècniques.
Quicksort recursiu
Sabem que la tècnica bàsica del quicksort il·lustrat anteriorment utilitza la recursió per ordenar la matriu. Al quicksort recursiu després de particionar la matriu, la rutina quicksort es diu recursivament per ordenar els sub-arrays.
La implementació següent mostra la tècnica quicksort mitjançant recursivitat.
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 Sortida:
Matriu original: (4, -1, 6, 8, 0, 5, -3)
Matriu ordenada: (-3, -1, 0, 4, 5, 6, 8)
Quicksort iteratiu
A quicksort iteratiu, fem servir la pila auxiliar per col·locar paràmetres intermedis en lloc d’utilitzar particions de recursió i ordenació.
El següent programa Java implementa el quicksort iteratiu.
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 Sortida:
Matriu original: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Matriu ordenada: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)
Preguntes freqüents
P # 1) Com funciona un Quicksort?
Resposta: Quicksort utilitza una estratègia de divisió i conquesta. Quicksort primer particiona una matriu al voltant d’un element pivot seleccionat i genera sub-matrius que s’ordenen recursivament.
Q # 2) Quina és la complexitat horària de Quicksort?
millor convertidor de vídeo gratuït per a Windows
Resposta: La complexitat temporal del quicksort de mitjana és O (nlogn). En el pitjor dels casos, és O (n ^ 2) el mateix que el tipus de selecció.
P # 3) On s'utilitza Quicksort?
Resposta: Quicksort s’utilitza principalment en aplicacions recursives. Quicksort és la part de la biblioteca C. A més, gairebé els llenguatges de programació que utilitzen l'ordenació integrada implementen quicksort.
Q # 4) Quin és l'avantatge de Quicksort?
Resposta:
- Quicksort és un algorisme eficient i pot ordenar fàcilment fins i tot una enorme llista d’elements.
- Està ordenat al lloc i, per tant, no necessita espai ni memòria addicional.
- S'utilitza àmpliament i proporciona una manera eficient d'ordenar conjunts de dades de qualsevol longitud.
P # 5) Per què Quicksort és millor que el tipus de combinació?
Resposta: La principal raó per la qual el quicksort és millor que el tipus de combinació és que el quicksort és un mètode d’ordenació al lloc i no requereix espai de memòria addicional. La combinació d’ordenació requereix memòria addicional per a l’ordenació intermèdia.
Conclusió
Quicksort es considera el millor algorisme d'ordenació principalment per la seva eficiència per ordenar fins i tot un conjunt de dades enorme en temps O (nlogn).
Quicksort també és un tipus de lloc i no requereix espai de memòria addicional. En aquest tutorial, hem vist la implementació recursiva i iterativa de quicksort.
Al nostre proper tutorial, continuarem amb els mètodes d'ordenació a Java.
=> Feu una ullada a la guia per a principiants de Java aquí
Lectura recomanada
- Algorisme de cerca binària a Java: implementació i exemples
- Java Array - Com imprimir elements d'un array a Java?
- Selecció d'ordenació a Java - Algorisme de selecció i exemples
- Tipus de dades de matriu: matriu int, matriu doble, matriu de cadenes, etc.
- Matriu Java: declarar, crear i inicialitzar una matriu a Java
- Tutorial JAVA per a principiants: més de 100 tutorials pràctics de vídeo Java
- Java Copy Array: Com copiar / clonar un array a Java
- Tutorial de longitud de matriu de Java amb exemples de codi
