quick sort c with examples
Quicksort v jeziku C ++ z ilustracijo.
Quicksort je pogosto uporabljen algoritem za razvrščanje, ki izbere določen element, imenovan 'pivot', in razdeli matriko ali seznam, ki ga je treba razvrstiti na dva dela glede na to vrtišče s0, da so elementi, ki so manjši od pivota, levo od seznama in elementi večji od vrtišča so na desni strani seznama.
Tako je seznam razdeljen na dva seznama. Za isto velikost morda ne bodo potrebni pod seznami. Nato se Quicksort rekurzivno pokliče, da razvrsti ta dva seznama.
=> Tukaj si oglejte Perfect Guide za usposabljanje za C ++.
Kaj se boste naučili:
- Uvod
- Splošni algoritem
- Psevdo koda za hitri sortiranje
- Ilustracija
- Primer C ++
- Primer Java
- Analiza kompleksnosti algoritma Quicksort
- 3-smerni Quicksort
- Randomizirana hitra različica
- Quicksort vs Merge Sort
- Zaključek
- Priporočeno branje
Uvod
Quicksort deluje učinkovito in hitreje tudi pri večjih nizih ali seznamih.
V tej vadnici bomo raziskali več o delovanju Quicksorta in nekaj primerov programiranja algoritma quicksort.
Kot vrtilno vrednost lahko izberemo prvo, zadnjo ali srednjo vrednost ali katero koli naključno vrednost. Splošna ideja je, da se na koncu vrtilna vrednost postavi na ustrezen položaj v matriki s premikanjem drugih elementov v levi ali desni.
Splošni algoritem
Splošni algoritem za Quicksort je podan spodaj.
quicksort(A, low, high) begin Declare array A[N] to be sorted low = 1st element; high = last element; pivot if(low Oglejmo si zdaj psevdokodo za tehniko Quicksort.
Psevdo koda za hitri 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 Delovanje algoritma razdeljevanja je na primeru opisano spodaj.
Na tej sliki zadnji element vzamemo za vrtišče. Vidimo lahko, da je matrika zaporedoma razdeljena okoli vrtilnega elementa, dokler nimamo enega samega elementa v matriki.
Zdaj predstavljamo ponazoritev Quicksort spodaj, da bolje razumemo koncept.
Ilustracija
Oglejmo si ponazoritev algoritma hitrega sortiranja. Naslednjo matriko z zadnjim elementom upoštevajte kot vrtišče. Prav tako je prvi element označen z nizkim, zadnji pa z visokim.
brezplačna programska oprema za kopiranje DVD-jev za mac
Iz ilustracije lahko vidimo, da kazalce premikamo visoko in nizko na obeh koncih polja. Kadar nizke točke kažejo na element, ki je večji od vrtišča, in visoke točke na element, ki je manjši od vrtišča, si nato izmenjamo položaje teh elementov in spodnji in visoki kazalnik pomaknemo v svojo smer.
To se naredi, dokler se nizki in visoki kazalci ne prekrižata. Ko se med seboj prekrižata, se vrtilni element postavi v ustrezen položaj in matrika se razdeli na dva dela. Nato se oba podniza razvrstita neodvisno z uporabo hitrega sortiranja rekurzivno.
Primer C ++
Spodaj je predstavljena implementacija algoritma Quicksort v jeziku 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< Izhod:
Vhodno polje
12 23 3 43 51 35 19 45
Niz razvrščen po hitrem vrstnem redu
3 12 19 23 35 43 45 51
Tu imamo nekaj rutin, ki se uporabljajo za particioniranje matrike in rekurzivno klicanje hitrega sortiranja za razvrščanje particije, osnovne funkcije hitrega sortiranja in pomožnih funkcij za prikaz vsebine polja in ustrezno zamenjavo obeh elementov.
Najprej pokličemo funkcijo hitrega sortiranja z vhodno matriko. Znotraj funkcije hitrega sortiranja pokličemo funkcijo particije. V particijski funkciji uporabljamo zadnji element kot vrtilni element matrike. Ko se odločite za vrtišče, je polje razdeljeno na dva dela, nato pa se pokliče funkcija hitrega sortiranja za samostojno razvrščanje obeh podniz.
Ko se vrne funkcija hitrega sortiranja, je matrika razvrščena tako, da je element vrtišča na svojem pravilnem mestu, elementi, ki so manjši od vrtišča, na levi strani vrtišča, elementi, večji od vrtišča, pa na desni strani vrtišča.
Nato bomo v Java implementirali algoritem hitrega sortiranja.
Primer 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 Izhod:
Vhodno polje
12 23 3 43 51 35 19 45
Niz po razvrščanju s hitrim sortiranjem
3 12 19 23 35 43 45 51
Tudi pri implementaciji Jave smo uporabili isto logiko kot pri implementaciji C ++. Zadnji element v matriki smo uporabili, ko sta vrtilna in hitra vrstica izvedena na matriki, da bi vrtilni element postavili na ustrezen položaj.
Analiza kompleksnosti algoritma Quicksort
Čas, ki ga pospeši sortiranje polja, je odvisen od vhodnega polja in strategije ali metode particije.
Če je k število elementov, ki je manjše od vrtišča, in n skupno število elementov, potem lahko splošni čas, ki ga porabi živa sorta, izrazimo na naslednji način:
T (n) = T (k) + T (n-k-1) + O (n)
Tu sta T (k) in T (n-k-1) čas, ki ga zahtevajo rekurzivni klici, O (n) pa čas, potreben za razdelitveni klic.
kateri je najboljši brezplačni požarni zid
Podrobno analizirajmo to časovno zapletenost za hitro sortiranje.
# 1) Najslabši primer : Najslabši primer v tehniki hitrega sortiranja se zgodi večinoma, ko za vrtišče izberemo najnižji ali najvišji element v matriki. (Na zgornji sliki smo za vrtišče izbrali najvišji element). V takem primeru se zgodi najslabši primer, ko je vrsta, ki jo je treba razvrstiti, že razvrščena v naraščajočem ali padajočem vrstnem redu.
Zato se zgornji izraz za celoten čas porabi spremeni kot:
T (n) = T (0) + T (n-1) + O (n) ki se razreši na O (štdva)
# 2) Najboljši primer: Najboljši primer za hitro sortiranje je vedno, če je izbrani vrtilni element sredina polja.
Tako je ponovitev v najboljšem primeru:
funkcionalno preskušanje vs nefunkcionalno preskušanje
T (n) = 2T (n / 2) + O (n) = O (nlogn)
# 3) Povprečni primer: Za analizo povprečnega primera za hitro sortiranje bi morali upoštevati vse permutacije matrike in nato izračunati čas, ki ga potrebuje vsaka od teh permutacij. Na kratko, povprečni čas za hitro sortiranje postane tudi O (nlogn).
Spodaj so navedene različne zapletenosti tehnike Quicksort:
Najslabša časovna zapletenost O (n 2) stabilnost Ni stabilno, saj dva elementa z enakimi vrednostmi ne bosta postavljena v isti vrstni red. Stabilno - v razvrščenem izhodu se bosta v istem vrstnem redu pojavila dva elementa z enakimi vrednostmi. Najboljša časovna zapletenost O (n * log n) Povprečna časovna zapletenost O (n * log n) Zapletenost prostora O (n * log n)
Hitro razvrstitev lahko izvedemo na več različnih načinov, samo tako da spremenimo izbiro vrtilnega elementa (srednji, prvi ali zadnji), vendar se v najslabšem primeru redko zgodi pri hitrem sortiranju.
3-smerni Quicksort
V izvirni tehniki hitrega sortiranja običajno izberemo vrtilni element in nato matriko razdelimo na podniže okoli tega vrtišča, tako da eno podnivo sestavljajo elementi, manjši od vrtišča, drugi pa elementi, večji od vrtišča.
Kaj pa, če izberemo pivot element in je v matriki več kot en element, ki je enak pivot?
Na primer, upoštevajte naslednjo matriko {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Če na tej matriki izvedemo preprosto hitro sortiranje in izberemo 4 kot vrtilni element, bomo popravili le en pojav elementa 4, ostali pa bodo razdeljeni skupaj z drugimi elementi.
Namesto tega, če uporabimo 3-smerno hitro sortiranje, bomo matriko [l ... r] razdelili na tri podniže, kot sledi:
- Matrika [l… i] - Tu je i vrtišče in ta matrika vsebuje elemente, manjše od vrtišča.
- Matrika [i + 1… j-1] - Vsebuje elemente, ki so enaki vrtišču.
- Matrika [j… r] - Vsebuje elemente, večje od vrtišča.
Tako lahko uporabimo trosmerno hitro sortiranje, kadar imamo v matriki več kot en odvečni element.
Randomizirana hitra različica
Tehnika hitrega sortiranja se imenuje tehnika randomiziranega hitrega sortiranja, kadar za izbiro vrtilnega elementa uporabljamo naključne številke. V naključnem hitrem sortiranju se imenuje »osrednji pivot« in matriko deli tako, da ima vsaka stran vsaj ¼ elementov.
Psevdo-koda za naključni hitri razpored je podana spodaj:
// 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 procedure
V zgornji kodi na “randomQuickSort” v 2. koraku izberemo osrednjo vrtišče. V 2. koraku je verjetnost, da je izbrani element osrednji pivot, ½. Zato naj bi se zanka v 2. koraku izvajala dvakrat. Tako je časovna zapletenost za korak 2 v naključnem hitrem sortiranju O (n).
Uporaba zanke za izbiro osrednjega vrtišča ni idealen način za izvajanje naključnega hitrega sortiranja. Namesto tega lahko naključno izberemo element in ga imenujemo osrednja vrtišča ali prerazporedimo elemente polja. Pričakovana najslabša časovna zapletenost algoritma randomiziranega hitrega sortiranja je O (nlogn).
Quicksort vs Merge Sort
V tem poglavju bomo obravnavali glavne razlike med hitrim razvrščanjem in združevanjem.
Primerjalni parameter Hitro razvrščanje Razvrsti združitev razdelitev Matrika je razdeljena okoli vrtilnega elementa in ni nujno, da je vedno na dve polovici. Lahko se razdeli v poljubno razmerje. Matrika je razdeljena na dve polovici (n / 2). Najslabša zapletenost primera O (n 2) - v najslabšem primeru je potrebnih veliko primerjav. O (nlogn) - enako kot v povprečnem primeru Uporaba naborov podatkov Ne more dobro delovati z večjimi nabori podatkov. Dobro deluje z vsemi nabori podatkov, ne glede na velikost. Dodaten prostor Na mestu - ne potrebuje dodatnega prostora. Ni na mestu - potrebuje dodaten prostor za shranjevanje pomožnega polja. Način razvrščanja Notranji - podatki so razvrščeni v glavnem pomnilniku. Zunanji - uporablja zunanji pomnilnik za shranjevanje podatkovnih nizov. Učinkovitost Hitrejši in učinkovitejši za majhne sezname. Hitro in učinkovito za večje sezname. Nizi / povezani seznami Bolj prednostno za nize. Dobro deluje za povezane sezname.
Zaključek
Kot že samo ime pove, je quicksort algoritem, ki seznam hitro razvrsti kot kateri koli drug algoritem za razvrščanje. Tako kot sortiranje z združevanjem tudi hitro razvrščanje sprejme strategijo delitve in osvajanja.
Kot smo že videli, s hitrim razvrščanjem delimo seznam na podniz s pomočjo vrtilnega elementa. Nato se ti podnizi samostojno razvrstijo. Na koncu algoritma je celotno polje popolnoma razvrščeno.
Quicksort je hitrejši in učinkovito deluje za razvrščanje podatkovnih struktur. Quicksort je priljubljen algoritem za razvrščanje in je včasih celo boljši kot algoritem za razvrščanje.
V naslednji vadnici bomo podrobneje razpravljali o razvrščanju Shell.
=> Tukaj bodite pozorni na preprosto vadbeno serijo C ++.
Priporočeno branje
- Metoda sortiranja () MongoDB () s primeri
- Ukaz za razvrščanje Unix s sintakso, možnostmi in primeri
- Združi razvrstitev v jeziku C ++ s primeri
- Razvrstitev kopice v C ++ z primeri
- Razvrstitev lupine v C ++ z primeri
- Izbirno razvrščanje v C ++ z primeri
- Razvrstitev mehurčkov v jeziku C ++ s primeri
- Razvrstitev vstavka v C ++ z primeri