תוֹכֶן

• טבלת השוואה
• הגדרה של מיון מהיר
• הגדרת סוג מיזוג
• סיכום

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

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

1. 1. טבלת השוואה
   2. הגדרה
   3. הבדלים עיקריים
   4. סיכום

טבלת השוואה

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

הגדרה של מיון מהיר

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

נניח ש- A הוא מערך A, A, A, …… .., A של מספר n שצריך למיין. אלגוריתם המיון המהיר מורכב מהשלבים הבאים.

1. האלמנט הראשון או כל אלמנט אקראי שנבחר כמפתח, מניחים מקש = A (1).
2. המצביע "נמוך" ממוקם במקצה השני ומצביע "למעלה" ממוקם באלמנט האחרון של המערך, כלומר נמוך = 2 ומעלה = n;
3. בעקביות, הגדילו את המצביע “נמוך” במיקום אחד עד (מקש A).
4. באופן קבוע, צמצם את המצביע "למעלה" במיקום אחד עד (A <= מקש).
5. אם למעלה הוא גדול ממחלף A נמוך עם A.
6. חזור על שלב 3,4 ו- 5 עד שהמצב בשלב 5 נכשל (כלומר למעלה <= נמוך) ואז מחלף A למפתח.
7. אם האלמנטים השמאלי של המפתח קטנים יותר מהמפתח והאלמנטים מימין למפתח גדולים מהמפתח, המערך מחולק לשני מערכי משנה.
8. הנוהל שלעיל מיושם שוב ושוב על הסובלים עד למיון המערך כולו.

   

   
   

יתרונות וחסרונות

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

הגדרת סוג מיזוג

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

תן ל- A להיות מערך מספר n של אלמנטים שיש למיין A, A, ..........., A. סוג המיזוג עוקב אחר השלבים הנתונים.

1. פצל את המערך A למערך המשנה הממוין בערך n / 2 לפי 2, מה שאומר שהאלמנטים במערכי המשנה (A, A), (A, A), (A, A), (A, A) חייבים להיות בסדר ממוין.
2. שלב כל זוג זוגות בכדי להשיג את רשימת הסוביות הממוינות בגודל 4; האלמנטים בסוביות הם גם בסדר ממוין, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. שלב 2 מבוצע שוב ושוב עד שיש רק מערך אחד ממוין בגודל n.

   

יתרונות וחסרונות

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

1. במיזוג המיזוג, יש לחלק את המערך לשני חצאים בלבד (כלומר n / 2). לעומת זאת, במין מהיר, אין כפיה לחלק את הרשימה לאלמנטים שווים.
2. המורכבות במקרה הגרוע ביותר של סוג מהיר היא O (n²) מכיוון שצריך הרבה יותר השוואות במצב הגרוע ביותר. לעומת זאת, למיון מיזוג יש את אותם המקרים הגרועים ביותר ומורכבות המקרים הממוצע, כלומר O (n log n).
3. סוג מיזוג יכול לפעול היטב בכל סוג של ערכות נתונים בין אם זה גדול או קטן. נהפוך הוא, הסוג המהיר לא יכול לעבוד טוב עם מערכי נתונים גדולים.
4. מיון מהיר מהיר יותר ממיון מיזוג במקרים מסוימים, למשל עבור ערכות נתונים קטנות.
5. מיון מיזוג דורש שטח זיכרון נוסף לאחסון מערכי העזר. מצד שני, המיון המהיר אינו דורש הרבה מקום לאחסון נוסף.
6. מיזוג מיון יעיל יותר ממיון מהיר.
7. המיון המהיר הוא שיטת מיון פנימית בה הנתונים המותאמים למיון מותאמים בכל פעם בזיכרון הראשי. לעומת זאת, מיון המיזוג הוא שיטת מיון חיצונית, שבה לא ניתן להכיל את הנתונים שיש למיין בזיכרון בו זמנית ויש להקפיד שיש לשמור בזיכרון העזר.

סיכום

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