[Powered by Google Translate] [מיון מיזוג]
[רוב אודן - אוניברסיטת הרווארד]
[זה CS50. - CS50.TV]
בואו נדבר על סוג המיזוג.
עד כה ראה את מיון בועות, מיון הכנסה, ומיון בחירה.
למרות שאני יהיה סוג של גל היד שלי על מה שאני מתכוון טוב יותר,
סוג למזג בדרך מבצע טוב יותר מכל 3 סוגים אלה.
>> אבל לפני שמדבר על סוג המיזוג, בואו נדבר על מיזוג 2 רשימות ממוינות.
אנחנו קוראים לתהליך של לקיחת 2 רשימות ממוינות, כמו אלה,
ועושה רשימה אחת ממוינת מתוכם - ממזג את הרשימות.
איך אנחנו יכולים לעשות את זה?
ובכן, רעיון אחד הוא פשוט להיצמד רשימה אחת על סוף הרשימה השנייה
ולאחר מכן למיין את הרשימה שהתקבלה.
>> אמנם זה עובד, זה הרבה עבודה מיותרת.
אנחנו יכולים לעשות את זה מהר יותר מאשר רק מיון.
שים לב שרעיון שגוי אחד הוא פשוט לקחת את הכוסות לסירוגין מכל רשימה.
למרות שאולי נראה כמו זה עובד בהתחלה,
עושה שאנחנו בסופו של דבר עם 4, 8, 15, 23, 16 - הודעה כי 16 ו 23 נמצאים מחוץ למקום.
הסיבה לכך היא 2 אלמנטים שצריכים להופיע ברציפות ברשימה הממוזגת
הם באותה הרשימה ראשונית.
בני 15 ו 16 נמצא ברשימה בצד השמאל.
החוכמה היא לנצל את העובדה ששני הרשימות כבר מסודרות.
זה אומר שאם אנחנו רק מסתכלים על האלמנטים הראשונים של שתי הרשימות -
כאן, 4 ו 8 - אחד מהם חייבות להיות גם המרכיב הראשון ברשימה הממוזגת.
ובכן, מדוע זה כך?
שתי הרשימות הללו כבר מסודרים,
וכך גם 4 או 8 חייבים להיות האלמנט הקטן ביותר כאשר אנו משלבים את 2 רשימות.
במקרה זה, הקטן ביותר הוא 4,
כדי שנוכל להוציא 4 ולהפוך אותו לאלמנט הראשון של הרשימה הממוזגת שלנו.
עכשיו אנחנו ממשיכים ממזגים את 3 אלמנטים הנותרים של הרשימה הראשונה
ו 4 אלמנטים של הרשימה השנייה.
>> שוב, אנחנו צריכים רק להסתכל על האלמנט הראשון של שתי הרשימות.
הקטן יותר של 2 חייב להיות המרכיב השני ברשימה הממוזגת שלנו.
הפעם, בין 8 ל 15 הקטנים ביותר הוא 8, ולכן אנחנו מוסיפים כי
כמרכיב השני ברשימה הממוינת שלנו.
אנחנו יכולים להמשיך להשוות את המרכיבים הראשונים של שתי הרשימות
והסרה קטנה יותר של 2.
השוואה בין 15 ל 23, 15 היא קטנה יותר ואז זה האלמנט השלישי שלנו.
עכשיו משווה 16 ו 23, 16 הם קטנים יותר.
אז זה היסוד הרביעי.
>> שים לב כי 2 אלמנטים הגיעו מאותה הרשימה ברציפות.
זו הסיבה שהרשימה הממוזגת לא יכולה רק יסודות חלופיים מאת 2 הרשימות.
השוואה בין 50 ל 23, 23 היא קטנה יותר, ולכן אנחנו בוחרים את זה.
בין 50 ל 42, 42 הם קטנים יותר.
בין 50 ל 108, 50 הם קטנים יותר.
ולבסוף, יש לנו רק 108, כך שהוא חייב ללכת בסוף הרשימה שלנו.
שים לב שיש לנו רשימה יפה, מסודרת.
בכל פעם שהשווינו את 2 המרכיבים הראשונים של את 2 רשימות
היינו יכול לקבוע את האלמנט הבא ברשימה הממוזגת.
זה אומר שאם את הרשימה הסופית מכילה מספרי n, כאשר n כאן הוא 8,
אז אנחנו צריכים ברוב השוואות n כדי לקבל את כל המספרים האלה למקום הנכון.
כגון אלגוריתם אמר לרוץ בזמן ליניארי,
אבל אל תדאגו בקשר לזה כאן.
>> באמצעות האלגוריתם שלנו למיזוג, אנחנו יכולים לעשות את אלגוריתם מיון מיזוג מהיר.
אז, בואו לאפס את הרשימות שלנו.
ישנם 2 צעדים גדולים בתהליך של מיון מיזוג.
ראשית, ברציפות לפצל את הרשימה של כוסות לחצי
עד שיש לנו חבורה של רשימות רק עם 1 הכוס ב.
אל תדאגו אם רשימה מכילה מספר אי זוגי
ואתה לא יכול לעשות חתך נקי לחלוטין ביניהם.
רק באופן שרירותי לבחור לאיזו רשימה שתכלול את הכוס הנוספת פנימה
אז, בואו לפצל הרשימות האלה.
עכשיו יש לנו 2 רשימות.
עכשיו יש לנו 4 רשימות.
>> ועכשיו יש לנו 8 רשימות עם כוס אחת בכל רשימה.
אז זהו זה לשלב 1.
עבור שלב 2, אנחנו שוב ושוב למזג זוגות של רשימות באמצעות אלגוריתם המיזוג שלמדנו בעבר.
מיזוג 108 ו 15, אנחנו בסופו של דבר עם הרשימה 15, 108.
מיזוג 50 ו 4, אנחנו בסופו של דבר עם 4, 50.
מיזוג 8 ו 42, אנחנו בסופו של דבר עם 8, 42.
ומיזוג של 23 ו 16, אנחנו בסופו של דבר עם 16, 23.
עכשיו כל הרשימות שלנו הן בגודל 2.
שים לב שכל אחד 4 הרשימות ממוינת.
>> אז אנחנו יכולים להתחיל התמזגות זוגות של רשימות שוב.
מיזוג 15 ו 108 ו 4 ו 50 -
קודם כל לקחת 4, אז 15, אז 50, אז 108.
מיזוג 8, 42 ו 16, 23,
אנו לוקחים 1 8, 16, 23 אז, ולאחר מכן 42.
אז עכשיו יש לנו רק 2 רשימות של גודל 4, כל אחד מהם ממוין.
אז עכשיו אנחנו למזג 2 הרשימות האלה.
ראשית אנחנו לוקחים 4.
אז אנחנו לוקחים 8.
אנחנו לוקחים את 15 ו 16, אז 23, אז בן 42, אז 50, אז 108.
ואנחנו נעשינו.
עכשיו יש לנו רשימה ממוינת.
אז כמה מהר היה זה בדיוק?
במונחים טכניים, מעין מיזוג הוא O (n log n),
ואילו כל מיון בועות, מיון הכנסה, ומיון בחירה הוא O (n ²).
למעשה, כפי שאתה תלמד בקרוב, אתה לא תוכל לבוא עם סוג
המבצעת טובה יותר מאשר O (n log n) במקרה הכללי.
שוב, אל תדאגו סימון O גדול זה אם אתה לא ראית אותו עדיין.
>> רק יודע שזה אומר שאם אנחנו רוצים למיין רשימה גדולה באמת
מיון בועות, מיון הכנסה, ובחירת סוג עלול לקחת
באופן משמעותי יותר מאשר למזג מיון.
זה לא אומר שסוג המיזוג יהיה מהיר יותר לכל הרשימות
או אפילו לכל רשימה אחת מתחת לגודל מסוים.
לדוגמה, סוג ההכנסה עלול להיות מהסוג המהיר ביותר עבור כל הרשימות קטנות יותר מ 5 אלמנטים.
בפועל, מעין מיזוג הוא בדרך כלל מהר יותר לרשימות קטנות כמו 50 אלמנטים.
>> אבל מהירות נוספת זה לא באה ללא מחיר.
בניגוד למינים האחרים שלנו, אשר לוקח את הרשימה ולשנות את הרשימה במקום
עד שנגיע לרשימה ממוינת, מעין מיזוג צריך מרחב נוסף
למזג 2 רשימות יחד.
אנחנו לא יכולים להשתמש באופן מיידי את הרשימות שנמצאים מוזגו כדי לאחסן את הרשימה הממוזגת
מאז שעשוי לעקוף אלמנטים שעדיין צריכים להיות ממוזגים.
המרחב הזה הוא קצת מחיר, אבל זה בדרך כלל אינו בלתי סביר.
וזהו זה לסוג המיזוג.
>> השם שלי הוא רוב אודן, וזה CS50.
[CS50.TV]
- בחירה ומיון.
[צוחק]
אה, יש גם לקחת את זה כי אני עברתי איך אני מציג אותו.
רשימה בצד השמאל. זה היה טעות דפוס.
[Misspoke] אני דפוק -
[צוחק]
אני לא יודע מה -