להבין את מיון מיזוג - merge sort - אלגוריתם הפרד ומשול יעיל

מיון הוא פעולה בסיסית בעולם המחשוב. ישנם אלגוריתמי מיון רבים ושונים. במדריך הזה, נלמד על אחד מתהליכי המיון הפופולריים והיעילים ביותר: מיון מיזוג merge sort.

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

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

בסוף המדריך תהיה לך הבנה טובה יותר של אלגוריתם מיון מיזוג merge sort וכיצד להשתמש בו למיון יעיל של נתונים.

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

המתמטיקאי האגדי ג'ון פון נוימן פיתח את האלגוריתם מיון מיזוג בשנות ה-1940. הוא חשב על ערימה של קלפים שאותה צריך למיין. זה מאוד קשה אבל ממש קל למיין 2 קלפים אם מסדרים בשתי ערימות. בכל ערימה קלף אחד. אם אתה רוצה למזג אותם לערימה אחת מסודרת אתה רק צריך לשים את הקלף שערכו נמוך מעל לקלף שערכו גבוה. עכשיו יש לך ערימה של 2 קלפים ממוינים. בשלב זה, תשווה לערימה נוספת ממויינת שגם בה יש 2 קלפים ממוינים. תשווה את הקלף מראש הערימה הראשונה עם הקלף מראש הערימה השנייה ותעביר את הקלף הנמוך לערימה הממוינת. תחזור על התהליך עד שתסיים לעבור על כל הקלפים משתי הערימות. עכשיו יש לך ערימה של 4 קלפים ממוינים. תשווה אותה לערימה נוספת של 4 קלפים ממוינים. אחרי המיזוג שלהם תהיה לך ערימה של 8 קלפים ממוינים. אח"כ תשווה שתי ערימות של 8 קלפים ממוינים. וחוזר חלילה. בכל שלב תשווה ערימות המכילות מספר כפול של פריטים. כל שלב מכפיל פי 2 את מספר הקלפים הממוינים: בשביל לסדר 2 קלפים אתה צריך להשוות פעם 1, בשביל לסדר 4 קלפים אתה צריך להשוות פעמיים, בשביל 8 פריטים אתה צריך 3 השוואות. כלומר, כדי למיין N פריטים אתה צריך לחזור על פעולת המיון 2 בחזקת X פעמים השווה N. מה שאומר סיבוכיות זמן לוגריתמית של התהליך.

מובן מאליו שערימה שמכילה קלף 1 בודד היא ממוינת. זה המקרה הטריוויאלי. יתרה מכך, קל לסדר ולמזג 2 ערימות קלפים שבכל אחת קלף 1 לערימה אחת ממוינת המכילה 2 קלפים. חוזרים על התהליך כמה שצריך. בכל שלב ממזגים פי 2 יותר קלפים. אבל איך מקבלים מערימה אחת גדולה ערימות של קלפים בודדים? בשביל זה צריך לפצל את הערימה. מתחילים מפיצול הערימה לשני חצאים שווים. כל חצי מפצלים שוב לחצאים, וכך מקבלים 4 רבעים של הערימה המקורית, וחוזר חלילה עד שמקבלים מספר ערימות של קלפים יחידים כמספר הקלפים שהיו קיימים בערימה המקורית. בשלב זה כל ערימה המכילה קלף בודד היא ממוינת בפני עצמה. עכשיו שיש לנו ערימות של קלפים יחידים ממוינים משווים וממזגים בין זוגות של ערימות ממוינות כל ערימה מכילה קלף אחד. מקבלים ערימות של 2 קלפים ממוינים, שאותם ממזגים לערימות של 4, וחוזר חלילה, ערימות הולכות וגדלות, עד לקבלת ערימה שלמה גדולה וממוינת.

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

אלגוריתם מיון מיזוג כולל 2 צעדים:

1. פיצול split - את הרשימה הלא ממוינת מפצלים שוב ושוב לחצאים עד שכל תת רשימה מכילה פריט אחד או אפס פריטים. תת רשימות המכילות פריט אחד או ריקות נחשבות ממוינות.
2. מיזוג merge - תת הרשימות הממוינות ממוזגות יחדיו, תוך סידור הפריטים ויצירת רשימה אחת ממוינת.

איך עובד מיון מיזוג - בסבלנות שלב אחר שלב

א. שלב החלוקה (=פיצול)

נעביר לאלגוריתם את רשימת הפריטים הבאה לצורך סידור:

האלגוריתם יחלק את הרשימה ל-2 תת רשימות שוות גודל:

• כיוון שהרשימה מונה מספר אי זוגי של פריטים החלוקה היא לשתי תת רשימות שיש ביניהם הבדל של פריט 1. רשימה ימנית המונה 4 פריטים ושמאלית המונה שלושה.

האלגוריתם יחלק שנית את 2 תת הרשימות ל-4 תת רשימות:

החלוקה האחרונה היא כאשר האלגוריתם יחלק את 4 תת הרשימות ל-7 תת רשימות שכל אחת מהם תכיל פריט 1:

• מספר תת הרשימות בשלב הסופי של החלוקה בהכרח שווה למספר הפריטים ברשימה הגדולה איתה התחלנו את התהליך.

ב. שלב המיזוג

אחרי שהאלגוריתם חילק את הרשימה לתת רשימות בכל אחת מהם פריט 1 מגיע שלב המיזוג בו משווים צמדי רשימות לצורך מיזוגם:

האלגוריתם ימזג 2 רשימות. אחת המכילה 9 ושנייה המכילה 6. 6 קטן מ-9 וזה יהיה הסדר ברשימה הממוזגת:

האלגוריתם ימזג 2 רשימות נוספות. אחת המכילה 4 ושנייה המכילה 10. 4 קטן מ-10 וזה יהיה הסדר ברשימה הממוזגת:

האלגוריתם ימזג 2 רשימות נוספות. אחת המכילה 5 ושנייה המכילה 7. 5 קטן מ-7 וזה יהיה הסדר ברשימה הממוזגת:

אחרי שהאלגוריתם סיים את השלב של מיזוג רשימות הפריטים הבודדים לרשימות המכילות 2 פריטים ממוינים כל אחת, הוא יעבור למיין ולמזג את הרשימות המכילות 2 פריטים לרשימות המונות 4 פריטים ממוינים כל אחת.

נתחיל ממיזוג הרשימות 8 מימין ו 6-9 משמאל. לשם המיזוג, נפעיל 2 מצביעים, אחד לכל רשימה, הסורקים משמאל לימין, ועל ידי כך עוקבים אחר הפריטים אותם משווים. המצביעים (מסומנים בירוק בתמונה) מורים על הפריטים 8 מהרשימה השמאלית ו-6 מהימנית. כיוון ש-6 הוא הפריט בעל הערך הנמוך יותר הוא יעבור לרשימה הממוזגת:

המצביע ימשיך במסעו לימין. בהשוואה בין 8 מהרשימה השמאלית ל-9 מהימנית, הפריט 8 הוא הנמוך יותר, ועל כן יעבור לרשימה הממוזגת:

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

• התחלנו עם 2 רשימות. באחת 2 פריטים. בשנייה פריט 1, מיינו ומיזגנו וכתוצאה מכך קיבלנו רשימה ובה 3 פריטים.

הפונקציה הממזגת תעבור לטפל בשתי תת הרשימות: 4-10 ו 5-7 עליהם יוצבו 2 מצביעים. 1 לכל רשימה. המצביעים יורו על הפריטים שנמצאים בעמדות האינדקס השמאליות. כיוון שהפריט 4 מהרשימה השמאלית קטן יותר מ-5 מהרשימה הימנית, 4 יהפוך להיות הפריט הראשון ברשימה הממוזגת:

המצביע ברשימה השמאלית יזוז צעד אחד ימינה. עכשיו ההשוואה היא בין הפריט 10 מהרשימה השמאלית לפריט 5 מהרשימה הימנית. כיוון ש-5 הוא הקטן יותר הוא יעבור לרשימה הממוזגת:

המצביע ברשימה הימנית יזוז צעד אחד ימינה, ועכשיו ההשוואה היא בין 7 מימין ל-10 משמאל. 7 הוא הנמוך יותר ועל כן יעבור לרשימה הממוזגת:

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

את השלב השני של תהליך המיזוג התחלנו עם 4 רשימות ממוינות וסיימנו עם 2.

את השלב השלישי של תהליך המיזוג יתחיל האלגוריתם עם 2 רשימות ממוינות ויסיים עם 1 גדולה.

נציב מצביע אחד על הפריט הראשון של הרשימה השמאלית (6) ומצביע שני על הפריט הראשון של הרשימה הימנית (4). נשווה ביניהם, ונוסיף לרשימה הממוינת את הקטן מביניהם (4):

כיוון שהקטן הגיע מהרשימה הימנית, נזיז את המצביע הימני עמדה 1 ימינה. עכשיו ההשוואה היא בין 5 מימין ל-6 משמאל. 5 נמוך יותר. על כן יעבור לרשימה הממוינת:

כיוון שהקטן הגיע מהרשימה הימנית, נזיז את המצביע הימני עמדה 1 ימינה. עכשיו ההשוואה היא בין 7 מימין ל-6 משמאל. 6 נמוך יותר. על כן יעבור לרשימה הממוינת:

כיוון שהקטן הגיע מהרשימה השמאלית, נזיז את המצביע השמאלי עמדה 1 ימינה. עכשיו ההשוואה היא בין 8 משמאל ל-7 מימין. 7 נמוך יותר. על כן יעבור לרשימה הממוינת:

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

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

המצביע משמאל לא יכול להתקדם יותר ועל כן יצא משימוש. נשארנו רק עם המצביע מימין. נעביר את הפריט עליו הוא מצביע (10) לרשימה הממוינת:

המצביע מימין לא יכול להתקדם יותר. לכן יצא משימוש. נשארנו עם רשימה 1 ממוינת:

זהו! אלגוריתם מיון מיזוג סיים למיין את הרשימה.

קוד פייתון של מיון מיזוג

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

def sort(arr):
    """Sorts the given array in ascending order."""
    # Base case.
    # A list of zero or a single item is sorted, by definition.
    if len(arr) <= 1:
        return arr

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

במקרים הרקורסיביים (בהם הרשימה מכילה לפחות 2 פריטים) הרשימה תפוצל סביב נקודת האמצע לשתי תתי רשימות - ימנית ושמאלית. כל אחת מתת הרשימות תפוצל אף היא באופן רקורסיבי:

def sort(arr):
    """Sorts the given array in ascending order."""
    # Base case.
    # A list of zero or a single item is sorted, by definition.
    if len(arr) <= 1:
        return arr


    # Recursive case.


    # Split array into 2 equal size sub arrays
    mid = len(arr) // 2
    left_arr = arr[:mid]
    right_arr = arr[mid:]


    # Sort recursively both sub arrays
    left_arr = sort(left_arr)
    right_arr = sort(right_arr)


    # Merge both sub arrays
    return merge(left_arr, right_arr)

אחרי הפיצול הרקורסיבי נכנסת לפעולה פונקציה ממזגת merge המקבלת בתור פרמרטים 2 תתי רשימות ממוינות ומחזירה רשימה 1 ממוינת:

def merge(left_arr, right_arr):
    """Merges two sorted arrays into a single sorted array."""
    merged_arr = []
    left_index = right_index = 0

    # Compare elements from the left and right arrays
    # to find the smaller element and add it to the merged array
    while left_index < len(left_arr) and right_index < len(right_arr):
        if left_arr[left_index] < right_arr[right_index]:
            merged_arr.append(left_arr[left_index])
            left_index += 1
        else:
            merged_arr.append(right_arr[right_index])
            right_index += 1

    # Add the remaining elements from the arrays
    merged_arr.extend(left_arr[left_index:])
    merged_arr.extend(right_arr[right_index:])

    return merged_arr

• הפונקציה הממזגת merge מקבלת שני תתי מערכים: left_arr ו-right_arr, אותם היא ממזגת למערך ממוין יחיד.
• הפונקציה מאתחלת מערך merged_arr ריק שתפקידו לאחסן את האלמנטים הממוינים.
• הפונקציה מאתחלת שני משתני אינדקס, left_index ו-right_index, שעוקבים אחר מיקום המצביע בכל רגע נתון בתתי המערכים left_arr ו-right_arr.
• בתוך לולאת while מושווים פריטים מתתי המערכים השמאלי והימני ונוסף הפריט שערכו נמוך יותר למערך הממוזג. בכל פעם שפריט נוסף למערך מאחד מתתי המערכים, נוסף 1 למשתנה האינדקס של אותו תת מערך.
• לאחר שהלולאה מסיימת לרוץ, עשויים להיות פריטים שנותרו במערך השמאלי או הימני. הקוד משתמש במתודה הפייתונית extend כדי להוסיף את האלמנטים הנותרים ל-merged_arr.
• לבסוף מוחזר merged_arr המכיל רשימה ממוינת המורכבת משילוב תתי המערכים אותם הפונקציה קיבלה.

נבדוק:

numbers = [8, 6, 9, 10, 4, 7, 5]
sorted_numbers = sort(numbers)
print(sorted_numbers)

התוצאה:

[4, 5, 6, 7, 8, 9, 10]

נבחן עוד מספר מקרי קצה:

def test_merge_sort_empty_array():
    assert sort([]) == []


def test_merge_sort_array_with_one_element():
    assert sort([1]) == [1]


def test_merge_sort_sorted_array():
    assert sort([1, 2, 3, 4, 5]) == [1, 2, 3, 4, 5]


def test_merge_sort_unsorted_array():
    assert sort([3, -5, 6, 1, 2, -8, 4, 3, 4, 100, -100]) == [-100, -8, -5, 1, 2, 3, 3, 4, 4, 6, 100]


def main():
    test_merge_sort_empty_array()
    test_merge_sort_array_with_one_element()
    test_merge_sort_sorted_array()
    test_merge_sort_unsorted_array()


if __name__ == "__main__":
    main()

• אם זה לא ברור נא לקרוא את המדריכים: מה זה __name__ == __main__ בפייתון? ובשביל להבין בדיקות יחידה בדיקות יחידה unit test בפייתון באמצעות pytest

סיבוכיות זמן של מיון מיזוג

אלגוריתם מיון מיזוג מורכב משני שלבים עוקבים: שלב פיצול שלאחריו שלב מיזוג. שלב הפיצול מתבצע בזמן קבוע פחות או יותר ולכן נזניח אותו.

נחשב את סיבוכיות הזמן של שלב המיזוג.

אם N הוא מספר הפריטים במערך, מיון מיזוג עושה log N צעדי מיזוג כיוון שכל פעם שמריצים את פונקצית המיזוג מקבלים רשימה בעלת אורך כפול כפלט. בשביל למזג 2 ערימות של פריטים בודדים (סה"כ 2 פריטים) צריך לעשות צעד מיזוג 1, בשביל למזג 2 ערימות בכל אחת 2 פריטים (סה"כ 4 פריטים) צריך לעשות 2 צעדי מיזוג, בשביל למזג 2 ערימות של 4 פריטים (סה"כ 8 פריטים) צריך לעשות 3 צעדי מיזוג. וכיו"ב. מכאן האופי הלוגריתמי. אם זה לא ברור נא להיזכר בחוקי חזקות:

2^1 = 2
2^2 = 4
2^3 = 8
2^4 =16

הכלל הוא:

2^x = N 

• כאשר לוגריתם בסיס 2 הוא דרך לשאול בחזקת כמה צריך להעלות את 2 בשביל לקבל את התוצאה.

לדוגמה, בחזקת כמה צריך להעלות את 2 כדי לקבל 2?

log2(2) = 1

בחזקת כמה צריך להעלות את 2 כדי לקבל 4?

log2(4) = 2

בחזקת כמה צריך להעלות את 2 כדי לקבל 8?

log2(8) = 3

הכלל הוא בחזקת כמה x צריך להעלות את 2 כדי לקבל N:

log2(x) = N

לפיכך הביטוי:

2^x = N

מבטא כמה פעמים x צריך להריץ את הפונקציה הממזגת כדי למזג רשימה באורך N. את הפתרון מוצאים באמצעות log בסיס 2.

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

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

סיבוכיות הזמן היא מכפלה של מספר הפעמים שהפונקציה רצה בעבודה שהיא עושה בכל פעם שהיא רצה. הפונקציה רצה log N פעמים, ובכל פעם שהיא רצה היא רצה על N פריטים.

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

O(N log N)

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

מדריכים נוספים בסדרה ללימוד פייתון שעשויים לעניין אותך

האלגוריתם Quicksort ותהליך החלוקה

אלגוריתם Selection Sort מיון בחירה

אלגוריתם חיפוש בינארי - מהבנה ליישום

big-O ביטוי ליעילות הקוד

פייתון מונחה עצמים 1: מחלקות, אובייקטים, תכונות ומתודות

בדיקות יחידה unit test בפייתון באמצעות pytest

לכל המדריכים בסדרה ללימוד פייתון

אהבתם? לא אהבתם? דרגו!

0 הצבעות, ממוצע 0 מתוך 5 כוכבים