[Powered by Google Translate] [מיון הכנסה] [טומי MacWilliam] [אוניברסיטת הרווארד] [זה CS50.TV] בואו נסתכל על סוג ההכנסה, אלגוריתם לקחת רשימה של מספרים ומיונם. אלגוריתם, לזכור, הוא פשוט הליך צעד אחר צעד להשגת משימה. הרעיון הבסיסי מאחורי סוג ההכנסה, הוא לחלק את הרשימה שלנו לשני חלקים, חלק ממוין וחלק לא ממוין. 

בכל צעד של האלגוריתם, מספר מועבר מהחלק הממוין לחלק הממוין עד סופו של דבר את כל הרשימה ממוינת. הנה לך הרשימה של שישה מספרים לא ממוינים - 23, 42, 4, 16, 8, ו 15. מכיוון שמספרים אלה לא כל בסדר עולים, הם לא ממוינים. מאחר שלא פתח במיון עדיין, תשקלו את כל ששת אלמנטי החלק הממוין שלנו. 

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

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

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

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

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

בסדר. עכשיו, יש לנו ארבעה אלמנטים ממוינים ושני אלמנטים לא ממוינים. אז, בואו נעבור 8 לתוך החלק מסודר. שמונה הם פחות מ 42. שמונה הם פחות מ 23. ו8 הם פחות מ 16. אבל 8 גדולים מ 4. אז, הייתי רוצה להכניס 8 בין 4 ל 16. ועכשיו אנחנו רק צריכים עוד אלמנט אחד עזב למיין - 15. חמישה עשרה הם פחות מ 42, חמישה עשרה הם פחות מ 23. ו 15 הם פחות מ 16. אבל 15 גדול מ 8. 

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

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

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

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

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

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

זה אומר שיש סוג ההכנסה במקרה הטוב ביותר את ביצועים של n, שאנו מייצגים בΩ (n). וזהו זה לסוג ההכנסה, רק אחד מהאלגוריתמים הרבים אנו יכול להשתמש כדי למיין רשימה. השמי הוא טומי, וזה CS50. [CS50.TV] אה, אתה פשוט לא יכול לעצור את זה ברגע שהוא מתחיל. אה, עשינו את זה - בום! >>