quick sort c with examples
Brzi sortiranje na C ++ s ilustracijom.
Quicksort je široko korišteni algoritam za sortiranje koji odabire određeni element koji se naziva 'pivot' i razdvaja niz ili popis koji će se razvrstati u dva dijela na temelju ovog stožera s0 da su elementi manji od pivota lijevo od popisa i elementi veće od pivota nalaze se s desne strane popisa.
Tako je popis podijeljen na dvije podliste. Podspisci možda neće biti potrebni za istu veličinu. Tada se Quicksort rekurzivno poziva kako bi razvrstao ove dvije popise.
=> Ovdje pogledajte Savršeni vodič za obuku za C ++.
Što ćete naučiti:
- Uvod
- Opći algoritam
- Pseudo kod za brzi sortiranje
- Ilustracija
- Primjer C ++
- Primjer Java
- Analiza složenosti algoritma brzog sortiranja
- 3-smjerni Quicksort
- Randomized Quicksort
- Quicksort vs. Merge Sort
- Zaključak
- Preporučena literatura
Uvod
Quicksort djeluje učinkovito, brže, čak i za veće nizove ili popise.
U ovom uputstvu istražit ćemo više o radu Quicksorta zajedno s nekoliko primjera programiranja algoritma brzog sortiranja.
Kao stožernu vrijednost možemo odabrati prvu, zadnju ili srednju vrijednost ili bilo koju slučajnu vrijednost. Općenita je ideja da se na kraju pivot vrijednost postavlja na odgovarajući položaj u nizu pomicanjem ostalih elemenata u nizu ulijevo ili udesno.
Opći algoritam
Općeniti algoritam za Quicksort dan je u nastavku.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Pogledajmo sada pseudokod za Quicksort tehniku.
Pseudo kod za brzi sortiranje
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low U nastavku je opisan rad algoritma za particioniranje na primjeru.
Na ovoj ilustraciji zadnji element uzimamo kao stožer. Možemo vidjeti da se niz sukcesivno dijeli oko pivot elementa sve dok u polju nemamo jedan element.
Sada donosimo ilustraciju Quicksorta u nastavku kako bismo bolje razumjeli koncept.
Ilustracija
Pogledajmo ilustraciju algoritma brzog sortiranja. Smatraj sljedeći niz s posljednjim elementom pivotom. Također, prvi je element označen niskim, a zadnji element visokim.
java programiranje intervju pitanja za iskusne
Iz ilustracije možemo vidjeti da pomičemo pokazivače visoko i nisko na oba kraja niza. Kad god niske točke usmjere na element veći od pivota, a visoke točke na element manji od pivota, tada izmjenjujemo položaje tih elemenata i pomičemo niske i visoke pokazivače u njihovim pravcima.
To se radi sve dok se niski i visoki pokazivači ne prekriže. Jednom kada se križaju, zakretni element postavlja se u odgovarajući položaj i niz se dijeli na dva dijela. Tada se oba ova podniza sortiraju neovisno pomoću brzog sortiranja rekurzivno.
Primjer C ++
Slijedi implementacija Quicksort algoritma u C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Izlaz:
Ulazni niz
12 23 3 43 51 35 19 45
Niz sortiran s brzim sortiranjem
3 12 19 23 35 43 45 51
kako otvoriti json datoteku u sustavu Windows
Ovdje imamo nekoliko rutina koje se koriste za particioniranje niza i rekurzivno pozivanje brzog sortiranja za sortiranje particije, osnovne funkcije brzog sortiranja i uslužnih funkcija za prikaz sadržaja niza i zamjenu dvaju elemenata u skladu s tim.
Prvo pozivamo funkciju brzog sortiranja s ulaznim nizom. Unutar funkcije brzog sortiranja nazivamo particijsku funkciju. U particijskoj funkciji koristimo posljednji element kao stožerni element za niz. Jednom kada se odluči za pivot, niz je podijeljen na dva dijela, a zatim se poziva funkcija brzog sortiranja koja će neovisno sortirati oba podniza.
Kad se funkcija brze sortiranja vrati, niz se sortira tako da se element zakretanja nalazi na ispravnom mjestu, a elementi manji od zaokreta lijevo od zaokreta, a elementi veći od zaokreta desno od osovine.
Dalje, implementirat ćemo algoritam brzog sortiranja u Javi.
Primjer Java
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Izlaz:
Ulazni niz
12 23 3 43 51 35 19 45
Niz nakon sortiranja s brzim sortiranjem
3 12 19 23 35 43 45 51
I u implementaciji Jave koristili smo istu logiku koju smo koristili u implementaciji C ++. Koristili smo zadnji element u nizu dok se pivot i brzi sorti izvode na nizu kako bi se pivot element stavio na odgovarajući položaj.
Analiza složenosti algoritma brzog sortiranja
Vrijeme potrebno sortiranju niza za sortiranje niza ovisi o ulaznom nizu i strategiji ili metodi particije.
Ako je k broj elemenata manji od osovine, a n ukupan broj elemenata, tada se opće vrijeme potrebno brzom sortiranju može izraziti na sljedeći način:
T (n) = T (k) + T (n-k-1) + O (n)
Ovdje su T (k) i T (n-k-1) vrijeme koje je potrebno rekurzivnim pozivima, a O (n) je vrijeme potrebno particionom pozivu.
Detaljno analizirajmo ovu vremensku složenost za brzi sortiranje.
# 1) Najgori slučaj : Najgori slučaj u tehnici brzog sortiranja javlja se uglavnom kada kao pivot odaberemo najniži ili najviši element u polju. (Na gornjoj ilustraciji odabrali smo najviši element kao stožer). U takvoj se situaciji događa najgori slučaj kada je niz koji se sortira već sortiran u rastućem ili silaznom redoslijedu.
Stoga se gornji izraz za ukupno vrijeme uzima kao:
T (n) = T (0) + T (n-1) + O (n) to rješava na Nadva)
# 2) Najbolji slučaj: Najbolji slučaj za brzo sortiranje uvijek se dogodi kada je odabrani pivot element sredina niza.
Stoga je ponavljanje za najbolji slučaj:
što je deque c ++
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Prosječni slučaj: Da bismo analizirali prosječni slučaj za brzi sortiranje, trebali bismo razmotriti sve permutacije niza, a zatim izračunati vrijeme potrebno za svaku od tih permutacija. Ukratko, prosječno vrijeme za brzi sortiranje također postaje O (nlogn).
Slijede različite složenosti Quicksort tehnike:
Najgora vremenska složenost O (n 2) stabilnost Nije stabilno jer se dva elementa s istim vrijednostima neće smjestiti u isti redoslijed. Stabilno - dva elementa s istim vrijednostima pojavit će se u istom redoslijedu u sortiranom izlazu. Najbolja vremenska složenost O (n * log n) Prosječna vremenska složenost O (n * log n) Složenost prostora O (n * log n)
Možemo implementirati quicksort na mnogo različitih načina samo promjenom izbora pivot elementa (srednji, prvi ili zadnji), međutim najgori se slučaj rijetko događa za quicksort.
3-smjerni Quicksort
U originalnoj tehnici brzog sortiranja obično odabiremo pivot element, a zatim dijelimo niz na podnizove oko ovog pivota, tako da se jedan podskup sastoji od elemenata manjih od pivota, a drugi od elemenata većih od pivota.
Ali što ako odaberemo pivot element i ako je u nizu više od jednog elementa koji je jednak pivot?
Na primjer, razmotrite sljedeći niz {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Ako izvedemo jednostavni brzi sortiranje na ovom polju i odaberemo 4 kao stožerni element, tada ćemo popraviti samo jednu pojavu elementa 4, a ostatak će biti podijeljen zajedno s ostalim elementima.
Umjesto toga, ako koristimo trosmjerni brzi sortiranje, tada ćemo niz (l ... r) podijeliti na tri podniza kako slijedi:
- Polje (l… i) - Ovdje je i pivot i ovaj niz sadrži elemente manje od pivota.
- Niz (i + 1… j-1) - Sadrži elemente koji su jednaki osovini.
- Niz (j ... r) - Sadrži elemente veće od osovine.
Tako se trosmjerni brzi sortir može koristiti kada imamo više od jednog suvišnog elementa u nizu.
Randomized Quicksort
Tehnika brzog sortiranja naziva se tehnika randomizovanog brzog sortiranja kada za odabir stožernog elementa koristimo slučajne brojeve. U randomiziranom brzom sortiranju naziva se 'središnji stožer' i dijeli niz na takav način da svaka strana ima barem ¼ elemenata.
Pseudo-kôd za randomizirani brzi sortiran dan je u nastavku:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureU gornjem kodu na “randomQuickSort”, u koraku # 2 odabiremo središnju osovinu. U koraku 2 vjerojatnost da je odabrani element središnji osovina je ½. Stoga se očekuje da će se petlja u koraku 2 pokrenuti 2 puta. Stoga je vremenska složenost za korak 2 u randomiziranom brzom sortiranju O (n).
Korištenje petlje za odabir središnjeg pivota nije idealan način za provedbu randomiziranog brzog sortiranja. Umjesto toga, možemo nasumično odabrati element i nazvati ga središnjim okretanjem ili presložiti elemente niza. Očekivana vremenska složenost u najgorem slučaju za randomizirani algoritam brzog sortiranja je O (nlogn).
Quicksort vs. Merge Sort
U ovom ćemo odjeljku razgovarati o glavnim razlikama između brzog sortiranja i spajanja.
Parametar usporedbe Brzo sortiranje Spajanje sortiraj pregrađivanje Niz je podijeljen oko pivot elementa i nije nužno uvijek na dvije polovice. Može se podijeliti u bilo kojem omjeru. Niz je podijeljen na dvije polovice (n / 2). Najgora složenost slučaja O (n 2) - u najgorem slučaju potrebno je puno usporedbi. O (nlogn) - isto što i prosječni slučaj Korištenje skupova podataka Ne može dobro raditi s većim skupovima podataka. Dobro funkcionira sa svim skupovima podataka, bez obzira na veličinu. Dodatni prostor Na mjestu - ne treba dodatni prostor. Nije na mjestu - potreban mu je dodatni prostor za pohranu pomoćnog niza. Metoda sortiranja Interno - podaci se sortiraju u glavnoj memoriji. Vanjska - koristi vanjsku memoriju za spremanje nizova podataka. Učinkovitost Brži i učinkovitiji za popise malih veličina. Brzo i učinkovito za veće popise. Nizovi / povezani popisi Preferira se za nizove. Dobro funkcionira za povezane popise.
Zaključak
Kao što i samo ime govori, quicksort je algoritam koji sortira popis brzo od bilo kojeg drugog algoritma za sortiranje. Baš kao sortiranje spajanjem, brzo sortiranje također usvaja strategiju podijeli i osvoji.
Kao što smo već vidjeli, korištenjem brzog sortiranja dijelimo popis na podnizove pomoću pivot elementa. Tada se ti pod-nizovi neovisno sortiraju. Na kraju algoritma, čitav je niz u potpunosti sortiran.
Quicksort je brži i učinkovito djeluje na sortiranje struktura podataka. Quicksort je popularan algoritam za sortiranje i ponekad je čak poželjniji od algoritma za spajanje.
U sljedećem uputstvu detaljno ćemo razgovarati o sortiranju školjki.
=> Ovdje pripazite na jednostavne serije obuke za C ++.
Preporučena literatura
- MongoDB metoda sortiranja () s primjerima
- Unix naredba za sortiranje sa sintaksom, opcijama i primjerima
- Spoji sortiranje u C ++ s primjerima
- Sortiranje hrpe u C ++ s primjerima
- Razvrstavanje ljuske na C ++ s primjerima
- Sortiranje odabira na C ++ s primjerima
- Razvrstavanje mjehurića na C ++ s primjerima
- Sortiranje umetanja u C ++ s primjerima
