Tas ir Divide & Conquer tipa algoritms.
Dalīt: Pārkārtojiet elementus un sadaliet masīvus divos apakšmasīvos un elementā starp meklēšanu, lai katrs kreisā apakšmasīva elements būtu mazāks vai vienāds ar vidējo elementu un katrs labā apakšmasīva elements ir lielāks par vidējo elementu.
Iekarot: Rekursīvi kārtojiet divus apakšmasīvus.
Apvienot: Apvienojiet jau sakārtoto masīvu.
Algoritms:
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)
Sadalīšanas algoritms:
Sadalīšanas algoritms pārkārto apakšmasīvus noteiktā vietā.
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)>
Ļaujiet 44 esi Rakurs elements un skenēšana tiek veikta no labās uz kreiso pusi
Salīdzinot 44 uz labās puses elementiem, un, ja labās puses elementi ir mazāks nekā 44 , pēc tam nomainiet to. Kā 22 ir mazāks par 44 tāpēc nomainiet tos.
<strong>22</strong> 33 11 55 77 90 40 60 99 <strong>44</strong> 88
Tagad salīdzina 44 uz kreisās puses elementu un elementam jābūt lielāks nekā 44, tad nomainiet tos. Kā 55 ir lielākas par 44 tāpēc nomainiet tos.
22 33 11 <strong>44</strong> 77 90 40 60 99 <strong>55</strong> 88
Rekursīvi, atkārtojot 1. un 2. darbību, līdz tiek iegūti divi saraksti, kas ir pa kreisi no pivot elementa 44 & viens pa labi no pagrieziena elementa.
22 33 11 <strong>40</strong> 77 90 <strong>44</strong> 60 99 55 88
Apmainīt pret 77:
22 33 11 40 <strong>44</strong> 90 <strong>77</strong> 60 99 55 88
Tagad elements labajā un kreisajā pusē ir lielāks par un mazāks par 44 attiecīgi.
Tagad mēs iegūstam divus sakārtotus sarakstus:
Un šie apakšsaraksti tiek sakārtoti tādā pašā procesā kā iepriekš.
Šie divi apakšsaraksti ir sakārtoti blakus.
Apakšsarakstu sapludināšana:
KĀRTOTI SARAKSTI
Sliktākā gadījuma analīze: Tas ir gadījums, kad preces jau ir sakārtotas un mēs cenšamies tās kārtot vēlreiz. Tas prasīs daudz laika un vietas.
Vienādojums:
T (n) =T(1)+T(n-1)+n
T (1) ir laiks, ko aizņem pagrieziena elements.
T (n-1) ir laiks, ko aizņem atlikušais elements, izņemot pagrieziena elementu.
N: salīdzinājumu skaits, kas nepieciešams, lai noteiktu precīzu tā atrašanās vietu (katru elementu)
Ja salīdzinām pirmo elementu pivot ar citu, tad būs 5 salīdzinājumi.
Tas nozīmē, ka būs n salīdzinājumi, ja ir n vienumi.
Relāciju formula sliktākajam gadījumam:
Piezīme: lai T (n-4) padarītu par T (1), mēs ievietosim (n-1) '4' vietā un, ja
Mēs ieliekam (n-1) 4 vietā, tad mums ir jāievieto (n-2) 3 vietā un (n-3)
2 vietā un tā tālāk.
T(n)=(n-1) T(1) + T(n-(n-1))+(n-(n-2))+(n-(n-3))+(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
[Pieskaitot 1 un atņemot 1, lai izveidotu AP sēriju]
T (n) = (n-1) T (1) +T (1) +1+2+3+4+........ + n-1
T (n) = (n-1) T (1) +T (1) + 
-1
Apstāšanās nosacījums: T (1) =0
Jo beidzot ir palicis tikai viens elements un nav nepieciešams salīdzinājums.
T (n) = (n-1) (0) +0+ -1
Ātrās kārtošanas sliktākā gadījuma sarežģītība ir T (n) = O (n2)
Randomizēta ātrā kārtošana [vidējais gadījums]:
Parasti mēs pieņemam pirmo saraksta elementu kā pivot elementu. Vidējā gadījumā iespēju skaits iegūt pivot elementu ir vienāds ar vienumu skaitu.
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
Tātad kopumā, ja mēs ņemam Kth elementam jābūt pagrieziena elementam.
Tad
Rakurselements veiks n salīdzināšanu, un mēs to darām vidējos gadījumos,
Tātad relāciju formula nejaušai ātrai šķirošanai ir:
<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
Vienādojumā 1 ielieciet n=n-1
(n -1) T (n-1) = (n-1) n+2 (T(0)+T(1)+T(2)+...T(n-2)......eq2
No vienādojuma 1 un vienādojuma 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
java int, lai char
Ielieciet n=n-1 vienādojumā 3
Ievietojiet 4 ekv. 3 ekv
Ielieciet n=n-2 vienādojumā 3
Ievietojiet 6 ekv. 5 ekv
Ielieciet n=n-3 vienādojumā 3
Ievietojiet 8 ekv. 7 ekv
No 3eq, 5eq, 7eq, 9 eq mēs iegūstam
No 10 ekv
Reiziniet un daliet pēdējo vārdu ar 2
Vai ātrās kārtošanas vidējā gadījuma sarežģītība n elementu šķirošanai.
3. Ātrā kārtošana [labākais gadījums]: Jebkurā kārtošanā labākais gadījums ir vienīgais gadījums, kad mēs neveicam nekādu salīdzinājumu starp elementiem, kas tiek darīts tikai tad, ja mums ir tikai viens kārtojamais elements.
