מיון מיזוג

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 תיאור האלגוריתם
- 1.1 מימוש מילולי
- 1.2 מימוש המיזוג
2 דוגמת הרצה
3 ניתוח סיבוכיות מיון-מיזוג

[עריכה] תיאור האלגוריתם

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

[עריכה] מימוש מילולי

ברמה העקרונית, עובד מיון-מיזוג בצורה הבאה:

מיין-מזג n איברים

אם n=1 (המערך של איבר אחד ממילא ממוין) חזור
מיין-מזג את n/2 האברים הראשונים
מיין-מזג את n/2 האברים האחרונים
מזג את 2 תוצאות המיון

בפסאודו קוד, המזכיר את שפת C, יראה האלגוריתם כך:

mergesort(Array m)
{
     if length(m) ≤ 1
         return m
     else
     {
         middle = length(m) / 2
         for each x in m up to middle
             add x to left
         for each x in m after middle
             add x to right
         left = mergesort(left)
         right = mergesort(right)
         result = merge(left, right)
         return result
     }
}

[עריכה] מימוש המיזוג

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

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

בפסאודו קוד יראה המיזוג כך:

merge(left,right)
{
    while length(left) > 0 and length(right) > 0
    {
        if first(left) ≤ first(right)
        {
            append first(left) to result
            left = rest(left)
        }
        else
        {
            append first(right) to result
            right = rest(right)
        }
    }
    if length(left) > 0
        append left to result
    if length(right) > 0 
        append right to result
    return result
}

להמחשה, נמזג את קבוצות המספרים הממויינות: 1,2,4,8,9,10,11 ו-3,7.

האיברים הראשונים הם 1 ו-3. 1 קטן מ-3 ולכן נכניס את 1.
כעת האיברים הראשונים הם 2 (1 הוכנס) ו-3 (לא טיפלנו בו עדיין). 2 קטן מ-3 ולכן נכניס את 2.
כעת האיברים הראשונים הם 4 ו-3. 3 קטן מ-4 ולכן נכניס את 3.
כעת האיברים הראשונים הם 4 ו-7. 4 קטן מ-7 ולכן נכניס את 4.
כעת האיברים הראשונים הם 8 ו-7. 7 קטן מ-8 ולכן נכניס את 7.
שים לב שלא נותרו עוד מספרים בקבוצת המספרים השנייה, נכניס את יתר קבוצת המספרים הראשונה: 8,9,10,11.

נראה כעת מהו המערך שהתקבל: 1,2,3,4,7,8,9,10,11. אלו הם בדיוק כל המספרים כאשר הם ממויינים כפי שציפינו.

[עריכה] דוגמת הרצה

השרטוט הבא מדגים כיצד ממיין האלגוריתם מערך בגודל 7 המכיל את הערכים: 38,27,43,3,9,82,10.

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

[עריכה] ניתוח סיבוכיות מיון-מיזוג

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

ננסה לחשב תחילה את מספר הפעמים שמתבצעת פעולת המיזוג. הפעולה מתבצעת בכל קריאה לפונקציה "מיון-מיזוג". הקריאה הראשונה תמזג בין שני חצאי מערכים בגודל $\ n/2$ (סה"כ $\ n$ איברים, סיבוכיות זמן ריצה $\ O(n)$ . לפני-כן הקריאה הראשונה קוראת פעמיים למיון-מיזוג, פעם אחת עבור חצי המערך הראשון ופעם שנייה עבור חצי המערך השני. בכל קריאה יתבצע מיזוג של שני חצאי מערכים בגודל $\ n/4$ , סה"כ מדובר ב-4 מערכים ולכן יש סה"כ $\ n$ איברים שיתמזגו ושוב סיבוכיות זמן הריצה הכוללת היא $\ O(n)$ . האלגוריתם ימשיך עד אשר כל המערכים יהיו בגודל 1 ואז נמזג אותם זוג-זוג, עדיין מדובר ב- $\ n$ איברים ולכן סיבוכיות זמן הריצה של כל פעולות המיזוג יחד היא $\ O(n)$ .

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

נסתכל בכל פעם רק על חלק אחד של המערך המפוצל, נתחיל במערך הגדול ונשאר עם מערך בגודל $\ n/2$ ואז נמשיך להתבונן במערך בגודל $\ n/4$ וכן הלאה, עד אשר נגיע למערך בגודל 1. בכל שלב מתבצע מיזוג שזמן ריצתו $\ O(n)$ , נותר רק לספור כמה שלבים כאלו יש.

כפי שנאמר קודם, בכל פעם אנו שולחים למיון-מיזוג מערך שגודלו חצי מהמערך הקודם. לאחר קריאה אחת יהיה גודל המערך $\frac{n}{2}$ , לאחר שתי קריאות יהיה גודלו $\frac{n}{2^2}$ וכן הלאה. התהליך ייגמר כאשר גודל המערך הינו 1. אם התהליך כולו יימשך $\ k$ פעמים, יהיה גודל המערך $\frac{n}{2^k}$ . אנו דורשים שגודל זה יהיה 1 ולכן נדרוש $\frac{n}{2^k} = 1$ . נוציא $\ log$ משני אגפי המשוואה ונקבל כי $\ k = log(n)$ .