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

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

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

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

הרעיון הבסיסי

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

הרעיון הבסיסי של Quicksort.

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

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

Partitioning

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

# Partitions an array (Values) between beginning (b) and end (e) indices.
# 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 v <= Values[r]
	
8		do
9			++l
10		while v >= 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‏ (beginning)‏ וe‏ (end).‏ 5-7 מזיזות את r לשמאל כל עוד הוא עובר על איברים גדולים מv ; באופן דומה, 8-10 מזיזות את l ימינה כל עוד הוא עובר על איברים קטנים או שווים לv. אם l < r, אז הערכים מוחלפים; אחרת, הpartition מסתיים בr.

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

האלגוריתם

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

# Sorts an array (Values) from a beginning 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 אמנם תיקח רק $\displaystyle O(1)$, אך 6 תפעל על מערך שקטן רק ב1 (באופן די דומה למיון הכנסה).

במקרה זה, לכן, נקבל את נוסחת הנסיגה $\displaystyle T(n)=T(n-1)+\Theta (n)$, שפתרונה $\displaystyle \Theta (n^{2})$.

כלומר המקרה הגרוע (שהוא רע לפחות כמו מקרה זה), הוא $\displaystyle \Omega (n^{2})$.

עכשיו תורכם: וודא שהנך יודע להוכיח שמיון Quicksort יעבוד תמיד בזמן $\displaystyle O(n^{2})$ (השתמש באינדוקציה).

המקרה הטוב

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

במקרה זה, נקבל את נוסחת הנסיגה $\displaystyle T(n)=2\cdot T(n/2)+O(n)$, שפתרונה (עפ"י משפט המאסטר) $\displaystyle \Theta (n\cdot \log(n))$.

כדאי לדעת: נשים לב שקיבלנו סדר גדילה של $\displaystyle \Theta (n\cdot \log(n))$, ולכן, לפי מה שראינו בהחסם התחתון על מיון מבוסס השוואות, מדובר בסדר גדילה אופטימלי לבעיה.

המקרה בפועל

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

ראשית, נניח ש3 של Quicksort איננה בוחרת את האיבר האמצעי, אלא רק איבר שגדול מעשירית מהאיברים. אז היינו מקבלים את נוסחת הנסיגה $\displaystyle T(n)=T(n/10)+T(9\cdot n/10)+\Theta (n)$, שפתרונה עדיין $\displaystyle \Theta (n\cdot \log(n))$. זה מראה לנו שחוץ מ"נאחס רע" במיוחד, הרעיון די חסין, וסדר הגדילה בפועל כנראה יהיה קרוב לזה שבמקרה הטוב.

הניתוח המדוייק דורש ידע בהסתברות, ולכן מעתה פשוט נניח שאין לה נאחס רע כ"כ, והיא אכן עובדת בזמן $\displaystyle \Theta (n\cdot \log(n))$. נשווה זאת, אם כן, למיון מיזוג, שלו אותה סיבוכיות:

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

הפרק הקודם: מיון הכנסה ומיזוג

Quicksort

הפרק הבא: החסם התחתון על מיון מבוסס-השוואות