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

כדאי לדעת: שאלה זו עוסקת באלגוריתם המיון Quicksort - אלגוריתם מיון מהיר ונפוץ-שימוש מאד. את מהירות האלגוריתם בפועל מקנים הסברים הסתברותיים וטריקים טכניים המייצרים לולאות פשוטות ומהירות מאד. לא נלמד על שני נושאים אלה בקורס (המעוניינים יכולים לקרוא עוד בדף Quicksort.

להלן מימוש אפשרי לפונקציה Partition. הפונקציה מקבלת מערך (Values), אינדקס התחלה (b), ואינדקס סוף (e). אם לפני הקריאה לפונקציה [v == Values[b הוא הערך שישב במקום b, אז הפונקציה תארגן מחדש את המערך ותחזיר ערך p, כך שValues[b, ..., p] מכיל אך ורק איברים קטנים או שווים לv, וValues[p + 1, ..., e] מכיל אך ורק איברים גדולים או שווים לv.

# 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]

שימו לב: אין צורך להתעמק בפסוודו-קוד של Partition. רפרף עליו באופן כללי, ובהמשך הנח את הדברים הבאים: הפונקציה עובדת נכון, דהיינו היא אכן מארגנת את המערך ומחזירה ערך p לפי ההסבר שלמעלה. אם p = Partition(Values, b, e), אז $\displaystyle b\leq p<e$. סיבוכיות הפונקציה היא לינארית באורך הקטע, דהיינו $\displaystyle \Theta (b-e+1)$ (בכל מקרה: טוב או רע).

פונקציית המיון Quicksort מוגדרת בעזרת Partition באופן הבא:

# 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)

בפונקציה זו, 3 בוחרת מספר אקראי בין b לe (לדוגמה, אם b == 1 וe == 3, אז ייבחר $\displaystyle 1$,‏ $\displaystyle 2$,‏ או $\displaystyle 3$). (הנח שסיבוכיות Random היא $\displaystyle O(1)$.) ‏ 4 מחליפה בין איבר אינדקס ההתחלה לאיבר האינדקס האקראי שנבחר. 5 קוראת לPartition שראינו, דבר שמחלק את המערך לשני חלקים. 6 ו7 קוראות רקורסיבית לפונקציה על כל אחד משני החלקים.

1. אנא הוכח את נכונות הפונקציה Quicksort. דהיינו, הוכח שQuicksort(Values, 1, Length(Values)) אכן תמיין את Values.
2. הנח שהפונקציה מופעלת על מערך בעל איברים שונים זה מזה. נניח שאיתרע מזלנו, וRandom(b, e) (בשורה 3) מחזירה תמיד את אינדקס האיבר הקטן ביותר בין b לe. אנא נתח את סיבוכיות המיון במקרה זה.
3. הנח שהפונקציה מופעלת על מערך בעל איברים שונים זה מזה. נניח שאיתרע מזלנו, וRandom(b, e) (בשורה 3) מחזירה תמיד את אינדקס האיבר שחצי מהאיברים בין b לe גדולים ממנו (התעלם משגיאות עיגול). אנא נתח את סיבוכיות המיון במקרה זה.