מיון מיזוג - Merge sort

מיון מיזוג - Merge sort#

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

עקרונות הפתרון#

  • נפרק את רשימת הקלט לשני חצאים, ונמיין כל אחד מהם בנפרד.

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

  • לאחר מכן, נרכיב את שתי תתי הרשימות הממויינות ביחד כדי ליצור רשימה ממויינת אחת שלמה.

מיזוג שתי רשימות ממוינות#

כעת נראה כיצד מאחדים שתי רשימות ממוינות לרשימה ממוינת אחת. כדי לבצע זאת בצורה יעילה, ניעזר בכך שהרשימות כבר ממוינות.

עיצרו וחישבו: בהינתן שתי רשימות ממוינות a ו־b, מאילו איברים עשוי להגיע הערך המינימלי ברשימה המאוחדת?

כיוון שכל אחת מהרשימות כבר ממוינת, האיבר הקטן ביותר בכל אחת מהן נמצא בתחילתה — כלומר באינדקס 0.
איננו יודעים מי מהשניים קטן יותר, a[0] או b[0], אך ברור שאחד מהם יהיה הערך המינימלי ברשימה המאוחדת.

תיאור האלגוריתם#

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

התהליך נמשך עד שאחת הרשימות “הסתיימה” - כל האיברים בה הועתקו לרשימה המאוחדת. אחר כך נוכל להעתיק את שארית האיברים מהרשימה השניה לרשימת הפלט.

מימוש מיזוג שתי רשימות ממויינות בפייתון#

def merge(left, right):
    merged_list = []
    left_i, right_i = 0, 0    # Leading indices
    while left_i < len(left) and right_i < len(right):    # While both lists are not done
        if left[left_i] <= right[right_i]:
            merged_list.append(left[left_i])
            left_i += 1
        else:
            merged_list.append(right[right_i])
            right_i += 1

    # copy remaining:
    merged_list += left[left_i:] + right[right_i:]
    return merged_list

עיצרו וחישבו: נניח ש-len(right)=5, ו־-len(left)=3. כמה איטרציות תתבצענה לכל היותר בתוך לולאת ה-while?

אנחנו יודעים שהלולאה תיפסק ברגע שאחת מהרשימות “תסתיים” - כלומר, כשנכניס לרשימה המאוחדת את האיבר האחרון שלה. כדי לגרום ללולאה לפעול כמה שיותר זמן, נרצה ששתי הרשימות “יחזיקו מעמד” כמה שיותר לפני שהאחת מהן תתרוקן. נשיג זאת אם נדאג שהאיבר המקסימלי בכל רשימה יופיע כמה שיותר לקראת הסוף של תהליך המיזוג.

לדוגמה: עבור left=[1,2,100] וright=[3,4,5,6,101], שתי הרשימות ישתתפו כמעט עד הסוף - כל אחת תשמור את האיבר המקסימלי שלה (100 ו־101) לסיום. במקרה זה יתבצעו 6 איטרציות של הלולאה, עד הרגע שבו נכניס את 100 ונרוקן את הרשימה left.

היתרון במיזוג רשימות ממוינות#

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

לאחר שהכרנו את הפונקציה merge, נשתמש בה עבור הפתרון הרקורסיבי של Merge Sort.

מימוש Merge Sort#

נתחיל מהגדרת שלושת חלקי הרקורסיה בפתרון:

  • תנאי עצירה (stop): רשימה עם איבר אחד. הרשימה כבר ממוינת ואין צורך להמשיך.

  • פירוק לתתי בעיות (decomposition): נחלק את הרשימה לשני חצאים (באורך קטן יותר מהרשימה המקורית), ונמיין כל אחד מהחצאים בצורה רקורסיבית.

  • הרכבת תתי הבעיות לפתרון (aggregation): נמזג את תתי-הרשימות הממוינות לרשימה אחת ממוינת (באמצעות פונקצית merge שכתבנו למעלה)

מימוש בפייתון#

def mergesort(lst):
    if len(lst) <= 1: # STOP
        return lst

    middle = len(lst) // 2 
    left = mergesort(lst[ : middle]) # DECOMPOSITION
    right = mergesort(lst[middle : ]) # DECOMPOSITION
    merged_list = merge(left, right) # USE
    return merged_list 

print(mergesort([3,1,7,137,132,731]))

[1, 3, 7, 132, 137, 731]

עיצרו וחישבו: נניח שהרצנו את הפונקציה על רשימה באורך 16. מה יהיה “העומק” של עץ הרקורסיה?

ב-Merge Sort, בכל שלב של הרקורסיה הרשימה נחצית לשניים — כלומר בכל רמה בעץ הרקורסיה, גודל הרשימות קטן פי שניים מהשלב הקודם. נמשיך לפצל עד שנקבל תתי־רשימות באורך 1 (שבהן אין צורך למיין).

אם אורך הרשימה ההתחלתי הוא len(lst)=16, נוכל לחשב את עומק העץ כך: בכל שלב אנו מחלקים ב־2:
16 → 8 → 4 → 2 → 1

נדרשו 4 חלוקות להגיע מ־16 ל־1, ולכן עומק עץ הרקורסיה הוא 4.

באופן כללי, עומק העץ של Merge Sort הוא \(log₂(n)\) - כלומר במקרה זה, \(log₂(16)=4\).

Contents