Uvod u brzo sortiranje na Javi
Sljedeći članak Brzo sortiranje na Javi pruža pregled algoritma za brzo sortiranje u Javi. Algoritam brzih sortiranja jedan je od algoritama sortiranja koji je učinkovit i sličan algoritmu sortiranja spajanja. Ovo je jedan od najčešće korištenih algoritama za svrstavanje u stvarnom vremenu. Najgora vremenska složenost ovog algoritma je O (n 2), prosječna vremenska složenost slučaja je O (n log n), a najbolja vremenska složenost je O (n log n).
Složenost prostora ako je O (n log n) gdje je n veličina ulaza. Proces razvrstavanja uključuje podjelu ulaza, rekurzivne iteracije i označavanje središnjeg elementa za svaku rekurziju. Vrsta sortiranja u ovom algoritmu uključuje usporedbu susjednih elemenata na iterativni način.
Kako brzo razvrstavanje funkcionira na Javi?
Algoritam za brzo razvrstavanje može se implementirati u Javi formiranjem pseudo koda s nizom koraka koji su efikasno dizajnirani i praćeni.
- Glavno načelo algoritma za brzo sortiranje koji radi temelji se na pristupu podijeli i osvoji (eng. Conquer), a ujedno je i učinkovit algoritam sortiranja.
- Ulazni niz podijeljen je na podskupine, a podjela se temelji na elementu stožera koji je središnji element. Pod nizovi na obje strane stožernog elementa glavna su područja na kojima se sortiranje zapravo događa.
- Središnji element stožišta je baza koja dijeli niz na dvije particije gdje je lijeva polovica elemenata niže od stožernog elementa, a desna polovica elemenata niza veća od stožernog elementa.
- Prije razmatranja okretnog elementa, može biti bilo tko od elemenata niza. To se obično smatra srednjim ili prvim ili posljednjim radi lakšeg razumijevanja. Element stožera može biti nasumičan od bilo kojeg elementa niza.
- U našem primjeru, posljednji element matrice smatra se stožernim elementom, gdje podjela nizova započinje s desnog kraja matrice.
- Konačno, stožerni element će se nalaziti u stvarnom položaju sortiranja nakon završetka postupka sortiranja, pri čemu se glavni proces sortiranja nalazi u logici particije algoritma sortiranja.
- Učinkovitost algoritma ovisi o veličini podruga i kako su uravnoteženi. Što su pod nizovi neuravnoteženi, to će složenost vremena dovesti do složenijih slučajeva.
- Odabir elemenata stožišta nasumično rezultira najboljom vremenskom složenošću u mnogim slučajevima umjesto odabira određenog početnog, završnog ili srednjeg indeksa kao stožernih elemenata.
Primjeri za uvođenje brzog sortiranja u Javi
Algoritam QuickSort implementiran je koristeći programski jezik Java kao što je dolje navedeno, a izlazni kod prikazan je pod kôdom.
- Kôd u početku uzima ulaz koristeći metodu quickSortAlgo () s nizom, početnim indeksom i završnim indeksom, tj. Dužinom polja kao argumenta.
- Nakon pozivanja metode quickSortAlgo (), provjerava je li početni indeks manji od konačnog indeksa, a zatim poziva metodu arrayPartition () kako bi dobio vrijednost stožernog elementa.
- Element particije sadrži logiku raspoređivanja manjih i većih elemenata oko stožernog elementa na temelju vrijednosti elemenata.
- Nakon dobivanja indeksa stožernih elemenata nakon izvršenja metode particije, metoda QuickSortAlgo () sama se poziva rekurzivno dok se svi podraslasti ne dijele i ne sortiraju u potpunosti.
- U logici particije, posljednji element je dodijeljen kao stožerni element, a prvi se element uspoređuje sa stožernim elementom, tj. Sa zadnjim gdje se elementi izmjenjuju na temelju toga jesu li manji ili veći.
- Taj se proces rekurzije događa dok se svi elementi niza ne podijele i razvrstaju gdje je konačni rezultat kombinirano razvrstani niz.
- Elementi se izmjenjuju unutar iteracije for-petlje samo u slučaju da je element manji ili jednak elementu okretnog elementa.
- Nakon dovršetka postupka ponavljanja, zamjenjuje se posljednji element, tj. Vrijednost pomičnog elementa se pomiče na lijevu stranu tako da se izrađuju nove particije i isti postupak ponavlja u obliku rekurzije što rezultira nizom operacija sortiranja na različitim mogućim particijama kao formiranje potpolje iz datih elemenata niza.
- Donji kôd može se izvoditi na bilo kojem IDE-u, a izlaz se može provjeriti promjenom vrijednosti polja u main () Glavna metoda koristi se upravo u svrhu dobivanja izlaza u konzoli. Kao dio Java kodiranja standarda, glavna metoda se može ukloniti u nastavku, a objekt se može stvoriti i ispod njih se mogu nazivati metode čineći ih nestalnim.
Implementacija algoritma brzog sortiranja u 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);
)
)
)
Izlaz:
Zaključak
Algoritam brzog razvrstavanja je učinkovit, ali nije mnogo stabilan u usporedbi s drugim tehnikama sortiranja. Učinkovitost algoritama za brzo sortiranje opada u slučaju većeg broja ponovljenih elemenata, što je nedostatak. Složenost prostora optimizirana je u ovom algoritmu za brzo sortiranje.
Preporučeni članci
Ovo je vodič za brzo sortiranje na Javi. Ovdje smo raspravljali o načinu na koji Quick Sort djeluje na Javi zajedno s primjerom i implementacijom koda. Možete i proći naše druge predložene članke da biste saznali više -
- Poredaj u Javi
- Što je binarno stablo na Javi?
- Manipulacija bita u Javi
- Pregled sortiranja spajanja u JavaScript-u
- Pregled brzog razvrstavanja u JavaScript-u
- Poredajte u Python
- Top 6 algoritma za razvrstavanje u JavaScript