מיון מיזוג (Merge Sort)

Merge Sort - מיון מיזוג. אלגוריתם זה פועל בשיטת הפרד ומשול, האלגו’ הומצא על ידי המתמטיקאי ג׳ון פון ניומן בשנת 1945. להבדיל מהאלגוריתמים שראינו עד כה, לאלגוריתם זה יש 2 שגרות (Merge, ו Merge Sort).

מהי שיטת הפרד ומשול?

Merge Sort Animation

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

 

עקרון האלגוריתם

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

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

 

הקוד של האלגוריתם בפסאודו קוד

(ה ~ נועד לסמן עיגול כלפי מטה)

MERGE (A, p, q, r)
n1 <- q - p + 1
n2 <- r - q
create arrays L[1..n1 + 1] and R[1..n2+1]
for (i <- 1 to n1) do
    L[i] <- A[p + i - 1]
for (j <- 1 to n2) do
    R[j] <- A[q + j]
L[n1 + 1] <- infinity
R[n2 + 1] <- infinity
i <- 1
j <- 1
for (k <- p to r) do
    if (L[i] =< R[j])
        A[k] <- L[i]
    else
        A[k] <- R[j]
    j <- j + 1

MERGE-SORT (A, p, r)
if ( p < r )
    q <- ~(p + r )/ 2~
    MERGE-SORT (A, p, q)
    MERGE-SORT (A, q + 1, r)
    MERGE (A, p, q, r)

 

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

MERGE-SORT מקבל את A - המערך שיש למיין, p - משתנה המכיל מצביע לתחילת המערך, ואת r - משתנה המכיל מצביע לסוף המערך. השגרה MERGE-SORT מחלקת את המערך ל-2 (על ידי מצביע לאיבר האמצעי במשתנה q) וקריאה רקורסיבית (קריאה לעצמה) פעמיים, פעם אחת מ p (שמצביע לתחילת המערך המקורי) ועד ל q (שמצביע לאמצע המערך המקורי), ופעם נוספת מ q+1 (האיבר אחרי האמצע במערך המקורי) ועד ל r (שמצביע לסוף המערך המקורי). כך האלגו’ מחלק את עצמו כל פעם ל-2 עד שלא מתקיים התנאי p<r (שההתחלה לא קטנה מ r, הסוף. ז”א שיש לפחות איבר אחד בתת מערך).

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

שימו לב כי המיזוג של הסדרות מתבצע ע”י השגרה Merge ולכן היא זאת שמבצעת את רוב העבודה באלגוריתם.

 

הרצה של הקוד לשם המחשה של השלבים המתבצעים

  1. נקבל מערך: { 5, 7, 1, 3 }.
  2. שורה 2: מתחילים מ MERGE-SORT, מכיוון ש p<r נבצע:
    • שורה 3: נחלק את הסכום p (האיבר הראשון) ועוד r (האיבר האחרון) ל2, ז”א שכרגע יש לנו 5 תאים, נחלק ל2 זה 2.5, לכן q יהיה שווה 2 (מעגלים כלפי מטה).
    • שורה 4: קוראים שוב לעצמנו לכן חוזרים לשורה 1.
  3. שורה 2: מכיוון ש p (האיבר הראשון, 1) עדיין גדול מ r (שהיה q, אז הוא שווה ל2) נבצע:
    • שורה 3: נחלק את הסכום p (האיבר הראשון, 1) ועוד r (האיבר האחרון) ל2, ז”א שכרגע זה 3, נחלק ל2 זה 1.5, לכן q יהיה שווה 1.
    • שורה 4: קוראים שוב לעצמנו ולכן חוזרים לשורה 1.
  4. שורה 2: מכיוון ש p (האיבר הראשון, 1) כבר לא גדול (אלא שווה) ל r (שהיה q, אז הוא שווה ל1), לא ניכנס לפעולות שבתוך ה if, ונצא ישר מהמתודה (כי יש בה רק If), ז”א שנחזור אחורה (האלגו’ שלנו רקורסיבי).
    • שורה 5: קוראים שוב לעצמנו, ולכן חוזרים לשורה 1.
  5. שורה 2: מכיון ש p (שהיה q + 1, והוא 1) קטן מ r (האיבר האחרון, 2) נבצע:
    • שורה 3: נחלק את הסכום p (שהוא 1) ועוד r (שהוא 2), שהוא 3, ל2 זה 1.5, לכן q יהיה שווה 1.
    • שורה 4: קוראים שוב לעצמנו ולכן חוזרים לשורה 1.
  6. שורה 2: מכיוון ש p (האיבר הראשון, 1) כבר לא גדול (אלא שווה) ל r (שהיה q, אז הוא שווה ל1), לא ניכנס לפעולות שבתוך ה if, ונצא ישר מהמתודה (כי יש בה רק If), ז”א שנחזור אחורה (האלגו’ שלנו רקורסיבי). <ul style="list-style-type: circle;">
    • שורה 5: קוראים שוב לעצמנו, ולכן חוזרים לשורה 1.
  7. שורה 2: מכיון ש p (שהיה q + 1, והוא 1) שווה ל r (אותו איבר, לכן גם הוא 1), לא ניכנס לפעולות שבתוך ה If, ונצא ישר מהמתודה (כי יש בה רק if), ז”א שנחזור אחורה (האלגו’ שלנו רקורסיבי).
    • שורה 6: נקרא למתודה MERGE על { 5, 7 }. <ul style="list-style-type: disc;">
    • המתודה MERGE תמיין על ידי השוואה את האיברים { 5, 7 }, ולכן התת מערך יראה כך: { 7, 5 }.
    • לאחר מכן, נחזור חזרה למעלה, לשוב ל MERGE אך הפעם על { 1, 3 }.
    • המתודה MERGE תמיין על ידי השוואה את האיברים, והתת מערך יראה כך: { 3, 1 }.
    • לאחר מכן נעלה בפעם האחרונה (נכנסו 3 פעמים, נעלה חזרה ברקורסיה 3 פעמים), ונמיין את התת מערכים { 7, 5 }, ו { 3, 1 } למערך אחד (על ידי השוואה אחד מול השני (1 מול 5, 1 קטן מ5 ולכן 1 יהיה ראשון, לאחר מכן 3 מול 5, 3 קטן מ5 ולכן 3 יהיה שני, ולאחר מכן לא נשארו איברים להשוואה אז “נשפוך” את האיברים שנשארו בתת מערך למערך הראשי.

 

שימו לב, במתודה MERGE: שורות 2 עד 12 הינן “הכנה” לעבודה האמיתית, השורות כוללות חישוב של אורך התתי מערכים, ויצירה של 2 מערכים גדולים יותר (באחד), העתקה של האיברים בתת מערך השמאלי למערך השמאלי החדש והעתקה של האיברים בתת מערך הימיני למערך הימיני החדש. בנוסף, בשורות 9-10 מתבצעת הצבה של זקיפים בתאים האחרונים במערך (בקוד אמיתי כנראה שנציב שם 1-, הרי לא ניתן להציב אינוסף). ובשורות 13 עד 18 מתבצע המיון האמיתי של האיברים על ידי השוואה של כל אחד מהאיברים לשני.

 

סיבוכיות זמן ריצה: ((O(n*lg(n (למען הסר ספק: lg - זהו log בבסיס 2).
סיבוכיות מקום: (O(n.