מדריך למיון מיזוג ב-Python

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

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

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

מהו מיזוג מיון?

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

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

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

אסטרטגיית חלוקה וכיבוש

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

בעיה של מיון מיזוג. מקור: DataCamp

זמן ומקום מרחב של מיון מיזוג

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

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

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

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

ניתוח רכיבות הזמן נכתב בכתיב Big O, כתיב מתמטי המתאר את קצב הצמיחה או הירידה של פונקציה. המיון מיזוגי נטייה לזמן רכיבות או רכיבות לוגריתמי, המסומנות כ-O(N log(N)), כאשר N מייצג את מספר האיברים ברשימה. האות 'O' מסמלת את 'סדר' הצמיחה.

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

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

רכיבות המקום של מיון מיזוגי

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

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

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

יישום מיון מיזוג בפייתון

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

הבנת ריקורסיה במיון מיזוג

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

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

ברגע שיש לנו את תתי הרשימות הממוינות הללו, אנו מתחילים בתהליך המיזוג. כדי לעשות זאת, אנו מאתחלים שלושה משתני אינדקס: i למעקב אחר המיקום ב-left_half, j ל-right_half, ו-k עבור הרשימה הממוזגת הסופית. אנו משווים לאחר מכן אלמנטים משני החצאים. אם האלמנט הנוכחי ב-left_half קטן יותר, אנו שמים אותו ב-my_list[k] ומזיזים את i קדימה. אחרת, אנו לוקחים את האלמנט מ-right_half, שמים אותו ב-my_list[k], ומגדילים את j. לאחר כל השוואה, אנו מזיזים את k קדימה למיקום הבא ברשימה הסופית.

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

יישום בפייתון

להלן, תוכל למצוא את הקוד המשתמש ברשימה הלא מסודרת של הדיאגרמה הקודמת כדוגמה:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

מיזוג מיון מול אלגוריתמים אחרים למיון

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

בטבלה הבאה, תוכל למצוא השוואה בין מיזוג מיון לאלגוריתמים פופולריים אחרים למיון.

יישומים מעשיים של מיון מיזוג

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

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

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

שגיאות נפוצות ופתרון בעיות

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

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

בנוסף, רעיון טוב לחקור היה הפרדת משימות. שלבי המיון הממוזגים יכולים להיות מקבילים בקלות עם הכוח החישובי המתאים, ובכך להפחית את הזמן הנדרש להשלמת התהליך. קראו את מדריך ה-CPU vs GPU שלנו כדי ללמוד עוד על חישוב מקביל. 

מסקנה

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

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