Kuidas rakendada QuickSorti Java-s?

See artikkel tutvustab teile veel üht jagamise ja vallutamise sorteerimisalgoritmi, mis on Java-s QuickSort, ja järgige seda demonstratsiooniga.

QuickSort on jagamise ja vallutamise algoritm. Jagamise ja vallutamise algoritmi kujundamise paradigmas jagame alamprobleemides olevad probleemid rekursiivselt, seejärel lahendame alamprobleemid ja lõpuks kombineerime lahendused lõpptulemuse leidmiseks. Selles artiklis keskendume QuickSort In'ile



Järgmisi näpunäiteid käsitletakse selles artiklis,



Alustagem!

Probleemide jagamisel alamprobleemideks tuleb meeles pidada, et alamprobleemide struktuur ei muutu algse probleemi seisuga.
Jaga ja võida algoritmil on 3 sammu:



  • Jaga: probleemi jaotamine alamprobleemideks
  • Vallutamine: alamprobleemide rekursiivne lahendamine
  • Kombineeri: kombineerides lahendused lõpptulemuse saamiseks

Pilt- Kiire sortimine Java- Edurekas

Jagamise ja vallutamise paradigmal põhinevaid erinevaid algoritme. Nende hulgas on ka kiire sortimine ja ühendamine.

Kuigi QuickSorti halvim ajaline keerukus on O (n2), mis on rohkem kui paljud teised sorteerimisalgoritmid nagu Sorteerimise ja Hunniku sorteerimine, on QuickSort praktikas kiirem, kuna selle sisemist silmust saab tõhusalt rakendada enamikus arhitektuurides ja enamikus pärismaailma andmed.



Räägime Quick sort algoritmi juurutamisest. Kiirsordi algoritmid võtavad pöördelemendi ja jaotavad massiivi pöördelemendi ümber. Quicksotil on mitmeid variatsioone, mis sõltuvad pöördelemendi valimisest. Pivoti elemendi valimiseks on mitu võimalust:

  • Esimese elemendi valimine
  • Valige viimane element
  • Juhusliku elemendi valimine
  • Mediaanelemendi valimine

Järgmine oluline asi, mida mõista, on partitsiooni () funktsioon Kiire sorteerimise algoritmis. Jaotefunktsioon pöördelemendi võtmiseks, asetab selle õigesse asendisse, liigutab kõik pöördelementist väiksemad elemendid vasakule ja kõik elemendid paremale paremale. Quicksortil kulub selleks lineaarne aeg.
Seejärel jagatakse massiiv liigendelemendist kaheks osaks (st elemendid, mis on väiksemad kui pöördetapp, ja elemendid, mis on suuremad kui pöördetapp) ja mõlemad massiivid sorteeritakse rekursiivselt Quicksorti algoritmi abil.

Nüüd, kui oleme aru saanud QuickSorti algoritmi toimimisest. Mõistame, kuidas Quicksorti algoritmi Java-s täiendada.

kuidas jõudu pythonis kasutada

Kiire sortimine Funktsioon:

/ * Quicksorti funktsioon vajab massiivi sorteerimist madalaima ja kõrgeima indeksiga * /

void sort (int arr [], int lowIndex, int highIndex) {// Kuni lowIndex = highIndex if (lowIndex

Vaatame nüüd jaotuskoodi, et mõista, kuidas see töötab.

Jaotus Kood

Jaotuskoodis valime pöördelemendiks viimase elemendi. Me läbime kogu massiivi (st kasutame meie puhul muutujat j). Jälgime massiivi viimast väikseimat elementi (st kasutame meie puhul muutujat i). Kui leiame mõne pöördepunktist väiksema elemendi, liigutame praeguse elemendi a [j] arr [i] -ga, muidu jätkame liikumist.

int partitsioon (int arr [], int lowIndex, int highIndex) {// Viimase elemendi tegemine pöördetapina int pivot = arr [highIndex] // i abil pivoti väiksemate elementide jälgimine int i = (lowIndex-1) jaoks (int j = lowIndex j

Nüüd, kui olete aru saanud funktsioonist Quicksort & partition, vaadake kiiret koodi

Kiire sortimine Java kood

klass QuickSort {// Sektsioonimeetod int partitsioon (int arr [], int lowIndex, int highIndex) {int pivot = arr [highIndex] int i = (lowIndex-1) for (int j = lowIndex j

// Sorteerimismeetod

void sort (int arr [], int lowIndex, int highIndex) {if (lowIndex

// Massiivi printimise meetod

staatiline tühine printArray (int arr []) {int n = arr.length for (int i = 0 i

// Peamine meetod

public static void main (String args []) {int arr [] = {101, 37, 68, 29, 11, 5} int n = arr.length QuickSort ob = new QuickSort () ob.sort (arr, 0, n-1) System.out.println ('sorteeritud massiiv') printArray (arr)}}

Väljund:

Väljund - kiire sortimine Java- Edurekas

Nüüd pärast ülaltoodud Java-programmi käivitamist oleksite aru saanud, kuidas QuickSort töötab ja kuidas seda Java-s rakendada.Nii oleme jõudnud selle artikli juurde, mis käsitleb teemat ‘Quicksort in Java’. Kui soovite rohkem teada saada,vaadake autor Edureka, usaldusväärne veebipõhine õppefirma. Edureka Java J2EE ja SOA koolitus- ja sertifitseerimiskursus on mõeldud selleks, et õpetada teid nii Java põhiliste kui ka edasijõudnute kontseptsioonide jaoks koos erinevate Java-raamistikega nagu Hibernate & Spring.

Kas teil on meile küsimus? Palun mainige seda selle blogi kommentaaride jaotises ja võtame teiega ühendust niipea kui võimalik.