Merge sort הוא אחד האלגוריתמים הבסיסיים של מדעי המחשב, שנוסח עוד ב-1945 על ידי המתמטיקאי הגדול ג'ון פון נוימן. בזמן שהשתתפה בפרויקט מנהטן, נוימן התמודד עם הצורך לעבד ביעילות כמויות אדירות של נתונים. השיטה שפיתח השתמשה בעקרון "הפרד וכבוש", מה שהפחית משמעותית את הזמן הנדרש לעבודה.
עקרון ושימוש באלגוריתם
שיטת המיזוג משמשת בבעיות של מיון מבנים שהזמינו גישה לאלמנטים, כגון מערכים, רשימות, זרמים.
במהלך העיבוד, בלוק הנתונים הראשוני מפוצל לרכיבים קטנים, עד אלמנט אחד, שלמעשה הוא כבר רשימה ממוינת. לאחר מכן הוא מורכב מחדש בסדר הנכון.
מיון מערך באורך מסוים מצריך אזור זיכרון נוסף באותו גודל, שבו המערך הממוין נאסף בחלקים.
ניתן להשתמש בשיטה כדי להזמין כל סוג נתונים דומה, כגון מספרים או מחרוזות.
מיזוג ממויןמגרשים
כדי להבין את האלגוריתם, בואו נתחיל את הניתוח שלו מהסוף - מהמנגנון של מיזוג בלוקים ממוינים.
בוא נדמיין שיש לנו שני מערכים של מספרים ממוינים בכל דרך שצריך לשלב זה עם זה כדי שהמיון לא יישבר. לשם הפשטות, נמיין את המספרים בסדר עולה.
דוגמה אלמנטרית: שני המערכים מורכבים מאלמנט אחד כל אחד.
int arr1={31}; int arr2={18};
כדי למזג אותם, אתה צריך לקחת את אלמנט האפס של המערך הראשון (אל תשכח שהמספור מתחיל מאפס) ואת אלמנט האפס של המערך השני. אלו הם, בהתאמה, 31 ו-18. לפי תנאי המיון, המספר 18 צריך לבוא קודם, שכן הוא פחות. פשוט שים את המספרים בסדר הנכון:
תוצאה
int={18, 31};
בוא נסתכל על דוגמה מסובכת יותר, שבה כל מערך מורכב מכמה אלמנטים:
int arr1={2, 17, 19, 45}; int arr2={5, 6, 21, 30};
אלגוריתם המיזוג יכלול השוואה ברצף של אלמנטים קטנים יותר והצבתם במערך המתקבל בסדר הנכון. כדי לעקוב אחר המדדים הנוכחיים, הבה נציג שני משתנים - index1 ו- index2. בתחילה, הגדרנו אותם לאפס, מכיוון שהמערכים ממוינים, והאלמנטים הקטנים ביותר נמצאים בהתחלה.
int index1=0; int index2=0;
בוא נכתוב את כל תהליך המיזוג צעד אחר צעד:
- קח את האלמנט עם index1 מהמערך arr1, ואת האלמנט עם index2 מהמערך arr2.
- השווה, בחר את הקטן שבהם והכנסמערך שהתקבל.
- הגדל את האינדקס הנוכחי של הרכיב הקטן ב-1.
- המשך מהשלב הראשון.
במסלול הראשון, המצב ייראה כך:
index1=0; index2=0; arr1[0]=2; arr2[0]=5; arr1[0] < arr2[0]; index1++; result[0]=arr1[0]; // תוצאה=[2]
בפנייה השנייה:
index1=1; index2=0; arr1[1]=17; arr2[0]=5; arr1[1] > arr2[0]; index2++; תוצאה[1]=arr2[0]; // תוצאה=[2, 5]
Third:
index1=1; index2=1; arr1[1]=17; arr2[1]=6; arr1[1] > arr2[1]; index2++; result[2]=arr2[1]; // תוצאה=[2, 5, 6]
וכן הלאה, עד שהתוצאה תהיה מערך ממוין לחלוטין: {2, 5, 6, 17, 21, 19, 30, 45}.
קשיים מסוימים עלולים להתעורר אם מערכים באורכים שונים ימוזגו. מה אם אחד מהאינדקסים הנוכחיים הגיע לאלמנט האחרון, ועדיין נותרו איברים במערך השני?
int arr1={1, 4}; int arr2={2, 5, 6, 7, 9}; // 1 צעד index1=0, index2=0; 1 2 תוצאה={1, 2}; // 3 step index1=1, index2=1; 4 < 5 תוצאה={1, 2, 4}; //4 step index1=2, index2=1 ??
המשתנה index1 הגיע לערך 2, אבל למערך arr1 אין אלמנט עם האינדקס הזה. הכל פשוט כאן: פשוט העבר את הרכיבים הנותרים של המערך השני למערך שנוצר, תוך שמירה על הסדר שלהם.
result={1, 2, 4, 5, 6, 7, 9};
מצב זה מצביע על הצורךהתאם את אינדקס הסימון הנוכחי לאורכו של המערך המתמזג.
ערכת מיזוג עבור רצפים מסודרים (A ו-B) באורכים שונים:
- אם האורך של שני הרצפים גדול מ-0, השווה את A[0] ו-B[0] והעבר את הקטן יותר למאגר.
- אם אורכו של אחד הרצפים הוא 0, קח את הרכיבים הנותרים של הרצף השני, ובלי לשנות את הסדר שלהם, עבור לסוף המאגר.
יישום השלב השני
דוגמה לחיבור שני מערכים ממוינים ב-Java ניתנת להלן.
int a1=new int {21, 23, 24, 40, 75, 76, 78, 77, 900, 2100, 2200, 2300, 2400, 2500}; int a2=new int {10, 11, 41, 50, 65, 86, 98, 101, 190, 1100, 1200, 3000, 5000}; int a3=new int[a1.length + a2.length]; int i=0, j=0; for (int k=0; k a1.length-1) { int a=a2[j]; a3[k]=a; j++; } else if (j > a2.length-1) { int a=a1; a3[k]=a; i++; } else if (a1 < a2[j]) { int a=a1; a3[k]=a; i++; } else { int b=a2[j]; a3[k]=b; j++; } }
כאן:
- a1 ו-a2 הם המערכים הממוינים המקוריים שיש למזג;
- a3 – מערך סופי;
- i ו-j הם אינדקסים של אלמנטים נוכחיים עבור מערכים a1 ו-a2.
התנאי הראשון והשני מבטיחים שהאינדקסים לא חורגים מגודל המערך. בלוקי התנאי השלישי והרביעי, בהתאמה, מועברים למערך המתקבל של האלמנט הקטן יותר.
הפרד וכבש
אז, למדנו למזג את הממויניםאוספי ערכים. ניתן לומר שהחלק השני של אלגוריתם מיון המיזוג - המיזוג עצמו - כבר ממוין.
עם זאת, אתה עדיין צריך להבין איך להגיע מהמערך המקורי הלא ממוין של מספרים לכמה ממוינים שניתן למזג.
בואו נשקול את השלב הראשון של האלגוריתם ונלמד כיצד להפריד מערכים.
זה לא קשה - רשימת הערכים המקורית מחולקת לשניים, ואז כל חלק גם מפוצלת, וכך הלאה עד שמתקבלים בלוקים קטנים מאוד.
אורכם של אלמנטים מינימליים כאלה יכול להיות שווה לאחד, כלומר, הם יכולים להיות בעצמם מערך ממוין, אבל זה לא תנאי הכרחי. גודל הבלוק נקבע מראש, וניתן להשתמש בכל אלגוריתם מיון מתאים שעובד ביעילות עם מערכים בגדלים קטנים (למשל מיון מהיר או מיון הכנסה) להזמנתו.
זה נראה כך.
// מערך מקורי {34, 95, 10, 2, 102, 70}; // פיצול ראשון {34, 95, 10} ו-{2, 102, 70}; // פיצול שני {34} ו-{95, 10} ו-{2} ו-{102, 70}
הבלוקים המתקבלים, המורכבים מ-1-2 אלמנטים, קלים מאוד לסדר.
לאחר מכן, אתה צריך למזג את המערכים הקטנים שכבר ממוינים בזוגות, תוך שמירה על סדר האיברים, מה שכבר למדנו לעשות.
יישום השלב הראשון
מחיצה רקורסיבית של מערך מוצגת למטה.
void mergeSort(T a, התחלה ארוכה, סיום ארוך) { פיצול ארוך; אם(התחלה < סיום) { פיצול=(התחלה + סיום)/2; mergeSort(a, start, split); mergeSort(a, split+1, finish); מיזוג(א, להתחיל, לפצל, לסיים); } }
מה קורה בקוד הזה:
-
פונקציית ה-mergeSort מקבלת את המערך ההתחלתי
a
ואת הגבול השמאלי והימני של האזור למיון (המדדים מתחילים ו-
- finish).
-
אם האורך של קטע זה גדול מאחד (
start < finish
), אז הוא מפוצל לשני חלקים (לפי אינדקס
- split), וכל אחד מהם ממוין באופן רקורסיבי.
-
בקריאה לפונקציה רקורסיבית עבור הצד השמאלי, אינדקס ההתחלה של העלילה והאינדקס
split
עוברים. עבור הימני, בהתאמה, ההתחלה תהיה
- (פיצול + 1), והסוף יהיה האינדקס האחרון של הקטע המקורי.
-
פונקציה
merge
מקבלת שני רצפים מסודרים (
a[start]…a[split]
ו-
- a[split] +1]…a[סיום]) וממזג אותם לפי סדר מיון.
המכניקה של פונקציית המיזוג נדונה למעלה.
סכמה כללית של האלגוריתם
שיטת מערך המיון של המיזוג מורכבת משני שלבים גדולים:
- פצל את המערך המקורי הלא ממוין לחתיכות קטנות.
- אספו אותם בזוגות, בהתאם לכלל המיון.
משימה גדולה ומורכבת מחולקת להרבה מאוד פשוטים, שנפתרים ברצף, מה שמוביל לתוצאה הרצויה.
הערכת שיטה
מורכבות הזמן של מיון המיזוג נקבעת לפי גובה העץ המפוצלאלגוריתם ושווה למספר האלמנטים במערך (n) כפול הלוגריתם שלו (log n). אומדן כזה נקרא לוגריתמי.
זהו גם יתרון וגם חיסרון של השיטה. זמן הריצה שלו אינו משתנה אפילו במקרה הגרוע ביותר, כאשר המערך המקורי ממוין בסדר הפוך. עם זאת, בעת עיבוד נתונים ממוינים לחלוטין, האלגוריתם אינו מספק רווח זמן.
חשוב גם לשים לב לעלות הזיכרון של שיטת המיזוג. הם שווים לגודל האוסף המקורי. באזור שהוקצה נוסף זה, מורכב מערך ממוין מהחתיכות.
יישום האלגוריתם
מיון מיזוג Pascal מוצג למטה.
Procedure MergeSort(name: string; var f: text); Var a1, a2, s, i, j, kol, tmp: מספר שלם; f1, f2: טקסט; ב: בוליאני Begincol:=0; Assign(f, name); reset(f); אמנם לא EOF(f) תתחיל לקרוא (f, a1); inc(col); סוֹף; close(f); Assign(f1, '{שם קובץ העזר הראשון}'); Assign(f2, '{שם קובץ העזר השני}'); s:=1; בעוד (s<kol) תתחיל איפוס(f); שכתוב (f1); שכתוב (f2); עבור i:=1 לקול div 2 תתחיל Read(f, a1); Write(f1, a1, ' '); סוֹף; אם (kol div 2) mod s0 אז התחל tmp:=kol div 2; בעוד tmp mod s0 מתחילים את Read(f, a1); Write(f1, a1, ' '); inc(tmp); סוֹף; סוֹף; אמנם לא EOF(f) תתחיל Read(f, a2); Write(f2, a2, ' '); סוֹף; close(f); close(f1); close(f2); שכתוב(ו); reset(f1); reset(f2); Read(f1, a1); Read(f2, a2); בעוד (לא EOF(f1)) ו-(לא EOF(f2)) מתחילים ב:=0; j:=0; b:=true; בעוד ש-(ב) ו-(לא EOF(f1)) ו-(לא EOF(f2)) מתחילים אם (a1<a2) אז מתחיליםWrite(f, a1, ' '); Read(f1, a1); inc(i); End else begin Write(f, a2, ' '); Read(f2, a2); inc(j); סוֹף; אם (i=s) או (j=s) אז b:=false; סוֹף; אם לא b אז התחל את While (i<s) ו-(לא EOF(f1)) תתחיל את Write(f, a1, ' '); Read(f1, a1); inc(i); סוֹף; בעוד (j<s) ו-(לא EOF(f2)) מתחילים ב-Write(f, a2, ' '); Read(f2, a2); inc(j); סוֹף; סוֹף; סוֹף; אמנם לא EOF(f1) תתחיל tmp:=a1; Read(f1, a1); אם לא EOF(f1) אז Write(f, tmp, ' ') else Write(f, tmp); סוֹף; אמנם לא EOF(f2) מתחילים את tmp:=a2; Read(f2, a2); אם לא EOF(f2) אז Write(f, tmp, ' ') אחרת Write(f, tmp); סוֹף; close(f); close(f1); close(f2); s:=s2; סוֹף; מחק(f1); מחק(f2); סוף;
מבחינה ויזואלית, פעולת האלגוריתם נראית כך (למעלה - רצף לא מסודר, למטה - מסודר).
מיון נתונים חיצוני
לעתים קרובות מאוד יש צורך למיין נתונים מסוימים הנמצאים בזיכרון החיצוני של המחשב. במקרים מסוימים, הם בגודל מרשים ולא ניתן למקם אותם ב-RAM כדי להקל על הגישה אליהם. במקרים כאלה, נעשה שימוש בשיטות מיון חיצוניות.
הצורך בגישה למדיה חיצונית פוגע ביעילות זמן העיבוד.
מורכבות העבודה היא שהאלגוריתם יכול לגשת רק לרכיב אחד של זרם הנתונים בכל פעם. ובמקרה זה, אחת התוצאות הטובות ביותר מוצגת על ידי שיטת מיון המיזוג, שיכולה להשוות את הרכיבים של שני קבצים ברצף אחד אחרי השני.
קריאת נתונים מאתמקור חיצוני, עיבודם וכתיבתם לקובץ הסופי מתבצעים בלוקים מסודרים (סדרות). לפי אופן העבודה עם גודל סדרות מסודרות, ישנם שני סוגי מיון: מיזוג פשוט וטבעי.
מיזוג פשוט
במיזוג פשוט, אורך הסדרה קבוע.
לכן, בקובץ המקורי הלא ממוין, כל הסדרות מורכבות מאלמנט אחד. לאחר השלב הראשון, הגודל גדל לשניים. הבא - 4, 8, 16 וכן הלאה.
זה עובד כך:
- קובץ המקור (f) מחולק לשניים עזר - f1, f2.
- הם שוב מתמזגים לקובץ אחד (f), אך במקביל כל האלמנטים מושווים בזוגות ובצורה זוגות. גודל הסדרה בשלב זה הופך לשניים.
- שלב 1 חוזר על עצמו.
- שלב 2 חוזר על עצמו, אבל ה-2ים שכבר הוזמנו מתמזגים ליצירת 4s ממוינים.
- הלולאה נמשכת, ומגדילה את הסדרה בכל איטרציה, עד שהקובץ כולו ממוין.
איך אתה יודע שהמיון החיצוני במיזוג פשוט הושלם?
- אורך סדרה חדשה (לאחר מיזוג) לא פחות ממספר הרכיבים הכולל;
- נותר פרק אחד בלבד;
- קובץ עזר f2 נותר ריק.
החסרונות של מיזוג פשוט הם: מכיוון שאורך הריצה קבוע בכל מעבר מיזוג, עיבוד נתונים בהזמנה חלקית ייקח זמן רב כמו נתונים אקראיים לחלוטין.
מיזוג טבעי
שיטה זו אינה מגבילה את האורךסדרה, אבל בוחר את המקסימום האפשרי.
אלגוריתם מיון:
- קריאת הרצף הראשוני מקובץ f. הרכיב המתקבל הראשון נכתב לקובץ f1.
- אם הערך הבא עומד בתנאי המיון, הוא כתוב שם, אם לא, אז לקובץ העזר השני f2.
- באופן זה, כל הרשומות של קובץ המקור מופצות, ונוצר רצף מסודר ב-f1, שקובע את הגודל הנוכחי של הסדרה.
- קבצים f1 ו-f2 ממוזגים.
- המחזור חוזר.
בשל גודלה הלא קבוע של הסדרה, יש צורך לסמן את סוף הרצף בתו מיוחד. לכן, בעת מיזוג, מספר ההשוואות עולה. בנוסף, הגודל של אחד מקבצי העזר עשוי להיות קרוב לגודל המקור.
בממוצע, מיזוג טבעי יעיל יותר ממיזוג פשוט עם מיון חיצוני.
תכונות האלגוריתם
כאשר משווים שני ערכים זהים, השיטה שומרת על הסדר המקורי שלהם, כלומר, היא יציבה.
ניתן לפצל בהצלחה רבה את תהליך המיון למספר שרשורים.
הסרטון מדגים בבירור את פעולתו של אלגוריתם מיון המיזוג.
