quicksort java algorithm
Ta vadnica pojasnjuje algoritem Quicksort v Javi, njene ilustracije, Implementacija QuickSort v Javi s pomočjo primerov kode:
Tehnika sortiranja Quicksort se pogosto uporablja v programskih aplikacijah. Quicksort uporablja strategijo deli in vladaj, kot je združevanje.
V algoritmu za hitro sortiranje je najprej izbran poseben element, imenovan 'pivot', zadevna matrika ali seznam pa je razdeljen na dva podnabora. Velikosti razdeljenih podmnožic so lahko enake ali ne.
=> Preberite serijo Easy Java Training Series.
Pregrade so takšne, da so vsi elementi, ki so manjši od vrtilnega elementa, levo od vrtišča, elementi, večji od pivota, pa na desni od vrtišča. Rutina Quicksort rekurzivno razvrsti dva podseznama. Quicksort deluje učinkovito in tudi hitreje tudi za večje nize ali sezname.
Kaj se boste naučili:
kako si ogledati datoteke .swf
- Quicksort Partition Java
- Quicksort Algorithm Java
- Psevkodo za hitro razvrščanje
- Ilustracija
- Quicksort Implementacija v Javi
- Pogosto zastavljena vprašanja
- Zaključek
- Priporočeno branje
Quicksort Partition Java
Ločevanje je ključni postopek tehnike Quicksort. Kaj je torej particioniranje?
Glede na matriko A izberemo vrednost x, imenovano pivot, tako da so vsi elementi, manjši od x, pred x, vsi elementi, večji od x, pa za x.
Vrtilna vrednost je lahko kar koli od naslednjega:
- Prvi element v matriki
- Zadnji element v matriki
- Srednji element v matriki
- Kateri koli naključni element v matriki
Ta vrtilna vrednost se nato postavi na ustrezen položaj v matriki z razdelitvijo matrike. Tako je rezultat postopka 'particioniranja' vrtilna vrednost na ustreznem položaju in elementi manjši od pivot na levi in elementi večji od pivot na desni.
Upoštevajte naslednji diagram, ki pojasnjuje postopek delitve.
Zgornji diagram prikazuje postopek particioniranja matrike z večkratnim izbiranjem zadnjega elementa v matriki kot vrtišča. Na vsaki ravni upoštevajte, da matriko razdelimo na dve podniz, tako da pivot postavimo na pravilen položaj.
Nato naštejemo algoritem in psevdo-kodo za tehniko hitrega sortiranja, ki vključuje tudi particijsko rutino.
Quicksort Algorithm Java
Splošni algoritem za hitro sortiranje je podan spodaj.
quicksort(Arr, low, high) begin Declare array Arr[N] to be sorted low = 1st element; high = last element; pivot if(low Spodaj je psevdo-koda za tehniko hitrega sortiranja.
Psevkodo za hitro razvrščanje
Sledi psevdo-koda za hitro sortiranje. Upoštevajte, da smo priskrbeli psevdo-kodo za rutino hitrega razvrščanja in particioniranja.
//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 Ilustracija
Poglejmo ponazoritev algoritma hitrega sortiranja. Za primer vzemimo naslednjo matriko. Tu smo za pivot izbrali zadnji element.
Kot je prikazano, je prvi element označen z nizkim, zadnji pa z visokim.
Kot je razvidno iz zgornje ilustracije, obstajata dva kazalca, visoki in nizki, ki kažeta na zadnji in prvi element polja. Oba kazalca se premikata, ko hitri sortir napreduje.
Ko element, ki ga kaže nizek kazalec, postane večji od vrtilnega elementa in je element, ki ga kaže visok kazalnik, manjši od vrtilnega elementa, zamenjamo elemente, ki jih kaže nizki in visoki kazalec, in vsak kazalec napreduje za 1 položaj.
Zgornji koraki se izvajajo, dokler se kazalca med seboj ne prekrižata. Ko se prečkajo, vrtilni element dobi ustrezen položaj v matriki. Na tej točki je polje razdeljeno in zdaj lahko vsako podnivo razvrstimo neodvisno z rekurzivnim uporabo algoritma hitrega razvrščanja za vsako podniz.
Quicksort Implementacija v Javi
Tehniko QuickSort je mogoče implementirati v Javi z uporabo rekurzije ali ponovitve. V tem poglavju bomo videli obe teh tehnik.
Rekurzivni hitri sorti
Vemo, da osnovna tehnika hitrega sortiranja, prikazana zgoraj, za razvrščanje polja uporablja rekurzijo. V rekurzivnem hitrem sortiranju po razdelitvi polja se rutina hitrega sortiranja pokliče rekurzivno za razvrščanje podnizov.
Spodnja izvedba prikazuje tehniko hitrega sortiranja z uporabo rekurzije.
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 Izhod:
Izvirno polje: [4, -1, 6, 8, 0, 5, -3]
Razvrščeno polje: [-3, -1, 0, 4, 5, 6, 8]
Iterative Quicksort
V ponavljajočem se hitrem sortiranju uporabimo pomožni sklad za umestitev vmesnih parametrov, namesto da uporabimo particije rekurzije in razvrščanja.
Naslednji program Java izvaja iterativno hitro sortiranje.
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 Izhod:
Izvirno polje: [3, 2, 6, -1, 9, 1, -6, 10, 5]
Razvrščeno polje: [- 6, -1, 1, 2, 3, 6, 9, 10, 5]
Pogosto zastavljena vprašanja
V # 1) Kako deluje Quicksort?
Odgovor: Quicksort uporablja strategijo delitve in osvajanja. Quicksort najprej razdeli matriko okoli izbranega elementa vrtišča in ustvari podniz, ki so rekurzivno razvrščeni.
V # 2) Kakšna je časovna zapletenost Quicksorta?
Odgovor: Časovna zapletenost hitrega sortiranja je v povprečju O (nlogn). V najslabšem primeru je O (n ^ 2) enako kot izbira.
V # 3) Kje se uporablja Quicksort?
Odgovor: Quicksort se večinoma uporablja v rekurzivnih aplikacijah. Quicksort je del C-knjižnice. Tudi skoraj programski jeziki, ki uporabljajo vgrajeno razvrščanje, izvajajo hitro sortiranje.
V # 4) V čem je prednost Quicksorta?
Odgovor:
- Quicksort je učinkovit algoritem in z lahkoto razvrsti celo ogromen seznam elementov.
- Je razvrščena na mestu in zato ne potrebuje dodatnega prostora ali pomnilnika.
- Veliko se uporablja in omogoča učinkovit način razvrščanja naborov podatkov katere koli dolžine.
V # 5) Zakaj je Quicksort boljši od spajanja?
Odgovor: Glavni razlog, zaradi katerega je hitra razvrstitev boljša od združevalne, je ta, da je hitra izbira način razvrščanja na mestu in ne potrebuje dodatnega pomnilniškega prostora. Razvrščanje po združitvi zahteva dodaten pomnilnik za vmesno razvrščanje.
Zaključek
Quicksort velja za najboljši algoritem za razvrščanje predvsem zaradi njegove učinkovitosti razvrščanja celo velikega nabora podatkov v O (nlogn) času.
Quicksort je tudi sorta na mestu in ne zahteva dodatnega pomnilniškega prostora. V tej vadnici smo videli rekurzivno in iterativno izvajanje hitrega sortiranja.
najboljše spletno mesto za pretvorbo youtuba v mp3
V naši prihajajoči vadnici bomo nadaljevali z metodami razvrščanja v Javi.
=> Tukaj si oglejte Vodnik za začetnike Java.
Priporočeno branje
- Binarni algoritem iskanja v Javi - implementacija in primeri
- Java Array - Kako natisniti elemente polja v Javi?
- Razvrščanje razvrščanja v Javi - Algoritem razvrščanja izbir in primeri
- Vrste podatkov matrike - int matrika, dvojno polje, niz nizov itd.
- Java Array - prijavite, ustvarite in inicializirajte polje v Javi
- JAVA Vadnica za začetnike: 100+ praktičnih Javnih video vadnic
- Java Copy Array: Kako kopirati / klonirati polje v Javi
- Vadnica za dolžino polja Java s primeri kode