מיון מהיר (Quick Sort)

Quick Sort - מיון מהיר. גם אלגוריתם זה הינו רקורסיבי ופועל בשיטת הפרד ומשול. האלגוריתם בוחר איבר אקראי מהמערך (נקרא pivot), ומסדר את כל האיברים (ע”י השוואה) כך שהאיברים הגדולים מאיבר הציר (איבר ה piviot) יופיעו אחריו (בצד הימיני של המערך) והאיברים הקטנים, לפניו (בצד השמאלי של המערך).

לאחר מכן האלגוריתם מבצע את אותה הפעולה באופן רקורסיבי, ז”א על החלק הימני (החלק של האיברים הגדולים מאיבר הציר) ועל החלק השמאלי (החלק של האיברים הקטנים מאיבר הציר). כמובן שבכל חלק הוא בוחר איבר ציר (pivot) חדש, וכך הלאה עד אשר ישנו איבר אחד (זהו תנאי העצירה).

 

עקרון האלגוריתם

  • אם ישנו יותר מאיבר אחד במערך בצע:
  • סדר את כל האיברים כך שהאיברים הגדולים מאיבר הציר יופיעו אחריו, והאיברים הקטנים ממנו לפניו.
  • חזור רקורסיבית על החלק השמאלי של המערך.
  • חזור רקורסיבית על החלק הימיני של המערך.

 

הקוד של האלגוריתם בפסאודו קוד

PARTITION (A, p, r)
x <- A[r]
i <- p -1
for (j <- 1 to r - 1) do
    if (A[j] <= x)
        i <- i +1
        exchange A[i] <-> A[j]
exchange A[i + 1] <-> A[r]
return i + 1

QUICKSORT (A, p, r)
if (p < r)
    q <- PARTITION (A, p, r)
    QUICKSORT (A, p, q - 1)
    QUICKSORT(A, q + 1, r)
Quick Sort Animation

להלן אנימציה (בצד שמאל) של האלגוריתם בפעולה על מערך, כשהמערך ההתחלתי הוא {4 ,2, 7, 8, 1, 3, 5, 6}, והמערך המתקבל בסוף הוא {8, 7, 6, 5, 4, 3, 2, 1}.

 

הסבר מופשט:
האלגוריתם (מיון מהיר - Quick Sort) מיישם את הפרדיגמה שהכרנו, הפרד ומשול. אך בניגוד למיון מיזוג (Merge Sort), אנו לא מחלקים את המערך לשני חלקים (כמעט) שווים, אלא בוחרים איבר (pivot) אקראי ומחלקים בצורה כזו שהאיברים הקטנים ממנו נשלחים לחלקו השמאלי והאיברים הגדולים ממנו נשלחים אל חלקו הימני.

שימו לב כי באלגוריתם זה הצירוף הוא טריוואלי, וכל העבודה מתבצעת בשלב ההפרדה (במתודה Partition). בנוסף, מכיוון ששגרת (מתודה) החלוקה תלויה בבחירת איבר הציר (pivot), לבחירת איבר זה יכולה להיות השפעה גדולה על ביצוע האלגוריתם, ולכן נהוג להפעיל שגרת Random על המערך (לפני הקריאה למיון מהיר).

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים:

  1. נקבל מערך: { 8, 10, 5, 1, 7, 3 }. אנו מתחילים במתודה QUICKSORT, כש A זהו המצביע למערך, p הוא משתנה המצביע לתא הראשון במערך (1), ו r זהו המצביע לתא האחרון במערך (6).
  2. שורה 2: (השורה הראשונה בפונ’ נועדה לבדיקה שלא חרגנו מגבולות המערך, או שלא בדקנו כבר את כולו), לכן נבדוק אם p<r (ז”א 1 קטן מ-6), התנאי מתקיים ולכן ניכנס:
  3. שורה 3: נכניס את partition ל q. המתודה partition תבחר את איבר הציר (pivot). באלגו’ הזה יהיה [A[r (נשמר במשתנה x), ותעביר את כל האיברים הקטנים ממנו לצד שמאל (ז”א תשאיר אותם איפה שהם), ואת האיברים הגדולים ממנו לצד ימין (אחריו), וכעת המערך יראה כך: { 10, 8, 5, 1, 7, 3 }, partition מחזירה 5, ז”א q=5.
  4. שורה 4: נבצע קריאה לעצמנו מ p (שהוא 1) עד q-1 (שהוא 4):
    • שורה 2: אם p<r (ז”א 1 קטן מ-4), התנאי מתקיים ולכן ניכנס:
    • שורה 3: partition תחזיר 3, ולכן q=3, וכעת המערך יראה כך: { 10, 8, 7, 5, 1, 3 }.
    • שורה 4: שוב נקרא לעצמנו מ p (שהוא 1) עד q-1 (שהוא 2):
    • שורה 2: אם p<r (ז”א 1 קטן מ-2), התנאי מתקיים ולכן ניכנס:
    • שורה 3: partition תחזיר 2, ולכן q=2, וכעת המערך יראה כך: { 10, 8, 7, 5, 3, 1 }.
    • שורה 4: שוב נקרא לעצמנו מ p (שהוא 1) עד q-1 (שהוא 1):
      • שורה 2: אם p<r (ז”א 1 קטן מ-1), התנאי לא מתקיים ולכן ניצא.
    • שורה 5: נקרא לעצמנו מ q+1 (שהוא 3) עד r (שהוא 4):
      • שורה 2: אם p<r (ז”א 3 קטן מ-4), התנאי מתקיים:
      • שורה 3: partition תחזיר 2, ולכן q=2, וכעת המערך יראה כך: { 10, 8, 7, 5, 3, 1 }.
      • שורה 4: שוב נקרא לעצמנו מ p (שהוא 3) עד q-1 (שהוא 2):
        • שורה 2: אם p<r (ז”א 3 קטן מ-2), התנאי לא מתקיים ולכן ניצא.
      • שורה 5: נקרא לעצמנו מ q+1 (שהוא 4) עד r (שהוא 4):
        • שורה 2: אם p<r (ז”א 4 קטן מ-4), התנאי לא מתקיים ולכן ניצא.
          • שורה 5: נקרא לעצמנו מ q+1 (שהוא 4) עד r (שהוא 4): <ul>
    • שורה 2: אם p<r (ז”א 4 קטן מ-4), התנאי לא מתקיים ולכן ניצא.
  5. שורה 5: נקרא לעצמנו מ q+1 (שהוא 6) עד r (שהוא 6):
    • שורה 1: אם p<r (ז”א 6 קטן מ6), התנאי לא מתקיים ולכן ניצא.

סיבוכיות זמן ריצה: (O(n^2 שימו לב, במקרה הממוצע זמן הריצה של האלגוריתם הוא: ((O(nlg(n. אלגוריתם זה מתאפיין בכך שלרוב הקלטים הזמן הממוצע הוא זה שיתקבל, ולכן כדי להעלות את הסיכוי לקבלת הזמן הממוצע נהוג לבצע שגרת Random על הקלט, על מנת להטיב את הסיכויים לקבלת קלט ממוצע.
סיבוכיות מקום: (O(n.