מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/Quicksort

מתוך ויקיספר, אוסף ספרי הלימוד והמדריכים החופשי.

דף זה עוסק באלגוריתם המיון quicksort - אלגוריתם מיון (אקראי) שעובד מצוין ברוב המקרים. בפועל, Quicksort עובד במהירות רבה יותר מאלגוריתמי המיון האחרים שלמדנו.

כדאי לדעת: בספר הקורס, הפרק "Quicksort" דן בנושא זה.

מימוש C++ std::sort

[עריכה] הרעיון הבסיסי

בתרשים הבא, A מראה מערך שברצוננו למיין בתחום שבין b‏ (begining)‏ לe‏ (end)‏. נבחר ערך כלשהו מהמערך, נניח 4, ונזיז כל דבר קטן מ4 לצד השמאלי של המערך, וכל דבר גדול או שווה ל4 לצד הימני של המערך. פעולה זו נקראת partitioning.

המערך בB אינו ממוין, אך הוא "קרוב יותר" להיות ממוין, בכך שלפחות הוא ממוין עפ"י הקריטריון "קטן מ4". כדי למיין את המערך, נפעיל אותו הדבר עבור כ"א מהחלק השמאלי והימני של המערך.

כדאי לדעת: מיון Quicksort משתמש ברעיון divide-and-conquer (הפרד ומשול) : כדי לפתור בעיה "גדולה" (מיון מערך גדול), משתמשים בפתרון בעיות "קטנות" (מיון מערכים קטנים יותר). כבר ראינו רעיון זה בחיפוש בינרי ומיון מיזוג.

[עריכה] Partitioning

להלן הפסוודו-קוד שמבצע את פעולת הpartition:

# Partitions an array (Values) between begining (b) and end (e) indexes.
# Returns the partition index p (b <= r < e).
# If v == Values[b] originally, then after calling this function:
#     any value in Values[b, ..., p] is <= v,
#     any value in Values[p + 1, ..., e] is >= v
Partition(Values, b, e)
1      v = Values[b]
 
2      l = b - 1
3      r = e + 1
 
4      while True            
5              do
6                      --r
7              while value < Values[r]
 
8              do
9                      ++l
10             while value > Values[l]
 
11             if l >= r
12                     return r                       
 
13             # Exchange Values[l] with Values[r]
14             Values[l] <-> Values[r]

ראשית, 2 ו3 קובעים את l‏ (left)‏ וr‏ (right)‏ בדיוק מעבר לb‏ (begining)‏ וe‏ (end).‏ 5-7 מזיזות את r לשמאל כל עוד הוא עובר על איברים גדולים מv ; באופן דומה, 8-10 מזיזות את l ימינה כל עוד הוא עובר על איברים קטנים או שווים לv. אם l \lt r, אז הערכים מוחלפים; אחרת, הpartition מסתיים בr.

כדאי לדעת: Quicksort עובד כ"כ טוב בפועל בגלל הפשטות של5-7 ו8-10.

[עריכה] האלגוריתם

להלן האלגוריתם שממיין את המערך:

# Sorts an array (Values) from a begining index (b) to 
#     an end index (e), through successive partitioning.
Quicksort(Values, b, e)
1      if b ≥ e
2              return
 
        # Choose a random number between b and e.
3      r = Random(b, e)
        # Exchange Values[b] with Values[r]
4      Values[b] <-> Values[r]       
 
5      p = Partition(Values, b, e)
 
6      Quicksort(Values, b, p)
7      Quicksort(Values, p + 1, e)

איזה איבר נבחר לpartition? היות שאין לנו העדפה מיוחדת, 3 בוחרת אינדקס אקראי r, ומשתמשת בערך שבאינדקס זה.

[עריכה] ניתוח

[עריכה] המקרה הגרוע

נניח ש-3 שלQuicksort בוחרת את האיבר הקטן ביותר. (אם היא בוחרת את האיבר הגדול ביותר, מקבלים מקרה סימטרי.) זה יגרום לPartition לחלק את המערך באופן הבא:

לאחר חלוקה עלובה זו, 5 של Quicksort אמנם תיקח רק , אך 6 תפעל על מערך שקטן רק ב1 (באופן די דומה למיון הכנסה).

במקרה זה, לכן, נקבל את נוסחת הנסיגה , שפתרונה .

כלומר המקרה הגרוע (שהוא רע לפחות כמו מקרה זה), הוא .

עכשיו תורך: וודא שהנך יודע להוכיח שמיון Quicksort יעבוד תמיד בזמן (השתמש באינדוקציה).

[עריכה] המקרה הטוב

המקרה הטוב הוא זה שראינו בתרשים הראשון: 3 של Quicksort בוחרת את האיבר האמצעי.

במקרה זה, נקבל את נוסחת הנסיגה , שפתרונה (עפ"י משפט המאסטר) .

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

[עריכה] המקרה בפועל

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

ראשית, נניח ש3 של Quicksort איננה בוחרת את האיבר האמצעי, אלא רק איבר שגדול מעשירית מהאיברים. אז היינו מקבלים את נוסחת הנסיגה , שפתרונה עדיין . זה מראה לנו שחוץ מ"נאחס רע" במיוחד, הרעיון די חסין, וסדר הגדילה בפועל כנראה יהיה קרוב לזה שבמקרה הטוב.

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

1. מיון מיזוג מקצה ומשחרר מערכים, מה שאומר שקבועי סדר הגדילה של ה גדולים למדי, והוא יכול להכשל בשל מיעוט משאבי מערכת (שזה די נורא מבחינת הנדסת תכנה, אגב).
2. Quicksort, לעומת זאת, כמעט שאיננה עושה כלום חוץ מלקרא לPartition, וכבר ראינו עד כמה פשוטה Partition.