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

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

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

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

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

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

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

ואני יודע שקרה ב חלק מהמקרים שלך שבוע. אז חזרתי וידני regraded הקוד של כולם. בעתיד אם כי, בבקשה, בבקשה לוודא שאתה מפעיל לבדוק 50 בקוד שלך. כי זה סוג של כאב לת"א יש לחזור וידני regrade כל pset לכל מופע יחיד, קטן החמיץ. אז לא לקחת את כל נקודות. אני חושב שאני המראתי אולי אחד או שניים לעיצוב. בעתיד אם כי, אם אתה נכשל check50, נקודות תילקח את התקינות. 

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

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

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

קהל: אתה אומר ש יכול להוריד אחד psets? 

ANDI פנג: כן. אז יש תשע psets כולל במהלך הסמסטר. ואם יש לך היקף points-- כך היקף הוא פשוט, די הרבה, אתה מנסה בעיה, אתה מניח בזמן, אתה מראה שיש לך הוכחנו שקראת את המפרט. זה פחות או יותר היקף. ואם אתה ממלא נקודות היקף, ש יכול לרדת הנמוך ביותר אחד מתוך היקף מלא. אז זה ביתרון שלך ל להשלים ולנסות כל pset. 

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

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

קהל: היו לנו גלידה. 

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

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

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

אז חידון 0 יהיה 14 אוקטובר אם אתה בקטע יום שני, רביעי ל -15 באוקטובר, אם אתה ב סעיף יום שלישי יום חמישי. זה אינו חל על אלו מכם בהרווארד who-- אני חושב שכולכם אהיה לוקח החידונים שלך על ה -14. 

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

קהל: אז החידון הוא הולך להיות במהלך הרצאה? 

ANDI פנג: כן. אז החידון, אני חושב, הוא 60 דקות שהוקצו שבמשבצת הזמן שרק תיקח באולם ההרצאות. אז אתה לא צריך לבוא ב ב, כמו, 19:00 אקראיים. הכל טוב. כן. מגניב. 

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

אז עד עכשיו, אני חושב ש יש כבר שני דברים תלמידים היו בדרך כלל עושה כאשר באגים psets. אחד, הם גם להוסיף ב printf () - כך כל כמה שורות, הם מוסיפים בprintf () - הו, מה הוא משתנה זה? הו, מה הוא משתנה זה now-- ואתה סוג של לראות את ההתקדמות הקוד שלך כפי שהוא פועל. או השיטה השנייה ילדים לעשות היא כי הם פשוט לכתוב את כל העניין ואז ללכת ככה בסוף. אני מקווה שזה עובד. אני מבטיח לך, GDB הוא טוב יותר משתי שיטות אלה. כן. אז זה יהיה החבר הכי טוב שלך החדש. כי זה דבר יפה כי מבחינה ויזואלית מציג שני מה הקוד שלך עושה בנקודה מסוימת כמו גם מה שכולכם משתנים נושאים, כמו מה הם הערכים שלהם, שבנקודה מסוימת. ובדרך זו, אתה באמת יכול להגדיר נקודות עצירה בקוד שלך. אתה יכול לרוץ דרך שורה אחרת שורה. וGDB רק צריך ל אתה, מוצג לך, מה כל המשתנים שלך הם, מה הם עושים, מה קורה בקוד. ובאופן כזה, זה כך הרבה יותר קל לראות מה שקורה במקום printf-ing או לכתוב את הדברים שלך. 

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

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

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

אז עם זאת, בעוד שהקוד הזה הוא מאוד יפה, זה לא עובד כמו שצריך. אז בואו לרוץ check50 על זה. בדוק 50 20-- OOP. 2? האם pset2 ש? כן. אה, pset1. אוקיי. אז אנחנו רצים check50. 

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

אוקיי. אז בואו לראות, אחד מ בדיקות שנכשלתי בcheck50 היה ערך הקלט של 0.41. אז את התשובה הנכונה ש אתה צריך לקבל הוא 4. אבל במקום מה שאני מדפיס את הוא 3-n, שאינו נכון. אז בואו פשוט להפעיל את זה באופן ידני, רק לוודא שcheck50 עובד. בואו לעשות ./greedy. אופס, אני צריך לעשות חמדנים. הנה. עכשיו ./greedy. 

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

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

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

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

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

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

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

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

אז עכשיו אנחנו רק הולכים לדרוך על פיסת קוד זה. אז בואו לראות. אה, הדפסה, "אה חי, איך הרבה שינוי הוא חייב? " לא אכפת לנו. אנחנו יודעים שעובדים, כך אנו דורכים עליו. 

אז n, שהוא לצוף ש יש לנו initialized-- או declared-- בחלק העליון, אנחנו עכשיו שווה שלGetFloat (). אז בואו לדרוך על זה. ואנו רואים ב התחתון כאן, התכנית הוא גרם לי לקלט ערך. אז בואו קלט הערך שאנחנו רוצים כדי לבדוק כאן, שהוא 0.41. גדול. 

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

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

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

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

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

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

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

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

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

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

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

והנה הסבר חזותי איך זה יעבוד. כך למשל, אם היינו מתחיל עם מערך של חמישה אלמנטים, מדד 0 עד 4, עם 3, 5, 2, 6, ו -4 ערכים ממוקם בarray-- כך עכשיו, אנחנו רק הולכים להניח שהם כולם לא ממוינים בגלל שלא בדקנו אחר. 

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

אז אחרי מעבר אחד, אנחנו אכן רואים כי 2 ו 3 הם החליפו. ואנחנו רק הולכים להמשיך לעשות זה שוב עם שאר המערך. אז אנחנו הולכים רק כדי לרוץ דרך ארבעת המדדים האחרונים של המערך. אנחנו תראו את זה 3 הוא הערך המינימאלי הבא. אז אנחנו הולכים להחליף את זה עם 4. ואז אנחנו פשוט הולכים לשמור פועל באמצעות עד, סופו של דבר, אתה להגיע למערך ממוין שבי 2, 3, 4, 5, ו -6 כולם מסודרים. האם כולם מבינים את ההיגיון איך מיון בחירה עובד? 

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

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

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

קהל: אתה רוצה ליצור כמה סוג של [לא ברור] שאתה פועל באמצעות המערך השלם שלך. 

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

קהל: בדוק אותם כל לקטן ביותר. 

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

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

קהל: הו, משתנה נוסף? ANDI פנג: כנראה נוסף ללולאה, נכון? אז אנחנו כנראה הולכים רוצים ללחזר through-- גדול. ואז אתה הולך לחזור ו כנראה לבדוק את המינימום שוב, נכון? ואתה הולך לשמור חוזר זה, כי הלולאות רק הולך להמשיך לרוץ, נכון? 

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

קהל: ללולאה. 

ANDI פנג: ללולאה? בדיוק. אז זה כנראה הולך להיות ללולאה. מה היא בדיקה כאן הולכת לרמוז? בדרך כלל, אם אתה רוצה לבדוק אם משהו הוא משהו else-- 

קהל: אם. 

ANDI פנג: אם, נכון? ולאחר מכן ההחלפה כאן, אנחנו לעבור על כך, כי דוד עבר כי בהרצאה גם כן. ואז לחזר השני implies-- 

קהל: נוסף ללולאה. 

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

או הו. למה זה not-- שם זה. אוקיי. מצטער, תן לי לנסות להתקרב קצת יותר. הנה. כל מה שאני עושה כאן הוא יצרתי תכנית בשם "בחירה / sort.c." יצרתי מערך של תשע ערכים, 4, 8, 2, 1, 6, 9, 7, 5, 3. נכון לעכשיו, כפי שאתה יכול רואה, הם לא מסודרות. n הולך להיות המספר ש אומר לך את הסכום של ערכים יש לך במערך שלך. במקרה זה, יש לנו תשעה ערכים. ואני פשוט חייבת ללולאה כאן שמדפיס את המערך לא ממוינים. 

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

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

קהל: [לא ברור] 

ANDI פנג: כן, מרגיש מצטער צריכה-- חופשי, לא צריך לעמוד תחושת up-- חופשי להרים את הקול שלך קצת. 

קהל: לשווה אני int 0-- 

ANDI פנג: כן, טוב. 

קהל: הוא אני פחות מאורך מערך. 

ANDI פנג: אז לשמור ב אכפת כאן, כי אנחנו אין לי פונקציה ש אומר לנו את אורכו של מערך, כבר יש לנו ערך שחנויות ש. נכון? דבר נוסף שכדאי בmind-- במערך תשעה ערכים, מה הם המדדים? בואו נגיד מערך זה היה 0-3. אתה רואה שעברת מדד הוא למעשה 3. זה לא 4, למרות שיש ארבעה ערכים במערך. 

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

קהל: האם לא יהיה זה n מינוס 1? ANDI פנג: זה הולך n מינוס 1, בדיוק. האם זה הגיוני, למה זה n מינוס 1, כולם? זה בגלל שמערכים הם אפס צמוד. הם מתחילים ב 0 ולהפעיל עד n מינוס 1. כן, זה קצת מסובך. אוקיי. ואז-- קהל: Isnt'1 ש כבר טפל באף, רק על ידי לא אומר "פחות או שווה "ורק אומר" פחות מ? " 

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

תקין. אולי שם טוב יותר של היה להיות-- "זמני" works-- לחלוטין אולי בשם יותר בצדק יהיה, אם אנחנו רוצים value-- הקטן ביותר 

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

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

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

אז עכשיו אנחנו רוצים להוסיף ללולאה כאן זה הולך לחזר דרך לא ממוינת, או שאר מערך זה. האם מישהו רוצה לתת לי שורת קוד שהייתי עושה את זה? Hint-- מה שאנחנו צריכים לעשות כאן? מה הולך בזה ללולאה? כן. קהל: אז היינו רוצה יש מספר שלם שונה, כי אנחנו פועלים דרך שאר של המערך במקום i, אז אולי י. 

ANDI פנג: כן, j נשמע לי טוב. שווים? 

קהל: אז יהיה אני בתוספת 1, כי אתה מתחיל בערך הבא. ולאחר מכן לend-- כך שוב, j הוא פחות מ n מינוס 1, ולאחר מכן j ++. ANDI פנג: נהדר. 

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

קהל: אם הצהרה. 

ANDI פנג: אם הצהרה. אז if-- ומה הולך להיות המצב שאנחנו רוצים בתוך אם ההצהרה שלנו? 

קהל: אם הערך של j הוא פחות מהערך של אני- 

ANDI פנג: בדיוק. אז if-- כך מערך זה נקרא "מערך". גדול. אז אם array-- מה זה היה? תגיד את זה שוב. 

קהל: אם המערך-J הוא פחות מ מערך-i, אז היינו לשנות את דקות. אז דקות תהיה j. 

ANDI פנג: האם זה הגיוני? אוקיי. ועכשיו כאן למטה, אנחנו בעצם רוצה ליישם את ההחלפה, נכון? אז זוכר, בהרצאה, שדוד, כאשר הוא מנסה להחליף כל-- מה היה מיץ תפוזים it-- וmilk-- 

קהל: זה היה ברוטו. 

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

קהל: משתנה זמני. 

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

קהל: זה יכול להיות מערך-i. 

ANDI פנג: כן, בוא לעשות מערך-i. ואז מה השורה הבאה של קוד אנחנו רוצים להיות כאן? קהל: מערך-i שווה מערך-J. ANDI פנג: ולבסוף? קהל: מערך-j שווה מערך-i. שווה או המערך-י: קהל מערך-temp-- או, זמני. 

ANDI פנג: אישור. אז בואו נריץ את זה ותראה את אם זה הולך לעבוד. איפה זה קורה? אה, זו בעיה. ראה, בקו 40, שאנחנו מנסה להשתמש במערך-J? אבל איפה j קיים רק ב? 

קהל: ללולאה. ANDI פנג: ימין. אז מה אנחנו הולכים צריכים לעשות? 

קהל: הגדר אותו מחוץ כל-- קהל: כן, אני מניח שיש לך להשתמש אחר אם הצהרה, נכון? אז כמו, אם minimum-- בסדר, תן לי לחשוב. 

ANDI פנג: חבר'ה, לנסות לקחת בואו תסתכלו ראו, מה משהו שאנחנו יכולים לעשות כאן? 

קהל: אישור. אז אם המינימום לא שווה j-- כך שאם המינימום הוא עדיין אני- אז אנחנו לא נצטרך להחליף. 

ANDI פנג: האם זה שווה לי? מה אתה רוצה לומר כאן? 

קהל: או כן, אם המינימום עושה אני לא שווה, כן. ANDI פנג: אישור. ובכן זה פותר, סוג של, הבעיות שלנו. אבל זה עדיין לא פותר בעיה של מה קורה אם j-- מאז j לא קיימת מחוצה לו, מה אתה אנחנו רוצים לעשות עם זה? להכריז עליו בחוץ? בואו ננסה לרוץ זה. או הו. הסוג שלנו לא עובד. 

כפי שניתן לראות, ראשוני שלנו היה לי מערך ערכים אלה. ואחר כך זה צריך להיות היה ב1, 2, 3, 4, 5, 6, 7, 8, 9. זה לא עובד. אהה. מה אנחנו עושים? קהל: Debug. ANDI פנג: בסדר, אנחנו יכולים לנסות את זה. אנחנו יכולים לאתר באגים. להקטין את התצוגה קצת. בואו להגדיר נקודת העצירה שלנו. בואו נלך על אישור like--. 

אז בגלל שאנחנו כבר יודעים ש שורות אלה, 15 עד 22, הם working-- כי כל מה שאני עושה הוא רק iterating דרך וprinting-- אני יכול ללכת קדימה ולדלג על זה. בואו נתחיל בקו 25. OOP, תן לי להיפטר מזה. 

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

אז הקו הזה כאן, אנו יכולים להתערב. אתה יכול לראות כאן למטה, יש לנו מערך. אלה הם הערכים שנמצאים במערך. האם אתה רואה את זה, איך מדד 0, זה מתאים לvalue-- הו, אני הולך לנסות להתקרב. מצטער, זה ממש קשה לsee-- במדד מערך 0, יש לנו ערך של 4 ו אז כן הלאה וכן הלאה. יש לנו המשתנים המקומיים שלנו. עכשיו הוא אני שווה 0, שבו אנו רוצים שזה יהיה. 

ואז בואו לשמור דריכה דרך. המינימום שלנו הוא שווה 0, שאנחנו גם רוצים שזה יהיה. ואז אנחנו נכנסים השני שלנו ל לולאה, אם המערך-J הוא פחות מהמערך-i, שזה לא היה. אז ראית איך שדלג על זה? 

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

כן, אז אנחנו באמת יכולים לצאת מהבאגים כאן. אז בואו נסתכל על פסאודו הקוד שלנו. For-- אנחנו הולכים מתחיל ב i שווה 0. אנחנו הולכים ללכת עד n מינוס 1. בואו לבדוק, היה לנו זכות ש? כן, זה היה נכון. 

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

אז עם זאת, מה אנחנו משווים כאן? 

קהל: j בתוספת 1. ANDI פנג: בדיוק. ואז אתה הולך לרוצה להגדיר המינימום שלך שווה לj בתוספת 1 גם כן. אז הלכתי דרך שממש מהר. האם אתם מבינים למה זה בתוספת י 1? אוקיי. 

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

אז בואו נגיד שיש לנו יש, כמו, 2, 5, 1, 8. נכון לעכשיו, הוא שאני שווה 0 וי הוא שווה 0. וזה הערך המינימאלי שלנו. אם המערך-J בתוספת אני- כך שאם אחד זה אחרי אחד אנחנו מסתכלים גדול מזו שלפניה, זה הולך להיות מינימאלי. 

אז הנה אנו רואים כי 5 לא פחות מזה. אז זה הולך לא להיות 5. אנו רואים כי 1 הוא פחות מ -2, נכון? אז עכשיו אנחנו יודעים שהמינימום שלנו הוא הולך להיות ערך המדד ב 0, 1, 2. כן? ואז כשאתה מקבל כאן למטה, אתה יכול להחליף את הערכים הנכונים. 

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

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

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

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

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

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

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

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

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

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

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

אוקיי. למישהו יש ניחוש מה מקרה הגרוע ביותר של זמן הריצה מיון בועות היא? כן. 

קהל: האם זה יהיה, כמו, n פעמים n מינוס 1 או משהו כזה? כמו, בכל פעם שהוא פועל, זה פשוט, כמו, החלפה אחד פחות כי כל מה שהיה. 

ANDI פנג: כן, כל כך אתה צודק לחלוטין. וזה מקרה שבך התשובה הייתה למעשה מורכבת יותר יותר מזה שאנחנו צריכים לתת. אז זה הולך run-- אני הולך למחוק את כל זה כאן. האם כולם טוב? האם אני יכול למחוק את זה? אוקיי. אתה הולך לרוץ דרך n פעמים בפעם הראשונה, נכון? והם הולכים לרוץ דרך n מינוס 1 בפעם השנייה, נכון? ואז אתה הולך לשמור הולך, n 2, וכולי. דוד עשה את זה בהרצאה, שבו, אם אתה הוסיף את כל הערכים האלה, אתה מקבל משהו שהוא like-- yeah-- מעל 2, אשר למעשה רק מפחית עד n בריבוע. אתה הולך לקבל חלק מוזר שם. וכך רק יודע ש n בריבוע תמיד גובר על כל החלק. ולכן במקרה זה, הגרוע ביותר זמן ריצה יהיה בריבוע n. אם זה היה יורד כדי, חושב, אתה צריך לעשות החלפה בכל פעם. 

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

קהל: n. ANDI פנג: זה n, בדיוק. ולמה זה n? קהל: מכיוון שאתה רק צריך לבדוק בכל פעם. ANDI פנג: בדיוק. אז בזמן הריצה הטובה ביותר האפשרית, אם רשימה זו כבר הייתה sorted-- נניח 1, 2, 3, 4-- הייתי הולך רק דרך, היית לבדוק, היית רואה, אה, כולם יסתדרו. אני לא צריך להחליף. אני סיימתי. אז במקרה כזה, זה פשוט n או את מספר הצעדים שאתה פשוט הייתי צריך לבדוק ברשימה הראשונה. 

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

כך למשל, יש לנו רשימה של 3, 5, 2, 6, 4 שוב. אנחנו יודעים שזה כרגע לא ממוינים כי יש לנו רק התחיל להסתכל על זה. אנחנו נסתכל ואנחנו יודעים ש הערך הראשון הוא מיון, נכון? אם אתה מחפש רק במערך של גודל אחד, אתה יודע שזה מסודרים. 

אז אנחנו יודעים ש ארבעה אחרים הם לא ממוינים. אנחנו עוברים ואנחנו רואים ערך ש. בוא נחזור. ראה ערך זה של 5? אנחנו נסתכל על זה. אנו משווים אותו ל -3. אנחנו יודעים שזה גדול יותר מ 3, כך שאנחנו יודעים שזה מסודרים. אז עכשיו אנחנו יודעים ששני הראשונים מסודרים והשלוש האחרונים הם לא. 

אנחנו נסתכל על 2. אנחנו הראשונים לבדוק את זה עם 5. האם זה פחות מ 5? זה לא. אז אנחנו צריכים לשמור מסתכלים למטה. אז לך לבדוק את 2 3. האם זה פחות מ? מס ' אז אתה יודע 2 יש להיות מוכנס לחזית ו 3 ו -5 לשניהם יש להידחף החוצה. לעשות את זה שוב עם 6 ו -4. ואנחנו רק לשמור על בדיקה במהות, שבו אנחנו פשוט לבדוק, לבדוק, לבדוק. ועד שהוא בימין עמדה, אנחנו סוג של רק הכנס אותו למיקום הנכון, המקום שבו שמו של זה בא. 

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

אישור האם מישהו רוצה תן לי את זמן הריצה הגרועה ביותר? כן. 

קהל: n בריבוע. 

ANDI פנג: זה n בריבוע. ולמה זה n בריבוע? 

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

קהל: n מינוס 1, כי ראשון כבר בריבוע. 

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

אז במקרה הטוב, זה בעצם רק הולך להיות n. אם יש לך 1, 2, 3, 4, 5, 6, 7, 8, אתה הולך לרוץ דרך שכל רשימה אחת כדי לבדוק אם הכול בסדר. האם כולם ברור בריצה כמו גם זמנים של בחירה? אני יודע שאני עובר אלה מהירים באמת. אבל רק יודע שאם אתה יודע מושגים כלליים, אתה צריך להיות טוב. אוקיי. אז רק אני אתן לכם אולי, כמו, דקות לדבר עם השכנים שלך על מה בדיוק כמה ההבדלים העיקריים בין סוגים אלה של מיני. אנחנו נלך על זה בקרוב. קהל: אה, בסדר. ANDI פנג: כן. אוקיי. מגניב, בואו לכנס כתובענה. אוקיי. אז זה היה סוג של שאלה פתוחה במובן כי יש המון תשובות להם. ונלך על כמה מהם בקצרה. רק רציתי להביא לך חבר ' לחשוב על מה שהבדיל כל שלושת הסוגים של מיני. ושמעתי, גם, גדול question-- מה להתמזג לעשות סוג? שאלה גדולה, כי זה מה שאנחנו מכסים הבאים. 

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

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

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

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

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

נניח שיש לנו מערך, שש אלמנטים, 3, 5, 2, 6, 4, 1, לא מסודרים. בסדר, יש הרבה בדף זה. אז אם אתם יכולים להסתכל ב צעד הראשון כאן, 3, 5, 2, 6, 4, 1, אתה יכול לפצל אותו לשתיים. יש לך 3, 5, 2, 6, 4, 1. אתה יודע כי אלה aren't-- לא יודע אם הם מסודרים או לא, כך אוכל לשמור פירוקם, במחצית, במחצית, במחצית, עד סופו של דבר, יש לך רק אלמנט אחד. ואלמנט אחד הוא תמיד מסודרים, נכון? 

אז אנחנו יודעים ש3, 5, 2, 4, 6, 1, על ידי עצמם, מסודרים. ועכשיו אנחנו יכולים להחזיר אותם יחד. אז אנחנו יודעים 3, 5. אנחנו להרכיב אותם. אנחנו יודעים שזה ממוין. 2 של עדיין שם. אנחנו יכולים לשים את 4 ואת 6 ביחד. אנחנו יודעים שזה מסודרים, ולכן אנחנו להרכיב ש. ו1 הוא שם. 

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

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

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

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

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

קהל: אז אתה פשוט תמיד השוואה [לא ברור]? 

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

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

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

קהל: האם n יומן המקרה n הגרוע ביותר? ANDI פנג: בדיוק. ולמה זה n להיכנס n. 

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

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

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

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

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

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

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

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

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

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

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

אז אני מניח ביקשתי ממך לכתוב חיפוש פונקציה שנקרא () שחזרה ערך, ערך בוליאני, זה היה נכון או false-- כמו, נכון אם מצא ערך, שקר אם לא. ואז אתה היה עבר בשוויך חיפשנו לערכים, ש הוא array-- הו, אני בהחלט לשים שבמקום הלא נכון. אוקיי. בכל מקרה, שיהיה לי היה בצד הימין של ערכים. ואז int n הוא המספר אלמנטים במערך ש. איך היית הולך על ניסיון לפסאודו קוד בעיה שב? אני אתן לך בחורים כמו שלוש דקות לעשות את זה. לא, אני חושב שיש only-- כן, יש אחד ממש עד כאן. קהל: האם אני יכול? ANDI פנג: כן, יש לי אותך. האם זה עובד? בסדר מגניב. 

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

קהל: [לא ברור] קהל: היית רוצה ללחזר through-- קהל: רק עוד ללולאה? קהל: --for. 

ANDI פנג: אז זה אחד זה קצת מסובך. חושב שאתה רוצה על-- להמשיך לרוץ לולאה זה שוב ושוב עד מתי? 

קהל: עד [לא ברור] הערך שווה לערך זה. ANDI פנג: בדיוק. אז אתה יכול בעצם רק write-- אנחנו אפילו יכולים לפשט את זה יותר. אנחנו רק יכולים לעשות לולאה בזמן, נכון? אז אתה יכול רק צריך loop-- אנחנו יודעים שזה זמן. אבל לעכשיו, אני הולך לומר "לולאה" - דרך מה? לולאת until-- מה היא מצב הסיום שלנו? אני חושב ששמעתי אותו. שמעתי מישהו אומר את זה. 

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

ANDI פנג: מה אם זה לא שם? מה אם הערך שאתה מחפש להוא לא ממש במערך הזה? קהל: אתה חוזר 1. 

ANDI פנג: אבל מה שאנחנו רוצים לולאה עד אם יש לנו מצב? כן. 

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

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

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

קהל: כן. 

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

ולאחר מכן, החברה ש שמצאנו our-- כן. 

קהל: רק question-- מהיר כשאתה אומר דקות ומקסימום, אנחנו מניחים ש זה כבר מסודרים? 

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

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

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

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

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

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

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

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

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

קהל: המתן. יש לי שאלה. 

ANDI פנג: כן. 

קהל: אז התחלתי לעשות החיפוש ליניארי בhelpers.c וזה לא היה באמת עובד. אבל אז מאוחר יותר, התברר לי שאנחנו פשוט צריך למחוק אותו ולעשות חיפוש בינארי. אז זה משנה אם זה לא עובד? 

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

וגם, הרבה ילדים היו מנסה לקמפל helpers.c. אתה לא רשאי למעשה כדי לעשות את זה, כי helpers.c אין פונקציה העיקרית. ואז אתה רק צריך להיות בעצם קומפילציה ליצור ולמצוא, כי למצוא שיחות helpers.c והפונקציות בתוכו. אז זה עושה את הניפוי קוץ בתחת. אבל זה מה שאנחנו צריכים לעשות. קהל: אתה פשוט להפוך את הכל, נכון? ANDI פנג: אתה יכול פשוט לעשות את כל וכן, כן. אוקיי. אז זהו זה במונחים של מה ש pset מבקש כל מה שאתה צריך לעשות. אם יש לך שאלות, מרגיש חופשי לשאול אותי אחרי הסעיף. אני אהיה כאן ל, כמו, 20 דקות. 

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

קהל: עם תוספת פונקציות, אנחנו נראים האלה? 

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