Meni

Brzo sortiranje u Javi - algoritam, ilustracija i implementacija

  • Glavni
  • Ostalo
  • Brzo sortiranje u Javi - algoritam, ilustracija i implementacija

quicksort java algorithm

Isprobajte Naš Instrument Za Uklanjanje Problema

Ovaj vodič objašnjava algoritam brzog sortiranja u Javi, njegove ilustracije, implementaciju QuickSort-a u Javi uz pomoć primjera koda:

Tehnika brzog sortiranja široko se koristi u softverskim aplikacijama. Quicksort koristi strategiju podijeli i osvoji, poput spajanja.

U algoritmu brzog sortiranja prvo se odabire poseban element nazvan 'pivot', a dotični niz ili popis dijeli se na dva podskupa. Podijeljeni podskupovi mogu ili ne moraju biti jednake veličine.

=> Pročitajte seriju Easy Training Training.

QuickSort tehnika u Javi

Pregrade su takve da su svi elementi manji od pivot elementa smješteni lijevo od pivota, a elementi veći od pivota desno od pivota. Rutina Quicksort rekurzivno sortira dva pod-popisa. Quicksort djeluje učinkovito, a također brže čak i za veće nizove ili popise.

Što ćete naučiti:

Quicksort particija Java

Pregrađivanje je ključni proces Quicksort tehnike. Pa, što je particija?

S obzirom na niz A, odabiremo vrijednost x koja se naziva pivot tako da su svi elementi manji od x ispred x, a svi elementi veći od x iza x.

Vrijednost osovine može biti bilo što od sljedećeg:

  • Prvi element u polju
  • Posljednji element u nizu
  • Srednji element u polju
  • Bilo koji slučajni element u polju

Ta se zaokretna vrijednost zatim postavlja particijom niza na odgovarajući položaj u polju. Stoga je izlaz postupka 'particioniranja' vrijednost osovine na odgovarajućem položaju i elementi manji od zaokreta na lijevoj strani i elementi veći od zaokreta s desne strane.

Razmotrite sljedeći dijagram koji objašnjava postupak particioniranja.

proces particioniranja

Gornji dijagram prikazuje postupak particioniranja niza ponavljanim odabirom posljednjeg elementa u nizu kao stožera. Na svakoj razini imajte na umu da niz dijelimo na dva podniza postavljanjem pivota na njegov ispravan položaj.

Dalje, navodimo algoritam i pseudo-kod za tehniku ​​brzog sortiranja koji također uključuje particijsku rutinu.

Quicksort algoritam Java

Općeniti algoritam za brzi sortiranje dan je u nastavku.

quicksort(Arr, low, high) begin Declare array Arr(N) to be sorted low = 1st element; high = last element; pivot if(low

Dolje je dan pseudo-kôd za tehniku ​​brzog sortiranja.

Pseudocode za brzo sortiranje

Slijedi pseudo-kôd za brzo sortiranje. Imajte na umu da smo osigurali pseudo-kôd za rutinu brzog sortiranja i 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

Pogledajmo ilustraciju algoritma brzog sortiranja. Uzmimo sljedeći niz kao primjer. Ovdje smo odabrali zadnji element kao stožer.

Kao što je prikazano, prvi je element označen niskim, a zadnji element visokim.

Ilustracija Quicksort algoritma

Kao što je vidljivo na gornjoj ilustraciji, postoje dva pokazivača, visoki i najniži koji upućuju na posljednji i prvi element niza. Oba ova pokazivača premještaju se kako brzi sortiment napreduje.

Kada element na koji upućuje niži pokazivač postane veći od pivot elementa, a element na koji je usmjeren visokim pokazivačem je manji od pivot elementa, zamijenimo elemente na koje pokazuju niski i visoki pokazivač, a svaki pokazivač napreduje za 1 položaj.

internet stvari koje tvrtke mogu gledati

Gornji koraci provode se sve dok se oba pokazivača ne ukrste u polju. Jednom kad se prekriže, pivot element dobiva svoj pravilan položaj u nizu. U ovom je trenutku niz podijeljen i sada svaki pod-niz možemo sortirati neovisno rekurzivnom primjenom algoritma brzog razvrstavanja na svaki pod-niz.

Quicksort implementacija u Javi

Tehnika QuickSort može se implementirati u Javi koristeći rekurziju ili iteraciju. U ovom ćemo odjeljku vidjeti obje ove tehnike.

Rekurzivni brzi sorti

Znamo da osnovna tehnika brzog sortiranja ilustrirana gore koristi rekurziju za sortiranje niza. U rekurzivnom brzom sortiranju nakon particioniranja niza, rutina brzog sortiranja poziva se rekurzivno za sortiranje podniza.

Sljedeća implementacija prikazuje tehniku ​​brzog sortiranja pomoću 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

Izlaz:

Izvorni niz: (4, -1, 6, 8, 0, 5, -3)
Poredani niz: (-3, -1, 0, 4, 5, 6, 8)

Rekurzivni brzi sortiranje - izlaz

Iterative Quicksort

U iterativnom brzom sortiranju koristimo pomoćni stog za postavljanje posrednih parametara umjesto da koristimo rekurziju i sortiranje particija.

Sljedeći Java program implementira iterativni brzi 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

Izlaz:

Izvorni niz: (3, 2, 6, -1, 9, 1, -6, 10, 5)
Sortirani niz: (- 6, -1, 1, 2, 3, 6, 9, 10, 5)

Iterativni brzi sortiranje - izlaz

Često postavljana pitanja

P # 1) Kako djeluje Quicksort?

Odgovor: Quicksort koristi strategiju podijeli i osvoji. Quicksort prvo particionira niz oko odabranog pivot elementa i generira podnizove koji se rekurzivno sortiraju.

najbolji program za ažuriranje upravljačkih programa za Windows 10

P # 2) Kolika je vremenska složenost Quicksorta?

Odgovor: Vremenska složenost brzog sortiranja u prosjeku je O (nlogn). U najgorem slučaju, to je O (n ^ 2) isto što i selekcijska sorta.

P # 3) Gdje se koristi Quicksort?

Odgovor: Quicksort se uglavnom koristi u rekurzivnim aplikacijama. Quicksort je dio C-biblioteke. Također, gotovo programski jezici koji koriste ugrađeno sortiranje implementiraju brzi sortiranje.

P # 4) Koja je prednost Quicksorta?

Odgovor:

  • Quicksort je učinkovit algoritam i lako može razvrstati čak i ogroman popis elemenata.
  • To je sortiranje na mjestu i stoga mu ne treba dodatni prostor ili memorija.
  • Široko se koristi i pruža učinkovit način razvrstavanja skupova podataka bilo koje duljine.

P # 5) Zašto je Quicksort bolji od spajanja?

Odgovor: Glavni razlog zbog kojeg je brzi sortiranje bolji od sortiranja spajanjem je taj što je živi sortiranje na mjestu i ne zahtijeva dodatni prostor u memoriji. Sortiranje spajanjem zahtijeva dodatnu memoriju za srednje razvrstavanje.

Zaključak

Quicksort se smatra najboljim algoritmom za sortiranje, uglavnom zbog svoje učinkovitosti razvrstavanja čak i ogromnog skupa podataka u O (nlogn) vremenu.

Quicksort je također vrsta na mjestu i ne zahtijeva dodatni prostor u memoriji. U ovom uputstvu vidjeli smo rekurzivnu i iterativnu implementaciju brzog sortiranja.

U našem nadolazećem uputstvu nastavit ćemo s metodama sortiranja u Javi.

=> Ovdje pogledajte Vodič za početnike za Java.

Preporučena literatura

^