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

1

במערך[2, 3, 8, 6, 1] ישנם חמשת ההיפוכים הבאים:

1. $\displaystyle (1,5)$
2. $\displaystyle (2,5)$
3. $\displaystyle (3,4)$
4. $\displaystyle (3,5)$
5. $\displaystyle (4,5)$

2

כדאי לדעת: הפתרון משתמש ברעיון "divide and conquer", כלומר פתרון בעיות "גדולות" ע"י פתירת בעיות "קטנות" יותר.

הפתרון מתבסס על שינויים קלים במיון מיזוג. ראשית, נתבונן בפסוודו-קוד הבא, שהוא ווריאציה קלה על Merge:

	# A global variable that counts the number of inversions.
1	inv


# Merge and count inversions. 
# Takes two sorted arrays (L, R).
# Returns a sorted array of L ∪ R, and counts how many members
#	of L and R are inverted relative to each other.
Merge-Count-Inversions(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			inv = inv + r - 1
7		else if l > Length(L)
8			Merged[m++] = R[r++]
9		else if L[l] inv = inv + r - 1
10			Merged[m++] = L[l++]
11			inv = inv + r - 1
12		else
13			Merged[m++] = R[r++]

14	return Merged

המשתנה הגלובלי inv (ב1) שומר על מספר ההפכים. הפונקציה Merge-Count-Inversions כמעט זהה לפונקציה Merge שאותה כבר פגשנו, למעט השורות 6 ו11 שנוספו - שורות אלה מעדכנות את inv בכל פעם שנלקח איבר מL.

משפט: אם Merge-Count-Inversions נקראת עם L וR ממוינים כלשהם, אז בסיום הקריאה: הפונקציה מחזירה מערך ממוין של איחוד איבריהם. למשתנה inv נוספו בדיוק מספר ההפכים בין איברי L לאיברי R (כלומר, מספר האיברים בL שגדולים מאיברים בR).

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

נניח שאחת משורות 4 או 9 בוחרת למזג את L[l]. בשלב זה, מספר האיברים שכבר נלקחו מR הוא r - 1, וכל אחד מאיברים אלה קטן בהכרח מL[l], או, במילים אחרות, מרכיב הפך בייחס לL[l]. מצד שני, כל איבר בR שעדיין לא נבחר, בהכרח גדול מL[l], ולכן אינו מרכיב הפך בייחס לL[l]. לכן כשנבחר L[l], הפונקציה מוסיפה לinv בדיוק את מספר ההפכים שהוא חלק מהם. היות שהפונקציה בוחרת בשלב כלשהו כל איבר מL, היא מוסיפה לinv את סך כל ההפכים בין L לR, בדיוק כפי שנטען.

כדי להשלים את הפתרון, פשוט נכתוב שוב פעם את Merge-Sort , אלא שבמקום לקרוא לMerge נקרא לMerge-Count-Inversions:

# Merge sort also counting inversions. 
# Takes an array (Values).
# Returns an array of the same elements, sorted in increasing order; also increases global variable inv 
# 	by the number of inversions.
Merge-Sort-Count-Inversions(Values)
1	if Length(Values) <= 1
2		return Values

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

לפני הקריאה הראשונה לMerge-Sort-Count-Inversions נאפס את המשתנה הגלובאלי inv. בסיום המיון, המשתנה inv יכיל את מספר ההחלפות, כפי שמראה המשפט הבא.

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

הוכחה: ההוכחה היא באינדוקציה על אורך המערך. נוכיח שבקריאה לMerge-ּSort-Count-Inversions במערך שארכו $\displaystyle n$, מספר ההפכים במערך מיתוסף לinv.

(בסיס האינדוקציה) אם אורך המערך הוא 0 או 1, אז שורה 2 של IMerge-ּSort-Count-Inversions תצא ישר. inv לא ישתנה מערכו ההתחלתי של 0, בדיוק כפי שאמור להיות (אין הפכים במערך ריק או במערך בעל איבר יחיד).

(מעבר האינדוקציה) נניח שאורך המערך גדול (ממש) מ1. יש שלושה סוגי הפכים אפשריים במערך:

1. הפכים בין איברים בחציו השמאלי לבין עצמם
2. הפכים בין איברים בחציו הימני לבין עצמם
3. הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני

כל אלו בהכרח מחושבים נכון:

1. הפכים בין איברים בחציו השמאלי לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 4 של Inversions-Imp.
2. הפכים בין איברים בחציו הימני לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 5 של Inversions-Imp.
3. הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני מחושבים נכון בפונקציה Merge-Count-Inversions, כפי שהוכחנו קודם. אמנם הפונקציה אינה נקראת על חלקי המערך המקוריים, אלא על פרמוטציות שלהם (שהרי 4 ו5 ממיינות אותם), אך לפרמוטציות בהכרח אותו מספר ההפכים אחד בייחס לשני.

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