Se on Divide & Conquer -tyyppinen algoritmi.
Jakaa: Järjestä elementit uudelleen ja jaa taulukot kahdeksi alitaulukoksi ja elementiksi haun välissä niin, että jokainen vasemman alitaulukon elementti on pienempi tai yhtä suuri kuin keskimääräinen elementti ja jokainen oikean alitaulukon elementti on suurempi kuin keskimmäinen elementti.
Valloittaa: Lajittele rekursiivisesti kaksi alitaulukkoa.
Yhdistää: Yhdistä jo lajiteltu matriisi.
Algoritmi:
QUICKSORT (array A, int m, int n) 1 if (n > m) 2 then 3 i ← a random index from [m,n] 4 swap A [i] with A[m] 5 o ← PARTITION (A, m, n) 6 QUICKSORT (A, m, o - 1) 7 QUICKSORT (A, o + 1, n)
Osioalgoritmi:
Osioalgoritmi järjestää alitaulukot uudelleen paikkaan.
PARTITION (array A, int m, int n) 1 x ← A[m] 2 o ← m 3 for p ← m + 1 to n 4 do if (A[p] <x) 1 5 6 7 8 then o ← + swap a[o] with a[p] a[m] return < pre> <p> <strong>Figure: shows the execution trace partition algorithm</strong> </p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort.webp" alt="DAA Quick sort"> <h3>Example of Quick Sort: </h3> <pre> 44 33 11 55 77 90 40 60 99 22 88 </pre> <p>Let <strong>44</strong> be the <strong>Pivot</strong> element and scanning done from right to left</p> <p>Comparing <strong>44</strong> to the right-side elements, and if right-side elements are <strong>smaller</strong> than <strong>44</strong> , then swap it. As <strong>22</strong> is smaller than <strong>44</strong> so swap them.</p> <pre> <strong>22</strong> 33 11 55 77 90 40 60 99 <strong>44</strong> 88 </pre> <p>Now comparing <strong>44</strong> to the left side element and the element must be <strong>greater</strong> than 44 then swap them. As <strong>55</strong> are greater than <strong>44</strong> so swap them.</p> <pre> 22 33 11 <strong>44</strong> 77 90 40 60 99 <strong>55</strong> 88 </pre> <p>Recursively, repeating steps 1 & steps 2 until we get two lists one left from pivot element <strong>44</strong> & one right from pivot element.</p> <pre> 22 33 11 <strong>40</strong> 77 90 <strong>44</strong> 60 99 55 88 </pre> <p> <strong>Swap with 77:</strong> </p> <pre> 22 33 11 40 <strong>44</strong> 90 <strong>77</strong> 60 99 55 88 </pre> <p>Now, the element on the right side and left side are greater than and smaller than <strong>44</strong> respectively.</p> <p> <strong>Now we get two sorted lists:</strong> </p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-2.webp" alt="DAA Quick sort"> <p>And these sublists are sorted under the same process as above done.</p> <p>These two sorted sublists side by side.</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-3.webp" alt="DAA Quick sort"> <br> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-4.webp" alt="DAA Quick sort"> <h3>Merging Sublists:</h3> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-5.webp" alt="DAA Quick sort"> <p> <strong> SORTED LISTS</strong> </p> <p> <strong>Worst Case Analysis:</strong> It is the case when items are already in sorted form and we try to sort them again. This will takes lots of time and space.</p> <h3>Equation:</h3> <pre> T (n) =T(1)+T(n-1)+n </pre> <p> <strong>T (1)</strong> is time taken by pivot element.</p> <p> <strong>T (n-1)</strong> is time taken by remaining element except for pivot element.</p> <p> <strong>N:</strong> the number of comparisons required to identify the exact position of itself (every element)</p> <p>If we compare first element pivot with other, then there will be 5 comparisons.</p> <p>It means there will be n comparisons if there are n items.</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-6.webp" alt="DAA Quick sort"> <h3>Relational Formula for Worst Case:</h3> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-7.webp" alt="DAA Quick sort"> <h3>Note: for making T (n-4) as T (1) we will put (n-1) in place of '4' and if <br> We put (n-1) in place of 4 then we have to put (n-2) in place of 3 and (n-3) <br> In place of 2 and so on. <p>T(n)=(n-1) T(1) + T(n-(n-1))+(n-(n-2))+(n-(n-3))+(n-(n-4))+n <br> T (n) = (n-1) T (1) + T (1) + 2 + 3 + 4+............n <br> T (n) = (n-1) T (1) +T (1) +2+3+4+...........+n+1-1</p> <p>[Adding 1 and subtracting 1 for making AP series]</p> <p>T (n) = (n-1) T (1) +T (1) +1+2+3+4+........ + n-1 <br> T (n) = (n-1) T (1) +T (1) + <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-8.webp" alt="DAA Quick sort">-1</p> <p> <strong>Stopping Condition: T (1) =0</strong> </p> <p>Because at last there is only one element left and no comparison is required.</p> <p>T (n) = (n-1) (0) +0+<img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-8.webp" alt="DAA Quick sort">-1</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-9.webp" alt="DAA Quick sort"> <p> <strong>Worst Case Complexity of Quick Sort is T (n) =O (n<sup>2</sup>)</strong> </p> <h3>Randomized Quick Sort [Average Case]:</h3> <p>Generally, we assume the first element of the list as the pivot element. In an average Case, the number of chances to get a pivot element is equal to the number of items.</p> <pre> Let total time taken =T (n) For eg: In a given list p 1, p 2, p 3, p 4............pn If p 1 is the pivot list then we have 2 lists. I.e. T (0) and T (n-1) If p2 is the pivot list then we have 2 lists. I.e. T (1) and T (n-2) p 1, p 2, p 3, p 4............pn If p3 is the pivot list then we have 2 lists. I.e. T (2) and T (n-3) p 1, p 2, p 3, p 4............p n </pre> <p>So in general if we take the <strong>Kth</strong> element to be the pivot element.</p> <p> <strong>Then,</strong> </p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-10.webp" alt="DAA Quick sort"> <p>Pivot element will do n comparison and we are doing average case so,</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-11.webp" alt="DAA Quick sort"> <p> <strong>So Relational Formula for Randomized Quick Sort is:</strong> </p> <pre> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-12.webp" alt="DAA Quick sort"> = n+1 +<img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-13.webp" alt="DAA Quick sort">(T(0)+T(1)+T(2)+...T(n-1)+T(n-2)+T(n-3)+...T(0)) <br> = n+1 +<img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-13.webp" alt="DAA Quick sort">x2 (T(0)+T(1)+T(2)+...T(n-2)+T(n-1)) </pre> <pre> n T (n) = n (n+1) +2 (T(0)+T(1)+T(2)+...T(n-1)........eq 1 </pre> <p>Put n=n-1 in eq 1</p> <pre> (n -1) T (n-1) = (n-1) n+2 (T(0)+T(1)+T(2)+...T(n-2)......eq2 </pre> <p>From eq1 and eq 2</p> <p>n T (n) - (n-1) T (n-1)= n(n+1)-n(n-1)+2 (T(0)+T(1)+T(2)+?T(n-2)+T(n-1))-2(T(0)+T(1)+T(2)+...T(n-2)) <br> n T(n)- (n-1) T(n-1)= n[n+1-n+1]+2T(n-1) <br> n T(n)=[2+(n-1)]T(n-1)+2n <br> n T(n)= n+1 T(n-1)+2n</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-14.webp" alt="DAA Quick sort"> <p>Put n=n-1 in eq 3</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-15.webp" alt="DAA Quick sort"> <p>Put 4 eq in 3 eq</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-16.webp" alt="DAA Quick sort"> <p>Put n=n-2 in eq 3</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-17.webp" alt="DAA Quick sort"> <p>Put 6 eq in 5 eq</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-18.webp" alt="DAA Quick sort"> <p>Put n=n-3 in eq 3</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-19.webp" alt="DAA Quick sort"> <p>Put 8 eq in 7 eq</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-20.webp" alt="DAA Quick sort"> <br> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-21.webp" alt="DAA Quick sort"> <p>From 3eq, 5eq, 7eq, 9 eq we get</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-22.webp" alt="DAA Quick sort"> <br> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-23.webp" alt="DAA Quick sort"> <p>From 10 eq</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-24.webp" alt="DAA Quick sort"> <p>Multiply and divide the last term by 2</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-25.webp" alt="DAA Quick sort"> <p> <strong>Is the average case complexity of quick sort for sorting n elements.</strong> </p> <p> <strong>3. Quick Sort [Best Case]:</strong> In any sorting, best case is the only case in which we don't make any comparison between elements that is only done when we have only one element to sort.</p> <img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-26.webp" alt="DAA Quick sort"> <hr></h3></x)>
Antaa 44 ole Pivot elementti ja skannaus tehdään oikealta vasemmalle
Vertaamalla 44 oikeanpuoleisiin elementteihin, ja jos oikeanpuoleiset elementit ovat pienempi kuin 44 , vaihda se sitten. Kuten 22 on pienempi kuin 44 joten vaihda ne.
<strong>22</strong> 33 11 55 77 90 40 60 99 <strong>44</strong> 88
Nyt vertaillaan 44 vasemmalle sivuelementille ja elementin tulee olla suurempi kuin 44 ja vaihda ne. Kuten 55 ovat suurempia kuin 44 joten vaihda ne.
22 33 11 <strong>44</strong> 77 90 40 60 99 <strong>55</strong> 88
Rekursiivisesti toistaen vaiheita 1 ja 2, kunnes saamme kaksi listaa, joista toinen on jäljellä pivot-elementistä 44 & yksi oikealle pivot-elementistä.
22 33 11 <strong>40</strong> 77 90 <strong>44</strong> 60 99 55 88
Vaihda 77:ään:
22 33 11 40 <strong>44</strong> 90 <strong>77</strong> 60 99 55 88
Nyt oikealla ja vasemmalla puolella oleva elementti on suurempi ja pienempi kuin 44 vastaavasti.
Nyt saamme kaksi lajiteltua luetteloa:
Ja nämä alaluettelot lajitellaan samalla prosessilla kuin edellä.
Nämä kaksi lajiteltua alaluetteloa vierekkäin.
Alaluetteloiden yhdistäminen:
LAJITTELUT LISTAT
Pahimman tapauksen analyysi: Näin on silloin, kun tuotteet ovat jo lajiteltuina ja yritämme lajitella ne uudelleen. Tämä vie paljon aikaa ja tilaa.
Yhtälö:
T (n) =T(1)+T(n-1)+n
T (1) on pivot-elementin käyttämä aika.
T (n-1) on jäljellä olevan elementin, paitsi pivot-elementin, kuluma aika.
N: Vertailujen määrä, joka vaaditaan itsensä tarkan sijainnin tunnistamiseksi (jokainen elementti)
Jos vertaamme ensimmäistä elementtipivotia muihin, vertailuja on viisi.
Se tarkoittaa, että vertailuja on n, jos kohteita on n.
Suhdekaava pahimpaan tapaukseen:
Huomautus: jos T (n-4):stä tehdään T (1), laitamme (n-1):n 4:n tilalle ja jos
Laitamme (n-1) luvun 4 tilalle, sitten meidän on asetettava (n-2) luvun 3 tilalle ja (n-3)
2:n tilalle ja niin edelleen.
T(n)=(n-1) T(1) + T(n-(n-1))+(n-(n-2))+(n-(n-3))+(n-(n) n-4))+n
T (n) = (n-1) T (1) + T (1) + 2 + 3 + 4+............n
T (n) = (n-1) T (1) +T (1) +2+3+4+........+n+1-1
[1 lisääminen ja 1 vähentäminen AP-sarjaa varten]
T (n) = (n-1) T (1) +T (1) +1+2+3+4+........ + n-1
T (n) = (n-1) T (1) +T (1) + 
-1
Pysäytysehto: T (1) =0
Koska vihdoinkin jäljellä on vain yksi elementti, eikä vertailua tarvita.
T (n) = (n-1) (0) +0+ -1
Pikalajittelun pahimman tapauksen monimutkaisuus on T (n) =O (n2)
Satunnaistettu pikalajittelu [keskimääräinen tapaus]:
Yleensä oletetaan, että luettelon ensimmäinen elementti on pivot-elementti. Keskimääräisessä tapauksessa mahdollisuuksia saada pivot-elementti on yhtä suuri kuin kohteiden lukumäärä.
Let total time taken =T (n) For eg: In a given list p 1, p 2, p 3, p 4............pn If p 1 is the pivot list then we have 2 lists. I.e. T (0) and T (n-1) If p2 is the pivot list then we have 2 lists. I.e. T (1) and T (n-2) p 1, p 2, p 3, p 4............pn If p3 is the pivot list then we have 2 lists. I.e. T (2) and T (n-3) p 1, p 2, p 3, p 4............p n
Joten yleensä, jos otamme Kth elementti pivot-elementiksi.
Sitten,
Pivot-elementti tekee n vertailun ja teemme keskimääräisen tapauksen niin,
Joten satunnaistetun pikalajittelun relaatiokaava on:
<img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-12.webp" alt="DAA Quick sort"> = n+1 +<img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-13.webp" alt="DAA Quick sort">(T(0)+T(1)+T(2)+...T(n-1)+T(n-2)+T(n-3)+...T(0)) <br> = n+1 +<img src="//techcodeview.com/img/daa-tutorial/50/quick-sort-13.webp" alt="DAA Quick sort">x2 (T(0)+T(1)+T(2)+...T(n-2)+T(n-1))
n T (n) = n (n+1) +2 (T(0)+T(1)+T(2)+...T(n-1)........eq 1
Laita n=n-1 yhtälöön 1
(n -1) T (n-1) = (n-1) n+2 (T(0)+T(1)+T(2)+...T(n-2)......eq2
Yhtälöistä 1 ja 2
n T(n) - (n-1) T (n-1) = n(n+1)-n(n-1)+2 (T(0)+T(1)+T(2)+? T(n-2)+T(n-1))-2(T(0)+T(1)+T(2)+...T(n-2))
n T(n)-(n-1) T(n-1)= n[n+1-n+1]+2T(n-1)
n T(n)=[2+(n-1)]T(n-1)+2n
n T(n) = n+1 T(n-1)+2n
kuinka palauttaa taulukko java
Laita n=n-1 yhtälöön 3
Laita 4 ekv. 3 ekv
Laita n=n-2 yhtälöön 3
Laita 6 ekv. 5 ekv
Laita n=n-3 yhtälöön 3
Laita 8 ekv. 7 ekv
3 ekv., 5 ekv, 7 ekv, 9 eq saamme
10 ekv
Kerro ja jaa viimeinen termi 2:lla
Onko nopean lajittelun keskimääräinen tapausten monimutkaisuus n elementin lajittelulle.
3. Pikalajittelu [paras tapaus]: Missä tahansa lajittelussa paras tapaus on ainoa tapaus, jossa emme tee vertailua elementtien välillä, mikä tehdään vain, kun meillä on vain yksi lajiteltava elementti.
