إنها خوارزمية من نوع 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
تي (1) هو الوقت الذي يستغرقه العنصر المحوري.
تي (ن-1) هو الوقت الذي يستغرقه العنصر المتبقي باستثناء العنصر المحوري.
ن: عدد المقارنات المطلوبة لتحديد الموقع الدقيق لنفسه (كل عنصر)
إذا قارنا العنصر المحوري الأول مع العناصر الأخرى، فسيكون هناك 5 مقارنات.
وهذا يعني أنه سيكون هناك n مقارنات إذا كان هناك n من العناصر.
الصيغة العلائقية لأسوأ الحالات:
ملاحظة: لجعل T (n-4) كـ T (1) سنضع (n-1) بدلاً من '4' وإذا
نضع (ن-1) مكان 4 ثم علينا أن نضع (ن-2) مكان 3 و (ن-3)
بدلا من 2 وهكذا.
T(n)=(n-1) T(1) + T(n-(n-1))+(n-(n-2))+(n-(n-3))+(n-( ن-4))+ن
ت (ن) = (ن-1) ت (1) + ت (1) + 2 + 3 + 4+ ........... ن
ت (ن) = (ن-1) ت (1) +ت (1) +2+3+4+..........+ن+1-1
[إضافة 1 وطرح 1 لإنشاء سلسلة AP]
ت (ن) = (ن-1) ت (1) +ت (1) +1+2+3+4+........ + ن-1
ت (ن) = (ن-1) ت (1) +ت (1) + 
-1
حالة التوقف: T (1) =0
لأنه في النهاية لم يتبق سوى عنصر واحد ولا حاجة للمقارنة.
تي (ن) = (ن-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
بشكل عام إذا أخذنا كث العنصر ليكون العنصر المحوري.
ثم،
سيقوم العنصر المحوري بإجراء مقارنة ونحن نقوم بحالة متوسطة لذلك،
لذا فإن الصيغة العلائقية للفرز السريع العشوائي هي:
<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
من مكافئ 1 ومكافئ 2
ن تي (ن) - (ن-1) تي (ن-1)= ن(ن+1)-ن(ن-1)+2 (ت(0)+تي(1)+تي(2)+؟ تي(ن-2)+تي(ن-1))-2(تي(0)+تي(1)+تي(2)+...تي(ن-2))
ن تي(ن)- (ن-1) تي(ن-1)= ن[ن+1-ن+1]+2T(ن-1)
ن تي(ن)=[2+(ن-1)]تي(ن-1)+2ن
ن تي(ن)= ن+1 تي(ن-1)+2ن
اختصارات لوحة المفاتيح لينكس
ضع n=n-1 في المعادلة 3
ضع 4 مكافئ في 3 مكافئ
ضع n=n-2 في المعادلة 3
ضع 6 مكافئ في 5 مكافئ
ضع n=n-3 في المعادلة 3
ضع 8 مكافئ في 7 مكافئ
من 3eq، 5eq، 7eq، 9 مكافئ نحصل عليه
من 10 مكافئ
اضرب الحد الأخير واقسمه على 2
هو متوسط تعقيد الحالة للفرز السريع لفرز العناصر n.
3. الفرز السريع [أفضل حالة]: في أي عملية فرز، أفضل حالة هي الحالة الوحيدة التي لا نقوم فيها بإجراء أي مقارنة بين العناصر والتي تتم فقط عندما يكون لدينا عنصر واحد فقط للفرز.
