Johdanto Java-pikalajitteluun
Seuraava artikkeli Java-pikakortti tarjoaa yleiskatsauksen Java-pikakyselyalgoritmiin. Pikalajittelualgoritmi on yksi lajittelualgoritmeista, joka on tehokas ja samanlainen kuin yhdistämisalgoritmi. Tämä on yksi yleisimmin käytetyistä algoritmeista reaaliaikaiseen lajitteluun. Tämän algoritmin pahimman tapauksen aikakompleksiisuus on O (n 2), tapauksen keskimääräinen kompleksisuus on O (n log n) ja parhaan tapauksen ajan monimutkaisuus on O (n log n).
Avaruuden monimutkaisuus, jos O (n log n) missä on n, on tulon koko. Lajitteluprosessiin sisältyy tulon osittainen jakaminen, rekursiiviset iteraatiot ja kääntöelementin merkitseminen jokaiselle rekursiolle. Lajitteluun tässä algoritmissa sisältyy vierekkäisten elementtien vertailu iteratiivisella tavalla.
Kuinka Quick Sort toimii Java-versiossa?
Pikalajittelu-algoritmi voidaan toteuttaa Java-järjestelmässä muodostamalla pseudokoodi, joka koostuu vaiheiden sarjasta, joka on suunniteltu ja jota seurataan tehokkaasti.
- Nopean lajittelualgoritmin pääperiaate, että se toimii, perustuu jako- ja valloitus -lähestymistapaan ja on myös tehokas lajittelualgoritmi.
- Tulojärjestelmä on jaettu osamatriiseihin ja jako perustuu kääntöelementtiin, joka on keskeinen elementti. Kääntöelementin molemmin puolin olevat alaryhmät ovat pääalueita, joissa lajittelu todella tapahtuu.
- Keskimmäinen kääntöelementti on perusta jakaa ryhmä kahteen osioon, joissa ryhmäelementtien vasen puoli on pienempi kuin kääntöelementti ja ryhmäelementtien oikea puoli on suurempi kuin kääntöelementti.
- Ennen nivel-elementin pohtimista se voi olla kuka tahansa taulukon elementeistä. Tätä pidetään yleensä ymmärtämisen helpottamiseksi keskimmäisenä tai ensimmäisenä tai viimeisenä. Kääntöelementti voi olla satunnainen mistä tahansa taulukkoelementistä.
- Esimerkissämme taulukon viimeistä elementtiä pidetään kääntöelementtinä, jossa aliryhmien osiointi alkaa taulukon oikeasta päästä.
- Lopuksi kääntöelementti on tosiasiallisessa lajitteluasennossaan lajitteluprosessin loppuunsaattamisen jälkeen, jolloin tärkein lajitteluprosessi on lajittelualgoritmin osiologiikassa.
- Algoritmin tehokkuus riippuu alimatriisien koosta ja siitä, kuinka ne ovat tasapainossa. Mitä enemmän alaryhmät ovat epätasapainossa, sitä enemmän ajan monimutkaisuus johtaa pahimman tapauksen monimutkaisuuteen.
- Kääntöelementtien valinta satunnaisella tavalla johtaa moniin tapauksiin parhaaseen ajan monimutkaisuuteen sen sijaan, että valitsisit tietyn aloitus-, lopetus- tai keski-indeksin kääntöelementeiksi.
Esimerkkejä pikalajittelun toteuttamiseen Java-sovelluksessa
QuickSort-algoritmi on toteutettu alla kuvatulla Java-ohjelmointikielellä ja lähtökoodi on näytetty koodin alla.
- Koodi aluksi ottaa syötteen menetelmällä quickSortAlgo (), jolloin argumentteina ovat taulukko, alkuindeksi ja lopullinen indeksi eli taulukon pituus.
- Soitettuaan quickSortAlgo () -menetelmän se tarkistaa, onko alkuperäinen hakemisto pienempi kuin lopullinen indeksi, ja kutsuu sitten arrayPartition () -menetelmää saadakseen pivot-elementin arvon.
- Osioelementti sisältää logiikan järjestää pienemmät ja suuret elementit kääntöelementin ympärille elementtiarvojen perusteella.
- Saatuaan pivot-elementti-indeksin osiointimenetelmän suorittamisen jälkeen, QuickSortAlgo () -menetelmää kutsutaan itsessään rekursiivisesti, kunnes kaikki alimatriisit on osioitu ja lajiteltu kokonaan.
- Osiologiikassa viimeinen elementti osoitetaan kääntöelementiksi ja ensimmäistä elementtiä verrataan kääntöelementtiin eli viimeiseen, jossa elementit vaihdetaan sen perusteella, ovatko ne pienempiä vai suurempia.
- Tämä rekursioprosessi tapahtuu, kunnes kaikki taulukon elementit osioidaan ja lajitellaan, jolloin lopputulos on yhdistetty lajiteltu taulukko.
- Elementit vaihdetaan silmukka iteraation sisällä vain siinä tapauksessa, että elementti on pienempi tai yhtä suuri kuin kääntöelementti.
- Kun iteraatioprosessi on suoritettu loppuun, viimeinen elementti vaihdetaan, ts. Kääntöelementin arvo siirretään vasemmalle puolelle siten, että uudet osiot tehdään ja sama prosessi toistuu rekursion muodossa, mikä johtaa lajitteluoperaatioiden sarjaan erilaisissa mahdollisissa osioissa alimatriisin muodostuksena annetusta ryhmäelementeistä.
- Alla olevaa koodia voidaan käyttää millä tahansa IDE: llä ja lähtö voidaan varmistaa tarkistamalla taulukon arvo mainiossa (). Päämenetelmää käytetään vain tulosteen saamiseksi konsoliin. Osana Java-koodausstandardeja päämenetelmä voidaan poistaa alapuolelta ja objekti voidaan luoda ja alla olevia menetelmiä voidaan kutsua tekemällä niistä epästaattisia.
Nopean lajittelualgoritmin koodin käyttöönotto Java-sovelluksessa
/*
* 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);
)
)
)
lähtö:
johtopäätös
Pikalajittelualgoritmi on tehokas, mutta ei kovin vakaa verrattuna muihin lajittelutekniikoihin. Nopeiden lajittelualgoritmien tehokkuus heikkenee, jos toistuvia elementtejä on enemmän, mikä on haitta. Avaruuden monimutkaisuus on optimoitu tässä nopean lajittelun algoritmissa.
Suositellut artikkelit
Tämä on opas pikalajitteluun Java-sovelluksessa. Tässä keskustellaan siitä, kuinka Quick Sort toimii Javassa, sekä esimerkki ja koodin toteutus. Voit myös käydä läpi muiden ehdotettujen artikkeleidemme saadaksesi lisätietoja -
- Kasa lajittelu Java
- Mikä on binaaripuu Javassa?
- Bittien manipulointi Java: lla
- Katsaus yhdistämiseen Järjestä JavaScript
- Yleiskuvaus Quick Sortista JavaScriptinä
- Heap Sort Pythonissa
- Kuusi suosituinta lajittelualgoritmia JavaScriptissä