[השמעת מוסיקה] 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

אני דאג לויד. זה CS50.