מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/מיון הכנסה ומיזוג/תרגילים/מציאת מספר היפוכים/תשובה
1
[עריכה]במערך[2, 3, 8, 6, 1]
ישנם חמשת ההיפוכים הבאים:
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, ולכן יש להוכיח רק את חלקו השני.
נניח שאחת משורות 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
יכיל את מספר ההחלפות, כפי שמראה המשפט הבא.
משפט: בסיום המיון, המשתנה |
הוכחה: ההוכחה היא באינדוקציה על אורך המערך. נוכיח שבקריאה לMerge-ּSort-Count-Inversions
במערך שארכו , מספר ההפכים במערך מיתוסף לinv
.
(בסיס האינדוקציה) אם אורך המערך הוא 0 או 1, אז שורה 2 של IMerge-ּSort-Count-Inversions
תצא ישר. inv
לא ישתנה מערכו ההתחלתי של 0, בדיוק כפי שאמור להיות (אין הפכים במערך ריק או במערך בעל איבר יחיד).
(מעבר האינדוקציה) נניח שאורך המערך גדול (ממש) מ1. יש שלושה סוגי הפכים אפשריים במערך:
- הפכים בין איברים בחציו השמאלי לבין עצמם
- הפכים בין איברים בחציו הימני לבין עצמם
- הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני
כל אלו בהכרח מחושבים נכון:
- הפכים בין איברים בחציו השמאלי לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 4 של
Inversions-Imp
. - הפכים בין איברים בחציו הימני לבין עצמם מיתוספים נכון (עפ"י הנחת האינדוקציה) בשורה 5 של
Inversions-Imp
. - הפכים בין איברים בחציו השמאלי לבין איברים בחציו הימני מחושבים נכון בפונקציה
Merge-Count-Inversions
, כפי שהוכחנו קודם. אמנם הפונקציה אינה נקראת על חלקי המערך המקוריים, אלא על פרמוטציות שלהם (שהרי 4 ו5 ממיינות אותם), אך לפרמוטציות בהכרח אותו מספר ההפכים אחד בייחס לשני.
קל לראות שהאלגוריתם עובד בזמן - ההוכחה זהה לזו של ניתוח הסיבוכיות במיון מיזוג.