כיצד ליישם מיון מיזוג ב- C ++ עם דוגמאות

מהו מיון המיזוג? מיון מיזוג הוא אלגוריתם מיון מבוסס השוואה השייך לקטגוריית החלוקה והכיבוש. מיון מיזוג משמש למיון מערך המבוסס על אסטרטגיית החלוקה והכיבוש אשר יוסקר בקצרה בפוסט זה יחד עם מושגים אחרים כגון האלגוריתם שלו עם דוגמה. נבחן גם את מורכבות הזמן של מיון המיזוג ב- C ++

המצביעים הבאים יוסקרו במאמר זה,

• לחלק ולכבוש אלגוריתם
• הבנת האלגוריתם למיון מיזוג עם דוגמה
• פסאוד-קוד למיון מיזוג
• תוכנית ב- C ++ עבור מיזוג מיון
• מורכבות הזמן עבור מיזוג מיון

ממשיך הלאה עם מאמר זה על מיזוג מיון ב- C ++

אלגוריתם לחלק ולכבוש

אם אתה כבר מכיר את האופן שבו quicksort עובד, אתה עשוי להיות מודע לאסטרטגיית החלוקה והכיבוש. לחלק ולכבוש שלושה שלבים עיקריים. להבנת שלבים אלה נשקול מערך שלום [] בעל אינדקס התחלתי 'a' וסוף אינדקס 'n' ומכאן נוכל לכתוב את המערך שלנו באופן הבא שלום [a & hellip..n]

לחלק - המהלך העיקרי או הצעד העיקרי של חלוקה וכיבוש הוא לחלק את הבעיה הנתונה לבעיות משנה או לחלקי משנה. המלכוד כאן הוא שתתי הבעיות צריכות להיות דומות לבעיה המקורית וקטן יותר בגודלן. במקרה שלנו נחלק את המערך שלנו לשני חצאים [a & hellip.m] [m + 1 & hellip..n] m שוכב באמצע אינדקס a ו- n

לכבוש- לאחר שסיימנו לחלק את הבעיה שלנו לבעיות משנה. אנו פותרים את בעיות המשנה הללו באופן רקורסיבי.

שלב- בשלב זה אנו משלבים את כל הפתרונות של בעיות המשנה שלנו בצורה הולמת. במילים אחרות, אנו משלבים שני מערכים ממוינים שונים כדי ליצור מערך ממוין אחד. שם יש לנו את המערך הממוין שלנו.

ממשיך הלאה עם מאמר זה על מיזוג מיון ב- C ++

מערך java של אובייקטים לדוגמא

הבנת אלגוריתם המיזוג עם דוגמה

בשלב זה אנו יודעים איזו גישה תשתמש במיון המיזוג. לכן, בואו ניקח בחשבון דוגמא ונעבור על כל שלב מ- Hello [] ללא סדר למערך ממוין.
דוגמה- שלום [10, 3, 7, 1, 15, 14, 9, 22]

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

1. ראשית, שקלנו מערך שלום [10, 3, 7, 1, 15, 14, 9, 22] במערך זה ישנם 8 אלמנטים בסך הכל.

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

3. לאחר החלוקה הראשונה, יש לנו 2 חלקים המורכבים מ -4 יסודות כל אחד. בואו נסתכל על המחצית הראשונה [10, 3, 7, 1].

4. אנו מחלקים [10, 3, 7, 1] לשני חלקים [10, 3] ו- [7, 1]. לאחר מכן אנו מחלקים אותם הלאה ל- [10], [3], [7], [1]. חלוקה נוספת אינה אפשרית מכיוון שאיננו יכולים לחשב מ '. רשימה המכילה אלמנט יחיד נחשבת תמיד כממוינת.

5. כיצד מתבצע מיזוג? בוא נגלה. ראשית [10] ו- [3] מושווים וממוזגים בסדר עולה [3, 10] באותו אופן שנקבל [1, 7]

6. לאחר מכן, אנו משווים את [3, 10] ו- [1, 7]. לאחר השוואה אנו ממזגים אותם בסדר עולה ומקבלים [1, 3, 7, 10].

7. [15, 14, 9, 2] גם מחולק ומשולב בצורה דומה לצורה [9, 14, 15, 22].

8. בשלב האחרון אנו משווים ומשלבים [15, 14, 9, 2] [9, 14, 15, 22] כדי לתת לנו את המערך הממוינו שלנוכלומר [1, 3, 7, 9, 10, 14, 15, 22].

ממשיך הלאה עם מאמר זה על מיזוג מיון ב- C ++

סדר עולה c ++

פסאוד-קוד למיון מיזוג

התחל אם עזב
הפונקציה mergeSort () קוראת לעצמה רקורסיבית לחלק את המערך שלנו עד שהוא הופך לאלמנט יחיד והפונקציה מיזוג () משמשת למיזוג המערכים הממוינים.
  ממשיך הלאה עם מאמר זה על מיזוג מיון ב- C ++
 מיזוג תוכנית מיון ב- C ++ 
#include #include #include באמצעות מרחב השמות std מיזוג ריק (int a [], int Firstindex, int m, int Lastindex) // ממזג את מערכי המשנה שנוצרים תוך חלוקה void mergeSort (int a [], int Firstindex, int Lastindex) {if (Firstindexגודל int שלום [גודל], אני מתכוון<<'Enter the elements of the array one by one:n' for(i=0 i>שלום [i] mergeSort (שלום, 0, גודל - 1) cout<<'The Sorted List isn' for(i=0 i
 תְפוּקָה- 
ממשיך הלאה עם מאמר זה על מיזוג מיון ב- C ++
 מורכבות זמן 
מורכבות הזמן היא היבט חשוב שיש לקחת בחשבון כאשר אנו מדברים על אלגוריתמים. מיון מיזוג נחשב למורכבות זמן רבה בהשוואה לאלגוריתמי מיון אחרים.
זמן הריצה הגרוע ביותר- O (n יומן n) 
זמן הריצה הטוב ביותר- O (n יומן n) 
זמן ריצה ממוצע- O (n יומן n)
עם זאת, אנו מגיעים לסוף מאמר מיזוג זה ב- C ++. אם ברצונך ללמוד עוד, עיין ב   מאת אדוריקה, חברת למידה מקוונת אמינה. קורס ההכשרה וההסמכה של Java J2EE ו- SOA של אדוריקה נועד להכשיר אותך לקונספטים מרכזיים של Java וגם עם מסגרות Java שונות כמו Hibernate & Spring.
 יש לך שאלה עבורנו? אנא הזכיר זאת במדור התגובות בבלוג זה ונחזור אליך בהקדם האפשרי.