מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג

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

בעיית המיון.

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

מיון הכנסה

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

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

שלבי מיון הכנסה.

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

שלבי מיון הכנסה - שלב ההכנסה.

פסוודו-קוד

# Insertion sort. 
# Takes an array (Values).
# Sorts the array in increasing order.
Insertion-Sort(Values)
1	for i in [1, ..., Length(Values)]
2		v = Values[i]
		
		# Insert v into the correct position of Values[1, ..., i].
	
3		j = i
4		while j > 1 and Values[j - 1] > v
5			Values[j] = Values[j - 1]			
6			--j
			
7		Values[j] = v

האינדקס i מציין את החלק של Values המכיל i איברים Values בסדר עולה. האינדקס j משמש להזזת האיברים שיש להזיז כדי להכניס את Values[i] למקום המתאים.

נכונות

הוכחה: ההוכחה היא באינדוקציה על i בלולאה 1 - 7 : בסוף האיטרציה ה i,‏ Values[1, ..., i] ממוין.

(בסיס האינדוקציה) עבור i = 1 הלולאה 4-6 איננה מתבצעת, ושום דבר אינו משתנה. Values[1, ..., 1] ממוין באופן טריביאלי.

(מעבר האינדוקציה)

בתחילת האיטרציה i,‏ Values[1, ..., i - 1] ממוין (עפ"י הנחת האינדוקציה). הלולאה 4-6 איננה משנה את הסדר בValues[1, ..., i - 1], היא רק מסיטה את האיברים הגדולים מv, ו7 מכניסה את v בין האיברים הקטנים ממנו לאלה שגדולים ממנו. לכן Values[1, ..., i] ממוין בסיום האיטרציה.

סיבוכיות

נקבע כ$\displaystyle n$ את Length(Values).

משפט: מיון הכנסה פועל בזמן $\displaystyle O(n^{2})$ במקרה הגרוע.

הוכחה: עבור $\displaystyle i$ כלשהו ב3,‏‏ 5-6 מתבצעת לכל היותר $\displaystyle i-1$ פעמים, ו7 פעם אחת. היות שכ"א מהן היא $\displaystyle O(1)$, אז 4-7 היא $\displaystyle O(i)$. בלולאה החיצונית 1-7,‏‏ 2-3 הן $\displaystyle O(1)$,‏ ו$\displaystyle i$ רצה מ$\displaystyle 1$ ל$\displaystyle n$. הסיבוכיות היא, לכן, לכל היותר $\displaystyle \sum _{i=1}^{n}[O(1)+O(i)]=O(n^{2})$ (נזכר שראינו פישוט דומה בדוגמה לשילוב מספר כללים בסדרי גדילה).‏

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

מיון מיזוג

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

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

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

מיזוג מערכים ממויינים

ראשית, הנה הדרך למזג מערכים ממוינים:

# Merge. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R.
Merge(L, R)
1	Merged = Make-Array( Length(L) + Length(R) )
	
2	l = r = m = 1
	
3	while l <= Length(L) or r <= Length(R)
4		if r > Length(R)
5			Merged[m++] = L[l++]
6		else if l > Length(L)
7			Merged[m++] = R[r++]
8		else if L[l] < R[r]
9			Merged[m++] = L[l++]
10		else
11			Merged[m++] = R[r++]

12	return Merged

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

משפט: אם L וR ממוינים, אז Merge מחזירה מערך ממוין של איבריהם.

משפט: נניח שMerge מקבלת שני מערכים בגודל $\displaystyle m$. אז הסיבוכיות הנה $\displaystyle \Theta (m)$.

פסוודו-קוד

נכתוב את אלגוריתם המיון בעזרת אלגוריתם המיזוג:

# Merge sort. 
# Takes an array (Values).
# Returns an array of the same elements, sorted in increasing order.
Merge-Sort(Values)
1	if Length(Values) <= 1
2		return Values

3	mid = ⌊(1 + Length(Values)) / 2⌋
		
4	L = Merge-Sort( Values[1, ... , mid] )
5	R = Merge-Sort( Values[mid + 1, ... , Length(Values)] )
	
6	return Merge(L, R)

נכונות

נוכיח כעת את נכונות מיון מיזוג.

הוכחה: נקבע כ$\displaystyle n$ את Length(Values). ההוכחה היא באינדוקציה על $\displaystyle n$.

(בסיס האינדוקציה) עבור $\displaystyle n=0$ או$\displaystyle n=1$,‏ 1-2 מחזירות פשוט את Values, שבמקרה זה ממוין עפ"י הגדרה.

(מעבר האינדוקציה) נניח שMerge-Sort עובדת לכל $\displaystyle n'<n$. אז 4-5 ממיינות את החצי השמאלי והימני לפי בסיס האינדוקציה (כי הפונקציה פועלת על מערכים קטנים יותר). 6 פועלת לכן על שני מערכים ממוינים, ולכן מחזירה את המערך ממוין.

סיבוכיות

שוב, נקבע כ$\displaystyle n$ את Length(Values).

משפט: מיון מיזוג רץ בזמן $\displaystyle O(n\cdot \log(n))$.

הוכחה: בMerge-Sort,‏ 1-3 הן כ"א $\displaystyle O(1)$, ו6 היא $\displaystyle \Theta (n)$. אם $\displaystyle T(n)$ הוא זמן הריצה, אז כ"א מ4-5 היא $\displaystyle T(n/2)$, ולכן $\displaystyle T(n)=2\cdot T(n/2)+O(1)+\Theta (n)$, או, ‏ בצורה אחרת, $\displaystyle T(n)=2\cdot T(n/2)+\Theta (n)$, ומכאן שזמן הריצה הוא $\displaystyle \Theta (n\cdot \log(n))$ (אפשר לראות זאת לפי משפט המאסטר).

הפרק הקודם: מציאת סיבוכיות פסוודו-קוד

מיון הכנסה ומיזוג תרגילים

הפרק הבא: Quicksort