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

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

תבנית:הארה

תבנית:מבנה תבנית

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

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

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

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

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 קובעים את תבנית:קוד בשורה‏ (left)‏ ותבנית:קוד בשורה‏ (right)‏ בדיוק מעבר לתבנית:קוד בשורה‏ (beginning)‏ ותבנית:קוד בשורה‏ (end).‏ 5-7 מזיזות את תבנית:קוד בשורה לשמאל כל עוד הוא עובר על איברים גדולים מתבנית:קוד בשורה ; באופן דומה, 8-10 מזיזות את תבנית:קוד בשורה ימינה כל עוד הוא עובר על איברים קטנים או שווים לתבנית:קוד בשורה. אם תבנית:קוד בשורה, אז הערכים מוחלפים; אחרת, הpartition מסתיים בתבנית:קוד בשורה.

תבנית:הארה

האלגוריתם

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

# 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 בוחרת אינדקס אקראי תבנית:קוד בשורה, ומשתמשת בערך שבאינדקס זה.

ניתוח

המקרה הגרוע

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

המקרה הנאחס.

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

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

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

המקרה הטוב

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

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

תבנית:הארה

המקרה בפועל

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

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

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

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