Uvod v hitro razvrščanje na Javi
Naslednji članek Hitro razvrščanje v Javi ponuja oris algoritma za hitro razvrščanje v Javi. Algoritem hitrega razvrščanja je eden od algoritmov za razvrščanje, ki je učinkovit in podoben algoritmu za razvrščanje združevanja. To je eden najpogosteje uporabljenih algoritmov za namene razvrščanja v realnem času. Najhujša časovna zapletenost tega algoritma je O (n 2), povprečna časovna zahtevnost je O (n log n) in najboljša časovna kompleksnost je O (n log n).
Kompleksnost prostora, če je O (n log n), kjer je n, velikost vhoda. Postopek razvrščanja vključuje razdelitev vnosa, rekurzivne iteracije in označevanje glavnega elementa za vsako rekurzijo. Vrsta razvrščanja v tem algoritmu vključuje primerjavo sosednjih elementov na iterativni način.
Kako hitro razvrščanje deluje na Javi?
Algoritem za hitro razvrščanje je mogoče izvajati v Javi tako, da oblikuje psevdo kodo z zaporedjem korakov, ki je učinkovito in zasnovan.
- Glavno načelo algoritma za hitro razvrščanje, ki deluje, temelji na pristopu "deli in osvoji" in je tudi učinkovit algoritem razvrščanja.
- Vhodna matrika je razdeljena na podrazrede in delitev temelji na vrtilnem elementu, ki je osrednji element. Podračuni na obeh straneh vrtilnega elementa so glavna področja, kjer se razvrščanje dejansko dogaja.
- Osrednji vrtilni element je osnova za razdelitev matrike v dve particiji, kjer je leva polovica elementov nižja od vrtilnega elementa in desna polovica elementov matrike večja od vrtilnega elementa.
- Preden preučimo element vrtenja, je lahko kdo izmed elementov matrike. Za lažje razumevanje se to običajno šteje za srednjega ali prvega ali zadnjega. Element vrtenja je lahko naključen od katerega koli od elementov matrike.
- V našem primeru je zadnji element matrike obravnavan kot vrtilni element, kjer se razdelitev podračunov začne z desnega konca matrike.
- Končno bo vrtilni element po končanem postopku sortiranja v svojem dejanskem razvrščenem položaju, kjer je glavni postopek razvrščanja lociran v logiki particije algoritma za razvrščanje.
- Učinkovitost algoritma je odvisna od velikosti nizov in njihove uravnoteženosti. Bolj kot so nizki neuravnoteženi, bolj bo časovna zapletenost vodila do najslabše zapletenosti.
- Izbira elementov vrtilnih elementov naključno povzroči najboljšo časovno zapletenost v veliko primerih, namesto da izberemo določen začetni, končni ali srednji indeks kot vrtilne elemente.
Primeri za izvajanje hitrega razvrščanja v Javi
Algoritem QuickSort je bil izveden s programskim jezikom Java, kot je spodaj, in izhodna koda je prikazana pod kodo.
- Koda sprva sprejme vhod s pomočjo metode quickSortAlgo () z array, začetnim indeksom in končnim indeksom, tj. Dolžino matrike kot argumentom.
- Po klicu metode quickSortAlgo () preveri, ali je začetni indeks manjši od končnega indeksa, in nato pokliče metodo arrayPartition (), da dobi vrednost vrtilnega elementa.
- Element particije vsebuje logiko razporejanja manjših in večjih elementov okoli vrtilnega elementa na podlagi vrednosti elementov.
- Potem ko dobimo indeks vrtilnih elementov po izvedbi metode particije, se metoda quickSortAlgo () sam pokliče rekurzivno, dokler se vsi podračuni ne razdelijo in razvrstijo v celoti.
- V logiki particije je zadnji element dodeljen kot vrtilni element in prvi element se primerja z vrtilnim elementom, tj. Zadnji, pri katerem se elementi zamenjajo glede na to, ali so manjši ali večji.
- Ta postopek rekurzije se zgodi, dokler vsi elementi matrike niso razdeljeni in razvrščeni, kjer je končni rezultat kombinirano razvrščeno polje.
- Elementi se zamenjajo znotraj iteracije for-zanke samo v primeru, da je element manjši ali enak vrtilnemu elementu.
- Po zaključku postopka iteracije se zadnji element zamenja, tj. Vrednost vrtilnega elementa se premakne na levo stran, tako da se izdelajo nove particije in se isti postopek ponovi v obliki rekurzije, kar ima za posledico vrsto operacij razvrščanja na različnih možnih particijah kot tvorba podračunov iz danih elementov matrike.
- Spodnja koda se lahko izvaja na katerem koli IDE, izhod pa je mogoče preveriti s spreminjanjem vrednosti matrike v main () Glavna metoda se uporablja samo za namen pridobivanja izhoda v konzoli. Kot del standardov kodiranja Java je mogoče spodaj odstraniti glavno metodo in ustvariti predmet, spodaj pa jih lahko prikličemo tako, da postanejo nestatični.
Implementacija algoritma za hitro razvrščanje v Javi
/*
* 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);
)
)
)
Izhod:
Zaključek
Algoritem hitrega razvrščanja je v primerjavi z drugimi tehnikami sortiranja učinkovit, vendar premalo stabilen. Učinkovitost algoritmov za hitro razvrščanje se zmanjša v primeru večjega števila ponovljenih elementov, kar je pomanjkljivost. Kompletnost prostora je optimizirana v tem algoritmu za hitro razvrščanje.
Priporočeni članki
To je vodnik za hitro razvrščanje na Javi. Tukaj razpravljamo o načinu hitrega razvrščanja v Javi skupaj s primerom in izvedbo kode. Če želite izvedeti več, lahko preberete tudi druge naše predlagane članke -
- Razvrsti po Javi
- Kaj je binarno drevo na Javi?
- Manipulacija bitja na Javi
- Pregled Razvrsti združitve v JavaScript
- Pregled hitrega razvrščanja v JavaScript
- Razvrstite v Python
- Najboljših 6 algoritmov za razvrščanje v JavaScript