זהו אלגוריתם מסוג Divide & Conquer.
לחלק: סדר מחדש את האלמנטים ופצל מערכים לשני תת-מערכים ורכיב בין לבין חפש שכל אלמנט במערך המשנה השמאלי קטן או שווה לאלמנט הממוצע וכל אלמנט בתת-מערך הימני גדול מהאלמנט האמצעי.
לִכבּוֹשׁ: באופן רקורסיבי, מיין שני מערכי משנה.
לְשַׁלֵב: שלב את המערך שכבר ממוין.
אַלגוֹרִיתְם:
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)
אלגוריתם מחיצות:
אלגוריתם מחיצות מסדר מחדש את מערכי המשנה במקום.
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)>
לתת 44 להיות ה צִיר אלמנט וסריקה מימין לשמאל
משווה 44 לאלמנטים בצד ימין, ואם אלמנטים בצד ימין כן קטן יותר מאשר 44 , ואז להחליף אותו. כפי ש 22 קטן מ 44 אז תחליף אותם.
<strong>22</strong> 33 11 55 77 90 40 60 99 <strong>44</strong> 88
עכשיו משווים 44 לאלמנט הצד השמאלי והאלמנט חייב להיות גדול יותר מ-44 ואז החליפו אותם. כפי ש 55 גדולים מ 44 אז תחליף אותם.
22 33 11 <strong>44</strong> 77 90 40 60 99 <strong>55</strong> 88
באופן רקורסיבי, חזרה על שלבים 1 ושלבים 2 עד שנקבל שתי רשימות, אחת שנותרה מאלמנט הציר 44 ואחד ממש מאלמנט ציר.
22 33 11 <strong>40</strong> 77 90 <strong>44</strong> 60 99 55 88
החלפה עם 77:
22 33 11 40 <strong>44</strong> 90 <strong>77</strong> 60 99 55 88
כעת, האלמנט בצד ימין ובצד שמאל גדולים וקטנים מ 44 בהתאמה.
כעת אנו מקבלים שתי רשימות ממוינות:
ורשימות המשנה הללו ממוינות באותו תהליך כפי שנעשה לעיל.
שתי רשימות המשנה הללו מיינו זו לצד זו.
מיזוג רשימות משנה:
רשימות ממוינות
ניתוח המקרה הגרוע ביותר: זה המצב כאשר פריטים כבר נמצאים בצורה ממוינת ואנו מנסים למיין אותם שוב. זה לוקח הרבה זמן ומקום.
משוואה:
T (n) =T(1)+T(n-1)+n
T (1) הוא הזמן שלוקח אלמנט ציר.
T (n-1) הוא הזמן שלוקח האלמנט הנותר מלבד אלמנט הציר.
N: מספר ההשוואות הנדרשות כדי לזהות את המיקום המדויק של עצמו (כל אלמנט)
אם נשווה את ציר האלמנט הראשון עם אחר, אז יהיו 5 השוואות.
זה אומר שיהיו n השוואות אם יהיו n פריטים.
נוסחת יחסים למקרה הגרוע ביותר:
הערה: להפיכת T (n-4) כ-T (1) נשים (n-1) במקום '4' ואם
אנחנו שמים (n-1) במקום 4 ואז עלינו לשים (n-2) במקום 3 ו-(n-3)
במקום 2 וכן הלאה.
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
[הוספת 1 והפחתה של 1 ליצירת סדרת AP]
T (n) = (n-1) T (1) +T (1) +1+2+3+4+........ + n-1
T (n) = (n-1) T (1) +T (1) + 
-1
מצב עצירה: T (1) =0
כי סוף סוף נשאר רק אלמנט אחד ואין צורך בהשוואה.
T (n) = (n-1) (0) +0+ -1
המורכבות במקרה הגרוע של מיון מהיר היא T (n) =O (n2)
מיון מהיר אקראי [מקרה ממוצע]:
באופן כללי, אנו מניחים שהאלמנט הראשון ברשימה הוא אלמנט הציר. במקרה ממוצע, מספר הסיכויים לקבל אלמנט ציר שווה למספר הפריטים.
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
אז באופן כללי אם ניקח את Kth אלמנט להיות אלמנט הציר.
לאחר מכן,
אלמנט Pivot יעשה השוואה ואנחנו עושים מקרה ממוצע אז,
אז הנוסחה ההתייחסותית למיון מהיר אקראי היא:
<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
שים n=n-1 בשווה 1
(n -1) T (n-1) = (n-1) n+2 (T(0)+T(1)+T(2)+...T(n-2)......eq2
מ-eq1 ו-eq 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
פרמטר verilog
שים n=n-1 בהשוואה 3
שים 4 eq ב 3 eq
שים n=n-2 בהשוואה 3
שים 6 eq ב 5 eq
שים n=n-3 בהשוואה 3
שים 8 eq ב 7 eq
מ-3eq, 5eq, 7eq, 9 eq אנחנו מקבלים
מ-10 שווים
הכפלו וחלקו את האיבר האחרון ב-2
האם מורכבות המקרה הממוצעת היא מיון מהיר עבור מיון n אלמנטים.
3. מיון מהיר [המקרה הטוב ביותר]: בכל מיון, המקרה הטוב ביותר הוא המקרה היחיד שבו אנחנו לא עושים השוואה בין אלמנטים שנעשית רק כשיש לנו רק אלמנט אחד למיין.
