תוכן העניינים
1. הקדמה
אלגוריתמי מיון במדעי המחשב משמשים לסידור נתונים בסדר עולה או יורד. ישנם אלגוריתמי מיון מרובים עם מאפיינים שונים זמינים. מיזוג מיון היא אחת השיטות ב-C++ שיכולה למיין את המערכים.
2. מה זה מיזוג מיון ב-C++
מיון מיזוג משתמש בטכניקת הפרד-וכבש שיכולה לסדר את האלמנטים של מערך. זה יכול גם למיין את רשימת האלמנטים ב-C++. הוא מפצל את הקלט לשני חצאים, ממיין כל חצי באופן עצמאי ואז ממזג אותם בסדר הנכון.
3. גישת הפרד ומשול
אלגוריתם המיון מיישם אסטרטגיית חלוקה-וכבוש, הכוללת חלוקה של מערך הקלט למערכים קטנים יותר, פתרון אותם בנפרד, ולאחר מכן מיזוג התוצאות כדי לייצר פלט ממוין. במקרה של מיון מיזוג, המערך מחולק באופן רקורסיבי לשני חצאים עד שנשאר רק אלמנט אחד בכל חצי.
4. מיזוג אלגוריתם מיון
אלגוריתם מיון המיזוג מורכב משני שלבים עיקריים: חלוקה ומיזוג. השלבים הם כדלקמן:
4.1 חלוקה
אלגוריתם מיון המיזוג עוקב אחר אסטרטגיית חלוקה-וכבש למיון אלמנטים במערך.
- השלב הראשון באלגוריתם יבדוק רכיבי מערך. אם הוא מכיל אלמנט אחד, אז הוא כבר נחשב לממוין, והאלגוריתם יחזיר את אותו מערך ללא כל שינוי.
- אם המערך מכיל יותר מאלמנט אחד, האלגוריתם ממשיך לחלק אותו לשני חצאים: החצי השמאלי והחצי הימני.
- לאחר מכן, אלגוריתם מיון המיזוג מיושם באופן רקורסיבי על החצאים השמאלי והימני של המערך, למעשה מחלק אותם למערכי משנה קטנים יותר וממיין אותם בנפרד.
- תהליך רקורסיבי זה ממשיך עד שתת-מערכים מכילים רק אלמנט אחד כל אחד (לפי שלב 1), ובשלב זה ניתן למזג אותם כדי לייצר מערך פלט סופי וממוין.
4.2 מיזוג
כעת נראה את השלבים למיזוג המערכים:
- השלב הראשון עבור אלגוריתם מיון המיזוג כולל יצירת מערך ריק.
- לאחר מכן האלגוריתם ממשיך להשוות את האלמנטים הראשונים של החצאים השמאלי והימני של מערך הקלט.
- הקטן מבין שני האלמנטים מתווספים למערך החדש ולאחר מכן מוסרים מהמחצית המתאימה שלו ממערך הקלט.
- לאחר מכן חוזרים על שלבים 2-3 עד שאחד החצאים מתרוקן.
- כל הרכיבים שנותרו בחצי הלא ריק מתווספים למערך החדש.
- המערך המתקבל ממוין כעת במלואו ומייצג את הפלט הסופי של אלגוריתם מיון המיזוג.
5. יישום מיזוג מיון ב-C++
כדי ליישם מיון מיזוג ב-C++ מתבצעות שתי שיטות שונות. מורכבות הזמן של שתי השיטות שווה ערך, אך השימוש שלהן במערכים משנה זמניים שונה.
השיטה הראשונה למיון המיזוג ב-C++ משתמשת בשני מערכי משנה זמניים, בעוד שהשנייה משתמשת רק באחד. ראוי לציין שהגודל הכולל של שני מערכי המשנה הזמניים בשיטה הראשונה שווה לגודל המערך המקורי בשיטה השנייה, ולכן מורכבות החלל נשארת קבועה.
שיטה 1 - שימוש בשני מערכי משנה זמניים
הנה תוכנית לדוגמה למיזוג מיון ב-C++ באמצעות שיטה 1, המשתמשת בשני מערכי משנה זמניים:
#includeבאמצעות מרחב שמות std ;
בָּטֵל לְמַזֵג ( int arr [ ] , int ל , int M , int ר )
{
int n1 = M - ל + 1 ;
int n2 = ר - M ;
int ל [ n1 ] , ר [ n2 ] ;
ל ( int אני = 0 ; אני < n1 ; אני ++ )
ל [ אני ] = arr [ ל + אני ] ;
ל ( int י = 0 ; י < n2 ; י ++ )
ר [ י ] = arr [ M + 1 + י ] ;
int אני = 0 , י = 0 , ק = ל ;
בזמן ( אני < n1 && י < n2 ) {
אם ( ל [ אני ] <= ר [ י ] ) {
arr [ ק ] = ל [ אני ] ;
אני ++;
}
אַחֵר {
arr [ ק ] = ר [ י ] ;
י ++;
}
ק ++;
}
בזמן ( אני < n1 ) {
arr [ ק ] = ל [ אני ] ;
אני ++;
ק ++;
}
בזמן ( י < n2 ) {
arr [ ק ] = ר [ י ] ;
י ++;
ק ++;
}
}
בָּטֵל MergeSort ( int arr [ ] , int ל , int ר )
{
אם ( ל < ר ) {
int M = ל + ( ר - ל ) / 2 ;
MergeSort ( arr , ל , M ) ;
MergeSort ( arr , M + 1 , ר ) ;
לְמַזֵג ( arr , ל , M , ר ) ;
}
}
int רָאשִׁי ( )
{
int arr [ ] = { 12 , אחד עשר , 13 , 5 , 6 , 7 } ;
int arr_size = מידה של ( arr ) / מידה של ( arr [ 0 ] ) ;
cout << 'מערך נתון הוא \n ' ;
ל ( int אני = 0 ; אני < arr_size ; אני ++ )
cout << arr [ אני ] << '' ;
MergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n מערך ממוין הוא \n ' ;
ל ( int אני = 0 ; אני < arr_size ; אני ++ )
cout << arr [ אני ] << '' ;
לַחֲזוֹר 0 ;
}
בתוכנית זו, פונקציית המיזוג לוקחת שלושה ארגומנטים arr, l ו-r, המייצגים את המערך שיש למיין ומציגה את המדדים של תת-המערך שצריך למזג. הפונקציה מוצאת תחילה את הגדלים של שני מערכי המשנה שיש למזג, ואז יוצרת שני מערכי משנה זמניים L ו-R כדי לאחסן את האלמנטים של מערכי המשנה הללו. לאחר מכן הוא משווה את האלמנטים ב-L ו-R וממזג אותם למערך המקורי ששמו arr בסדר עולה.
טכניקת החלוקה-וכבש משמשת על ידי פונקציית ה-mergeSort כדי לפצל את המערך לשני חצאים באופן רקורסיבי עד שנותר רק אלמנט אחד בחוץ בתת-המערך. לאחר מכן הוא ממזג את שני מערכי המשנה למערך משנה ממוין. הפונקציה ממשיכה למזג את מערכי המשנה אלא אם היא ממיינת את המערך השלם.
בפונקציה הראשית, אנו מגדירים מערך arr עם 6 אלמנטים וקוראים לפונקציה mergeSort כדי למיין אותו. בסוף הקוד מודפס המערך הממוין.
שיטה 2 - שימוש במערך משנה טמפ' אחד
הנה תוכנית לדוגמה למיזוג מיון ב-C++ באמצעות שיטה 2, המשתמשת במערך משנה זמני יחיד:
#includeבאמצעות מרחב שמות std ;
בָּטֵל לְמַזֵג ( int arr [ ] , int ל , int M , int ר )
{
int אני , י , ק ;
int n1 = M - ל + 1 ;
int n2 = ר - M ;
// צור מערכי משנה זמניים
int ל [ n1 ] , ר [ n2 ] ;
// העתק נתונים למערכים משנה
ל ( אני = 0 ; אני < n1 ; אני ++ )
ל [ אני ] = arr [ ל + אני ] ;
ל ( י = 0 ; י < n2 ; י ++ )
ר [ י ] = arr [ M + 1 + י ] ;
// מיזוג את מערכי המשנה הזמניים בחזרה למערך המקורי
אני = 0 ;
י = 0 ;
ק = ל ;
בזמן ( אני < n1 && י < n2 ) {
אם ( ל [ אני ] <= ר [ י ] ) {
arr [ ק ] = ל [ אני ] ;
אני ++;
}
אַחֵר {
arr [ ק ] = ר [ י ] ;
י ++;
}
ק ++;
}
// העתק את הרכיבים הנותרים של L[]
בזמן ( אני < n1 ) {
arr [ ק ] = ל [ אני ] ;
אני ++;
ק ++;
}
// העתק את הרכיבים הנותרים של R[]
בזמן ( י < n2 ) {
arr [ ק ] = ר [ י ] ;
י ++;
ק ++;
}
}
בָּטֵל MergeSort ( int arr [ ] , int ל , int ר )
{
אם ( ל < ר ) {
int M = ל + ( ר - ל ) / 2 ;
// מיין את החצאים השמאלי והימני באופן רקורסיבי
MergeSort ( arr , ל , M ) ;
MergeSort ( arr , M + 1 , ר ) ;
// למזג את שני החצאים הממוינים
לְמַזֵג ( arr , ל , M , ר ) ;
}
}
int רָאשִׁי ( )
{
int arr [ ] = { 12 , אחד עשר , 13 , 5 , 6 , 7 } ;
int arr_size = מידה של ( arr ) / מידה של ( arr [ 0 ] ) ;
cout << 'מערך נתון הוא \n ' ;
ל ( int אני = 0 ; אני < arr_size ; אני ++ )
cout << arr [ אני ] << '' ;
MergeSort ( arr , 0 , arr_size - 1 ) ;
cout << ' \n מערך ממוין הוא \n ' ;
ל ( int אני = 0 ; אני < arr_size ; אני ++ )
cout << arr [ אני ] << '' ;
לַחֲזוֹר 0 ;
}
תוכנית זו היא כמו הקודמת, אך במקום להשתמש בשני מערכי משנה זמניים L ו-R, היא משתמשת בטמפ' תת-מערך זמנית יחידה. פונקציית המיזוג פועלת באותו אופן כמו קודם, אבל במקום להעתיק את הנתונים ל-L ו-R, היא מעתיקה אותם ל-temp. לאחר מכן הוא ממזג אלמנטים של מערך זמני בחזרה לתוך arr שהוא המערך המקורי.
הפונקציה mergeSort זהה לקודמתה, אלא שהיא משתמשת ב-temp במקום L ו-R כדי לאחסן את המשנה הזמני.
בפונקציה הראשית, אנו מגדירים מערך arr עם 6 אלמנטים וקוראים לפונקציה mergeSort כדי למיין אותו. ביצוע הקוד מסתיים בהדפסת המערך הממוין על המסך.
סיכום
מיון מיזוג הוא אלגוריתם שממיין אלמנטים של מערך, והוא משתמש בטכניקת הפרד-וכבש ומבצע השוואות בין אלמנטים. למיזוג מיון ב-C++ יש מורכבות זמן של O(n log n) והוא יעיל במיוחד למיון מערכים גדולים. למרות שהוא דורש זיכרון נוסף כדי לאחסן את מערכי המשנה הממוזגים, היציבות שלו הופכת אותו לבחירה פופולרית למיון.