מיזוג מיון ב- Java
1. הקדמה
במדריך זה, נסתכל על האלגוריתם של מיזוג מיון והטמעתו ב- Java.
מיון מיזוג הוא אחת מטכניקות המיון היעילות ביותר והיא מבוססת על פרדיגמת "לחלק ולכבוש".
2. האלגוריתם
מיון מיזוג הוא אלגוריתם "לחלק ולכבוש" שבו אנו מחלקים את הבעיה תחילה לבעיות משנה. כאשר הפתרונות לבעיות המשנה מוכנים, אנו משלבים אותם יחד בכדי לקבל את הפתרון הסופי לבעיה.
זהו אחד האלגוריתמים שניתן ליישם בקלות באמצעות רקורסיה כאשר אנו מתמודדים עם בעיות המשנה ולא עם הבעיה העיקרית.
ניתן לתאר את האלגוריתם כתהליך הדו-שלבי הבא:
- מחלקים: בשלב זה אנו מחלקים את מערך הקלט לשני חצאים, שהציר הוא נקודת האמצע של המערך. שלב זה מתבצע רקורסיבית לכל מחצית המערכים עד שאין עוד חצי מערכים לחלוקה.
- לכבוש: בשלב זה אנו ממיינים וממזגים את המערכים המחולקים מלמטה למעלה וקבל את המערך הממוין.
התרשים הבא מציג את תהליך מיון המיזוג השלם למערך לדוגמה {10, 6, 8, 5, 7, 3, 4}.
אם נסתכל מקרוב על הדיאגרמה, נוכל לראות שהמערך מחולק רקורסיבית לשני חצאים עד שהגודל הופך ל 1. ברגע שהגודל הופך ל -1, תהליכי המיזוג נכנסים לפעולה ומתחילים למזג מערכים בחזרה תוך כדי מיון:
3. יישום
ליישום, נכתוב א מיזוג פונקציה שלוקחת את מערך הקלט ואת אורכו כפרמטרים. זו תהיה פונקציה רקורסיבית ולכן אנו זקוקים לבסיס ולתנאים הרקורסיביים.
תנאי הבסיס בודק אם אורך המערך הוא 1 והוא רק יחזור. בשאר המקרים השיחה הרקורסיבית תבוצע.
במקרה הרקורסיבי, אנו מקבלים את האינדקס האמצעי ויוצרים שני מערכים זמניים l [] ו r []. ה מיזוג אז נקראת רקורסיבית לשני מערכי המשנה:
חלל סטטי ציבורי mergeSort (int [] a, int n) {if (n <2) {return; } int באמצע = n / 2; int [] l = int int [mid]; int [] r = int int [n - mid]; עבור (int i = 0; i <mid; i ++) {l [i] = a [i]; } עבור (int i = mid; i <n; i ++) {r [i - mid] = a [i]; } mergeSort (l, mid); mergeSort (r, n - mid); מיזוג (a, l, r, mid, n - mid); }לאחר מכן אנו קוראים לְמַזֵג פונקציה המקבלת את הקלט וגם את מערכי המשנה וגם את מדדי ההתחלה והסיום של שני מערכי המשנה.
ה לְמַזֵג פונקציה משווה את האלמנטים של שני מערכי המשנה אחד אחד וממקם את האלמנט הקטן יותר במערך הקלט.
כשאנחנו מגיעים לסוף אחד מערכי המשנה, שאר האלמנטים מהמערך השני מועתקים למערך הקלט ובכך נותנים לנו את המערך הממוין הסופי:
מיזוג ריק סטטי ציבורי (int [] a, int [] l, int [] r, int שמאל, int ימין) {int i = 0, j = 0, k = 0; ואילו (i <left && j <right) {if (l [i] <= r [j]) {a [k ++] = l [i ++]; } אחר {a [k ++] = r [j ++]; }} בעוד (i <שמאל) {a [k ++] = l [i ++]; } בעוד (j <מימין) {a [k ++] = r [j ++]; }} מבחן היחידה לתכנית:
@Test הציבור בטל positiveTest () {int [] בפועל = {5, 1, 6, 2, 3, 4}; int [] צפוי = {1, 2, 3, 4, 5, 6}; MergeSort.mergeSort (בפועל, אורך בפועל); assertArrayEquals (צפוי, ממשי); }4. מורכבות
מכיוון שמיון המיזוג הוא אלגוריתם רקורסיבי, מורכבות הזמן יכולה לבוא לידי ביטוי כקשר הרקורסיבי הבא:
T (n) = 2T (n / 2) + O (n)2T (n / 2) תואם את הזמן הנדרש למיון מערכי המשנה ו- עַל) זמן למזג את כל המערך.
כאשר נפתרים, מורכבות הזמן תגיע O (nLogn).
זה נכון במקרה הגרוע, הממוצע והטוב ביותר שכן הוא תמיד יחלק את המערך לשניים ואז יתמזג.
מורכבות החלל של האלגוריתם היא עַל) כאשר אנו יוצרים מערכים זמניים בכל שיחה רקורסיבית.
5. מסקנה
במדריך מהיר זה ראינו את עבודתו של אלגוריתם מיון המיזוג וכיצד אנו יכולים ליישם אותו בג'אווה.
קוד העבודה כולו זמין ב- GitHub.
