1 SPEAKER: היי לכולם! ברוכים השבים לסעיף. כל כך שמח לראות כל כך הרבה מכם גם כאן, וכל מי שצופה באינטרנט. אז, כמו גב בברכה רגיל. אני מקווה שכל מה שהיית יפה בסוף השבוע, מלא של מנוחה, הרפיה. זה היה יפה אתמול. אז, אני מקווה שנהנה בחוץ. אז קודם כל כמה הודעות. לדירוג. אז, רוב אתה צריך קיבל דוא"ל ממני על Pset Scratch שלך, כמו גם לדירוג ל1 Pset. אז, רק כמה דברים. הקפד להשתמש check50 בstyle50. אלה אמורים להיות משאבים בשבילכם, כדי לוודא שאתה מקבל נקודות רבות ככל שאתה יכול ללא צורך לאבד אותם. אז, דברים כמו סגנון חשובים מאוד. אנחנו הולכים לקחת את זה ל. חלק מכם אולי כבר שם לב שמPset שלך. וcheck50 הוא רק באמת דרך קלה לוודא כי אנחנו בעצם חוזרים מה צריך להיות מוחזרות למשתמש, וכל מה שהוא פועל כראוי. על הפתק השני, לוודא שלך העלאת דברים לתיקייה הנכונה. זה עושה את החיים שלי רק קצת יותר קשה אם אתה מעלה Pset 2 לתוך 1 Pset כי כשאני מוריד דברים, הם לא להוריד בצורה נכונה. ואני יודע שזה קצת רופף במערכת להתרגל ל, אבל רק להיות סופר זהיר, אם רק בשבילי, כך שכאשר אתה מקבל מיילים בכ02:00 ואני לדירוג. אם לא יגרום לי להיראות בכל רחבי לPset שלך. מגניב. אני יודע שזה מוקדם, אבל אני לגמרי יש המריא שומר על ידי חיבור זה עקב ביום שישי הקרוב, ש המרצים שלי פשוט היו כמו, אה, כן. זכרו, יש לך מאמר עקב ביום שישי. אז, אני יודע שאף אחד לא אוהב לחשוב על מבחני אמצע סמסטר, אבל החידון הראשון שלך הוא ב -15 באוקטובר, שאוקטובר הוא החל מהשבוע. אז, זה יכול להיות מוקדם ממה שציפית הוא כל. כך שאתה לא נזרק משומר כש אני מזכיר סעיף בשבוע הבא כי הו, בשבוע הבא החידון שלך, חשבתי ש אני הייתי נותן לך קצת יותר של ראשים עד עכשיו. אז, להגדיר את הבעיה שלך, מספר שלוש. איך אנשים שקראו spec מתוך סקרנות? אישור. יש לנו כמה. סוג של למטה מ אחרון שבוע אבל זה בסדר. אני יודע שהוא היה יפה. אז תפרוץ. בהחלט לאחר להספיק היום לקרוא את האפיון שלך לפחות תנסה כמו הורדה קוד הפצה וריצה כמו האות הראשונה דבר שהם מבקשים ממך. מכיוון שאנו משתמשים ב קוד הפצה וספרייה שרק עכשיו using-- --It רק בפעם השנייה שעשינו Pset זה, דברים מטורפים יכולים לקרות עם המכשיר שלך, ואתה רוצה למצוא ש עכשיו לעומת מאוחר יותר. כי אם זה יום חמישי בערב או שזה יום רביעי בלילה, ומסיבה כלשהי המכשיר שלך עושה בדיוק את לא רוצה לרוץ עם הספרייה או עם ההפצה קוד, שאמצעי אתה אפילו לא יכול להתחיל לעשות את הקידוד. בגלל שאתה לא יכול לבדוק כדי לראות אם זה עובד. לא הולך שלך תוכל כדי לראות אם זה הידור. אתה רוצה לטפל באלה בשלב מוקדם ב השבוע, כשאתה עדיין יכול לשלוח לי דוא"ל או אחד מTFS האחר, ואנחנו יכולים לקבל אותם קבועים. כי אלה הם נושאים כי הם הולכים לעצור אותך מלעשות כל התקדמות של ממש. זה לא כמו באג אחד, ש אתה יכול פשוט סוג של לדלג על. אם אתה נתקלת בבעיות עם שלך מכשיר או קוד הפצה, אתה באמת רוצה לקבל את זה לקח אכפת לי של במוקדם ולא במאוחר. אז גם אם אתה לא הולך ממש להתחיל לקודד, להוריד את ההפצה קוד, לקרוא את המפרט, לוודא כל מה שעובד שם. בסדר? אם אתה יכול פשוט לעשות את זה, אני מבטיח חייכם יהיו קל יותר. ואז אתה כנראה הולך לעשות את זה עכשיו נכון? אישור. אז, כל שאלות שם? כל דברים לוגיסטיים? כולם טובים? אישור. כתב ויתור לאלה של אתה בחדר והאינטרנט. אני הולך להיות מנסה לעבור בין PowerPoint במכשיר כי אנחנו הולכים להיות עושה קצת קידוד היום לפי דרישת קהל של אנונימי סקר הצעה שנשלח שבוע שעבר. אז, יהיה לנו לעשות כמה קידוד. אז, אם אתם רוצים גם לפטר את המכשירים שלכם, ואתה צריך יש לי דואר אלקטרוני ממני, עם קובץ לדוגמה. אתם מוזמנים לעשות את זה. אז, אנחנו הולכים לדבר על GDB, אשר הוא הבאגים. זה הולך לעזור לך סוג של להבין איפה דברים הולכים בסדר בקוד שלך. זה באמת רק דרך בשבילך כדי להגביר דרך הקוד שלך כפי שהוא קורה, ולהיות מסוגל להדפיס את המשתנים או לראות מה באמת קורה מתחת למכסת מנוע פסוקי התכנית שלך פשוט רצתי, זה כמו בהעתקים גיאולוגיים, ואתם כמו, אין לו מושג מה בדיוק קרה כאן. אני לא יודע מה קו שהוא נכשל ב. אני לא יודע איפה זה השתבש. אז, GDB הוא הולך לעזור לך עם זה. כמו כן, אם אתה מחליט להמשיך כן, ולקחת את 61, זה באמת, באמת להיות שלך החבר הכי טוב, כי אני יכול להגיד לך בגלל שאני עובר כיתה ש. אנחנו הולכים להסתכל על ינארי חיפוש, שאם אתם זוכרים ספר טלפונים לדוגמא נהדרת מחזה מכיתה. אנחנו נהיה יישום ש, ו הליכה דרך שקצת יותר, ולאחר מכן אנחנו עוברים ארבעה מיני שונים, שהם בועה, בחירה, החדרה, ומיזוג. מגניב. אז, GDB כפי שציינתי, הוא הבאגים. ואלה הם סוג של גדול דברים, פונקציות או פקודות הגדולות כי אתה משתמש בGDB, ואני אלך שלך דרך הדגמה שלה ברגע אחד. אז, זה לא רק הולך להישאר מופשט. אני אנסה לעשות את זה כמו בטון ככל האפשר עבורכם. אז, לשבור. או שזה יהיה הפסקה כמו, חלק מספר, ש מייצג קו בתכנית שלך, או שאתה יכול לנקוב בשם פונקציה. אז, אם אתה אומר לשבור עיקרי, הוא יפסיק בעיקרי, ולתת לך ללכת דרך פונקציה ש. כמו כן, אם יש לך כמה חיצוני לתפקד כמו החלפה או קובייה, שהסתכלנו בשבוע שעבר. אם אתה אומר לשבור אחד מאותם, בכל פעם שהתכנית שלך פוגעת ש, זה יחכו לך ל תגיד לו מה לעשות. לפני זה פשוט יבצע, כך ש באמת יכול לשלב בתוך הפונקציה ותראה מה קורה. אז, בשלב הבא, רק מדלג על השורה הבאה, הולכת על פונקציות. צעד. כל אלה הם מופשטים הקטנים. אז, אני פשוט הולך לרוץ דרכם, אבל אתה תראה אותם בשימוש בשני. צעד לתוך פונקציה. אז כפי שאמרתי, כמו עם החלפה, זה היה מאפשר לך בעצם כאילו אתה כמו כניסה פיזית בתוך, אתה יכול להתעסק עם משתנים אלו, הדפסה מתוך מה שהם, לראות מה קורה. רשימה תהיה ממש פשוט להדפיס את הקוד שמסביב. אז, אם אתה סוג של לשכוח שבו אתה נמצא בתכנית שלך, או שאתה תוהה מה קורה סביבו, זה יהיה פשוט להדפיס את קטע של אוהב חמישה או שישה קווים סביבו. אז, אתה יכול להתאפס על איפה אתה נמצא. להדפיס כמה משתנים. אז, אם יש לך מפתח כמו בקיסר, שאנחנו מסתכלים. אתה יכול להגיד מפתח הדפסה בכל נקודה. זה יגיד לך מה הוא הערך כל כך כי, אולי איפשהו בדרך, אתה החלפת את המפתח שלך. אתה באמת יכול להגיד את זה כי למעשה ניתן לראות כי ערך. בהמקומיים, רק הדפסים את המשתנים המקומיים שלך. אז, בכל עת שאתה בתוך לולאה, ואתה רק רוצה לראות כמו, אה. מה אני שלי? מהו ערך מפתח זה כי אני לאתחל כאן? מהו המסר בשלב זה? זה יהיה פשוט להדפיס את כל של אלה, כך שאתה לא צריך בנפרד אומר, מסר הדפסת I. הדפסה. מפתח הדפסה. ולאחר מכן להציג. מה שעושה זה כמו שאתה המשך בתכנית, זה פשוט לוודא שזה בו מוצגות כמה משתנים מסוימים בכל נקודה. כך שאתה also-- --it זה סוג של קיצור דרך שבי אתה לא צריך להמשיך ככה, אה. מפתח הדפס או I. הדפסה זה פשוט באופן אוטומטי לעשות את זה בשבילך. אז, עם זה, אנחנו הולכים כדי לראות איך זה הולך. אני הולך לנסות ומתג מעל למכשיר שלי. לראות אם אני יכול לעשות את זה. כל. אנחנו רק לשקף אותו. אין שום דבר מטורף על המחשב הנייד שלי בכל מקרה. אישור. זה צריך להיות זה אחד. זה כל כך זעיר. בואו תראו אם אנחנו יכולים לעשות את זה. אישור. אליס היא ללא ספק נאבקת כאן רק קצת, אבל בואו נעשינו את זה במזכרת. אישור. אנחנו רק הולכים להגדיל את זה. אישור. יכול כולם סוג של רואה את זה? אולי קצת? אני יודע שזה קצת קטן. אתה לא ממש יכול להבין איך לעשות את זה גדול יותר. אם מישהו יודע. האם מישהו יודע איך לעשות את זה גדול יותר? אישור. אנחנו הולכים לזרום עם זה. לא משנה בכל מקרה, כי זה פשוט זה הקוד שאתם צריכים יש לי. מה שחשוב יותר הוא המסוף כאן. ויש לנו כאן למה זה כל כך קטן? הגדרות. אה. אייק האמיתי. מה קורה כאן? משם. האם זה טוב יותר לכולם? אישור ,. מגניב. אתה יודע כשאתה בCS קשיים טכניים ברמה הם סוג של חלק מthe-- אז, בואו לנקות את זה. אישור. אז, ממש כאן בסעיף, שהיו לנו כאן. קיסר הוא קובץ הפעלה. אז עשיתי את זה. אז, דבר אחד להבין עם GDB הוא כי זה עובד רק בקבצי הפעלה. אז, אתה לא יכול להפעיל אותו בdotsy. אתה חייב לעשות את בעצם בטוח שהקוד שלך הידור, ושזה באמת יכול להיות מנוהל. לכן, ודא שאם זה לא לקמפל, לקבל את זה כדי לקמפל, כך שסוג של אתה יכול לרוץ דרכו. לכן, כדי להתחיל GDB, כל מה שאתה עושה, סוג GDB גלוריה, ואז פשוט קובץ שברצון. אני תמיד באיות קיסר. אבל אתה רוצה לוודא מכיוון שזה הפעלה, הבזק הנקודה של TI, כך ש אומר שאתה הולך לרוץ CSI אתה הולך לבצע זה קבצים או עם הבאגים. אישור. אז, אתה עושה את זה, אתה מקבל סוג זה של ג'יבריש. זה פשוט כל הדברים על הבאגים. אתה לא באמת צריך תדאג בקשר לזה עכשיו. וכמו שאתה רואה, יש לנו את זה parens הפתוח, תוצר מקומי גולמי, קרוב parens, ורק נראה כמו סוג של שורת הפקודה שלנו, נכון? אז, מה שאנחנו רוצים do-- --So, הדבר הראשון הוא שאנחנו רוצים לבחור מקום לשבור אותו. אז, יש באג אחד בתכנית קיסר זה שאני מציג, ש אנחנו הולכים לברר. זה מה שהיא עושה זה לוקח את הקלט Barfoo בכל כמוסות, ומשום מה זה לא משנה א 'זה פשוט משאיר את זה לבד, האם כל דבר אחר נכון, אבל המכתב השני נותר ללא שינוי. אז, אנחנו הולכים לנסות ו להבין למה זה. לכן, הדבר הראשון שאתה בדרך כלל רוצה לעשות בכל פעם שאתה מתחיל בGDB הוא להבין איפה לשבור אותו. אז הקיסר הוא תכנית די קצרה. רק יש לנו תפקיד אחד, נכון? מה היה התפקיד שלנו בקיסר? יש רק פונקציה אחת, נכון ראשי? העיקרי היא פונקציה לכל התוכניות שלך. אם לא היה לך ראשי, אולי אני להיות קצת מודאג עכשיו, אבל אני מקווה שכולכם היה ראשי לשם. אז, מה אנחנו יכולים לעשות הוא שאנחנו יכולים פשוט לשבור ראשי, סתם ככה. אז, זה אומר, בסדר. אנו קובעים נקודת העצירה אחת שלנו יש. אז, עכשיו מה שצריך לזכור הוא קיסר לוקח נכון טענת שורת פקודה אחת ואנחנו לא עשינו את זה בכל מקום עדיין. אז, מה שאתה עושה הוא כאשר אתה בעצם ללכת לרוץ התכנית, כל תכנית שאתה פועל בGDB שצריך שורת הפקודה טיעונים, אתה הולך קלט כאשר אתה ראשון להתחיל להריץ אותה. אז, במקרה זה, אנחנו עושים לרוץ עם מפתח של שלוש. וזה באמת יתחיל. לכן, אם אתם רואים כאן, יש לנו אם RC הוא לא שווה ל 2. אז אם אתם כל מה שיש קובץ ששלחתי אותו אתה תראה שזה כמו השורה הראשונה הפונקציה העיקרית שלנו, נכון? זה בודק אם יש לנו את המספר הנכון של טיעונים. אז, אם אתה תוהה אם RC הוא נכון, אתה יכול לעשות משהו פשוט כמו RC הדפסה. RC הוא שני, שהוא מה צפוי לנו, נכון? אז, אנחנו יכולים ללכת הבא, וממשיך דרך. אז, יש לנו כמה מפתח יש. ואנחנו יכולים להדפיס את המפתח שלנו כדי לוודא שזה נכון. מעניין. לא בדיוק מה שציפינו. אז, דבר אחד הוא מבין עם GDB גם, הוא שזה לא עד שאתה בעצם פגע הבא, כי הקו שאתה פשוט ראית מבוצע בפועל. לכן, במקרה זה מפתח לא הוקצה עדיין. אז, מפתח הוא כמה ערך זבל שאתה רואה בחלק התחתון יש. שלילי 120-- $ --It מיליארדים של אחד ודברים מוזרים משהו נכון? זה לא המפתח שציפינו. אבל אם פגע הבא, ולאחר מכן אנו לנסות ומפתח הדפסה, זה שלושה. כולם רואים את זה? אז, אם אתה מקבל משהו שאתה אוהב את, לחכות. זה לגמרי לא נכון, ואני לא יודע איך זה יקרה בגלל כל מה שאני רוצה לעשות הוא להקצות מספר, משתנה, לנסות להכות הבא, נסה להדפיס זה שוב, ולראות אם זה עובד. כי זה רק הולך לבצע ו למעשה להקצות משהו אחריך הלהיט הבא. הגיוני לכולם? אה הא? SPEAKER 2: כאשר אתה אקראי מספרים מה זה אומר? 1 דובר: זה פשוט אקראי. זה פשוט זבל. זה פשוט משהו ש מחשב באופן אקראי להקצות. מגניב. אז, עכשיו אנחנו יכולים לעבור, וכך עכשיו יש לנו GetString טקסט רגיל זה. אז, תן לי רק להציג את מה ש יקרה כאשר פגעו הבא כאן. GDB שלנו סוג של נעלם, נכון? זה בגלל GetString עכשיו מבצע, נכון? אז, כשראינו טקסט רגיל שווה GetString, parens וparens פתוחים, ואנחנו להיט הבאים, שיש למעשה להורג עכשיו. אז, זה מחכה לי לנו קלט משהו. אז, אנחנו הולכים קלט המזון שלנו ש זה מה שזה לא הצליח כמו שאמרתי לך וכי רק אומר שזה סיימתי ביצוע, שנסגר הסוגר אומר שזה יציאה החוצה של לולאה ש. לכן, אנו יכולים להיט בא, ועכשיו, כמו שאני בטוח שאת מכירה מקיסר, זה, מה זה קו הולך לעשות. זה לInt אני שווה 0, N שווה Strlen, טקסט רגיל, ולאחר מכן אני הוא פחות מ n, אני, בתוספת, בתוספת. מה היא לולאה זה הולך לעשות? פתח את ההודעה שלך. מגניב. אז, בואו נתחיל לעשות את זה. אז, צריך את המצב הזה להתאים, לראשון שלנו? אם זה B, זה אנחנו I. טקסט רגיל ניתן לקבל מידע על המקומיים שלנו. אז, אני הוא אפס, ואם שש, ש אנו מצפים, והמפתח שלנו הוא שלוש. כל זה הגיוני, נכון? המספרים האלה הם כל בדיוק מה שהם צריכים להיות. אז, זמזם? SPEAKER 3: יש לי מספרים אקראיים למכרה. SPEAKER 1: ובכן, אנחנו יכולים check-- --we יכול לשוחח על זה בשנייה. אבל אתה צריך להיות מקבל את זה. אז, אם יש לנו הון B לראשון שלנו, מצב זה צריך לתפוס אותו, נכון? אז, אם פגעו הבא, אנו רואים כי אם זה מבצע למעשה. כי אם אתה הבא לאורך בקוד שלך, הקו הזה כאן, שבו אני טקסט רגיל מוחלף בחשבון זה, רק מבצע אם אם מצב נכון נכונה? GDB הוא רק הולך להראות לך דברים שמבצעים בפועל. אז אם מצב אם זה לא הושג, זה רק הולך לדלג לשורה הבאה. בסדר? אז, יש לנו את זה. הסוגר זה אומר שזה סגור מחוץ ללולאה שעכשיו. אז, זה הולך להתחיל שוב. פשוט ככה. אז, שאנחנו יכולים לקבל מידע על המקומיים שלנו כאן, ואנחנו רואים ש הראשונים המכתב השתנה, נכון? עכשיו זה E, כפי שהוא אמור להיות. אז, אנחנו יכולים להמשיך הלאה. ויש לנו סימון זו. ובדיקה זו צריכה לעבוד, נכון? זה א צריך להיות שונה זה שלוש אותיות קדימה. אבל אם תשימו לב, אנחנו לקבל משהו שונה. אז במקרה כאן זה, זה תפס זה, וכן את הקו הזה להורג, ששונה ב 'שלנו אבל, במקרה הזה כאן, יש לנו שזה פשוט לדלג עליה, והלכתי ל[? siff L. ?] אז משהו קורה שם. מה זה אומר לך הוא ש, אנחנו יודעים שהוא היה אמור לתפוס כאן, אבל זה לא. כל אחד יכול לראות מה שלנו בעיה היא בקו זה? זה דבר מאוד דקות. ואתה יכול גם להסתכל על הקוד שלך. זה גם line-- לשכוח את מה קו זה בthere-- אבל זה ב[ לא ברור]. כן? 4 רמקול: זה על יותר מ דף אם אתה קורא את זה בספר. 1 SPEAKER: בדיוק. אז, הבאגים לא יכולים להגיד לי שלך ש, אבל הבאגים יכול לקבל אותך לקו כי אתה יודע שהוא לא מתפקד. ולפעמים, כאשר במיוחד מאוחר יותר בסמסטר, כאשר עם מאה, יש לך עסק מאה כמה שורות קוד, ואתה לא יודע איפה זה כושל, זו היא דרך מצוינת לעשות את זה. אז, מצאנו באג שלנו. אתה יכול לתקן את זה בקובץ שלך, ואז אתה יכול להפעיל אותו שוב, וכל מה שהיה עובדים בצורה מושלמת. וזה הדבר הגדול ביותר זה יכול להיראות כמו, אישור. כן. מגניב. אתה יודע מה שאתה מחפש. אז, אתה יודע מה לעשות. GDB יכול להיות סופר מועיל, כי אתה ניתן להדפיס את כל הדברים האלה שאתה לא היית. זה הרבה יותר מועיל מאשר printf. כמה מכם משתמש ב כמו דוחות printf להבין איפה הבאג היה, נכון? אז, עם זה, אתה לא צריך לשמור חוזר, ורוצה להעיר ב Printf, או להעיר את, ולהבין מה אתה צריך להיות בהדפסה. זה בעצם רק מאפשר לך צעד דרך, להדפיס את הדברים כמו שאתה הולך דרך, כל כך, שאתה יכול לבחון כיצד הם משתנים בזמן אמת, כתכנית שלך פועל. וזה ייקח קצת קצת הזמן להתרגל אליו. אני מאוד ממליץ פשוט סוג להיות קצת מתוסכל עם זה לעכשיו. אם אתם מבלים שעות על בשבוע הבא לומד כיצד להשתמש GDB, תוכל לחסוך לעצמך כל כך הרבה זמן מאוחר יותר. ופשוטו כמשמעו. אנחנו אומרים לי לאנשים בכל שנה זה, ואני זוכר שלקחתי את כיתה, הייתי כמו, אני יהיה בסדר. מס ' Pset 6 נכנס ואני היה כאילו, אני הולך ללמוד כיצד להשתמש GDB כי אני לא יודע מה קורה כאן. אז אם אתה לוקח את הזמן כל כך להשתמש בו בתוכניות קטנות יותר שאתה הולך להיות עובד על, כמו לעבוד דרך משהו כמו Visionare, כמו זה. או אם אתה רוצה תרגול נוסף, אני בטוח ש אני יכול לבוא עם תוכניות מרכבה, לך לאתר באגים, אם תרצה. אבל אם אתה פשוט לקחת קצת זמן כדי לקבל מתרגל לזה, פשוט לשחק עם זה, זה באמת ישרת אותך היטב. וזה באמת אחד מ הדברים האלה שאתה פשוט צריך לנסות, ולקבל את הידיים מלוכלכות עם, לפני שאתה באמת מבין את זה. אני באמת רק הבנתי את זה פעם אחת היה דברים באגים עם זה אני, וזה הרבה יותר נחמד יש לי רעיון של איך לאתר באגים במוקדם ולא במאוחר. אישור. מגניב. אני יודע שזה כמו סוג של קורס מזורז בGDB, ואני בהחלט לעבוד על מקבל אלה להסתכל הפעם הבאה גדולה יותר. מגניב. אז, אם נחזור ל- PowerPoint שלנו. האם זה הולך לעבוד? AWH. כן. אישור. אז, אם אתה אי פעם צריך את כל שוב אלה, יש הרשימה. חיפוש בינארי כך, שכולם זוכר את המחזה הגדול של דוד קורע ספרי טלפון במחצית. אני לא ממש מקבל את ספרי טלפון יותר, כי כמו איפה אתה לקבל ספרי טלפון בימים אלה? אני באמת לא יודע. החיפוש בינארי. האם מישהו זוכר איך ינארי עבודות חיפוש? מישהו בכלל? כן? SPEAKER 5: אתה יודע מתי אתה מסתכל על איזה חצי זה יהיה ב, בהתבסס על כך, כדי להיפטר מאת החצי השני. SPEAKER 1 בדיוק. אז, חיפוש בינארי, שזה סוג של a-- --we אוהב לקרוא לזה פרד ומשול. אז, מה תוכל לעשות הוא אתה תיראה באמצע, ותראה אם ​​היא מתאימה מה שאתה מחפש. ואם זה לא, אז אתה מנסה להבין, זה הולך להיות שמאל מחצית או חצי הנכון. אז, זה יכול להיות אם אתה מחפש במשהו שלפי האלפבית, אתה רואה, הו. האם מגיע אליסון לפני M? כן. אז, אנחנו הולכים מסתכל על המחצית הראשונה. או שזה יכול להיות כמו עם מספרים. כל דבר שאתה יכול להשוות, ניתן למיין אותו. ניתן להשתמש בחיפוש בינארי ב. אז, מישהו זוכר את זה גרף או מה זה? זה מורכבות אסימפטוטי. אז, גרף זה פשוט מתאר כמה זמן זה לוקח אותך לפתרון בעיה כ אם תגדיל את מספרם של הדברים שאתה משתמש. אז, יש לנו N, שהוא הזמן ליניארי. אם N יותר משני, שהוא מעט , עדיין גדל טוב יותר סופר מהיר. ולאחר מכן יש לנו כניסה, אשר הוא מה שאנו מחשיבים חיפוש בינארי. אם אנחנו שמים לב, כבעיה שלך מקבל הרבה והרבה יותר גדול, הזמן שלוקח לך לפתור אותה לא ממש להגדיל כל כך הרבה. זה כמו להשוות כאן בהתחלה. אתה כמו, אישור. שום דבר כאן לא ממש משנה איזה מהם אנחנו משתמשים, אבל אתה מקבל למ', מיליארדים. אתה מנסה למצוא some-- --you're מנסה למצוא מחט בערימת שחת. אני חושב שאתה רוצה את הבעיה הזו. אתה רוצה את המורכבות הזאת, לא ליניארי, כי לכל מה שאתה לדעתך הולכים להיות מחפש דרך כל מחט בודדת, דבר חציר, מנסה לחפש המחט שלך. וזה לא כיף מדי לדעתי. אני אוהב מהר. אני אוהב יעיל. ותלמידים חרוצים כמו שאתה חבר'ה, יודע שאתה עובד בצורה חכמה יותר, לא דבר סוג קשה יותר, איך אתה יכול לפצות אלגוריתמים אלה. אז, אנחנו הולכים ללכת דרך רק דוגמה קטנה. אני חושב שאתם צריכים יד על חיפוש בינארי, אבל במקרה שמישהו הוא קצת מטושטש, רוצה לחזק אותו, אנחנו הולכים רק כדי ללכת באמצעות דוגמא כאן. אז, אנחנו מחפשים אם המערך מכיל שבע. אז, הדבר הראשון שאנחנו עושים הוא נראה באמצע, נכון? וגם אתה הולך להיות קידוד חיפוש בינארי רק שני. אז, זה הולך להיות כיף. אז אנחנו מסתכלים ב מערכים קטנים באמצע 3. האם 3 שווים 7? לא. זה שש. אז, האם זה פחות מ או יותר משבעה? פחות מ. כן. נחמדים עבודת בחורים. אני מרגיש שאני אוהב אני צריך יש לי ממתקים כי אני רוצה לזרוק אותו החוצה לחצרות. זה מה שאני הולך לעשות בשבוע הבא. זה ישמור אותך בחורים חדים. אז, אנחנו זורקים ש המחצית ראשונה, נכון? זה היה פחות מ. אנחנו יודעים כל מה ש שבצד שמאל הולך להיות פחות ממה ש אנחנו באמת מחפשים. אז, אין צורך ל לשים לב לזה. פשוט לשכוח אותו. אז, עכשיו אנחנו מסתכלים בצד ימין שלנו, ואנחנו מסתכל על האמצע שם, ועכשיו זה תשע. אז, 9 is-- --Everyone? גדול יותר ממה שאנחנו מחפש, נכון? אז, אנחנו הולכים לזרוק משם הכל בצד הימין. כמו ש. עכשיו, כל מה שאנחנו נשארים עם אחד. אז אנחנו בודקים, זה אחד מה אנחנו מחפשים? זה. מצאנו את מה שרצינו. אז סיימנו. Bilinear חיפוש. ואם אתה שם לב, אנחנו היו שם שבע תשומות. זה רק לקח אותנו כמו שלוש פעמים, אבל אם אתה עושה כמו מיליארדים, אתם יודעים כמה צעדים שהיית לקחת אם היו לנו ארבעה מליארד דברים? ניחושים? זה 32. 32 צעדים כדי למצוא משהו בארבעה מיליארדים מערך אלמנט בגלל כוחות של שני. אז שני הוא 32, הוא ארבעה מיליארדים. אז די מטורף איך אתה עדיין בתוך כמו מספר קטן למדי של צעדים למצוא משהו ב ארבעה מליארד אלמנטים. אז בנימה זאת, אנחנו הולך לקוד זה כך אתם בעצם יכולים סוג של לראות איך זה עובד. בסדר, אז אתם יכולים קוד. אני הולך לתת לכם לדבר קצת. להכיר את אנשים סביבך, שהוא מה שמישהו רוצה מן הסעיף אחרון. אז להכיר את האנשים סביבך. לדבר קצת. וכל מה שאני רוצה ממך בחורים עכשיו הוא רק מנסה ליצור קווי המתאר של פסאודו קוד. בסדר? וואו. כל מה שאני רוצה מכם הוא שאתה רק הולך למלא במקרה בזמן זה. אז אני צריך להגדיר עליון אלה וחסמים התחתונים ש מייצג את תחילת וסוף המערך שלנו. ואתה הולך בעצם לולאה דרך ולהבין מה שאנחנו עושים בתוך לולאת ה while זה. אז אם אתה יכול להבין out-- יש לי רמז there-- מה הם המקרים שיש לנו כאן? אז אם אתה רוצה להבין מקרים, אנו פסאודו קוד אלה ואז למעשה את הקוד שלהן. וזה הולך להיות, אני חושב, אני מקווה שזה להיות קצת יותר קל ממה שאתה מצפה. כי זה לא כל כך הרבה קוד, למעשה, שהוא ממש מגניב. ממ-הממ? תלמיד: [לא ברור]? מנחה: כן. היה משהו למצוא באמצע. תלמיד: אז אנחנו יכולים להשתמש בזה. אישור. מנחה: מושלמת. אז זה הדבר הראשון שאנחנו צריכים לעשות. אז למצוא את האמצע. גדול. אז יש לך רעיון כיצד תוכל למעשה למצוא את האמצע עם קוד? סטודנט: כן. n מעל 2? מנחה: אז n מעל 2. אז דבר אחד שיש לזכור הוא ש הגבול העליון ותחתון שלך לשנות. אנחנו ממשיכים הצרת החלק של המערך שאנחנו מחפשים. אז n מעל 2 יפעל רק את הדבר הראשון שאנחנו עושים. אז לוקח עליון ותחתון בחשבון, איך יכול להיות שנקבל אלמנט האמצע? מכיוון שאנחנו רוצים האמצע בין עליון ותחתון, נכון? ממ-הממ? תלמיד: [לא ברור]. מנחה: אז יש לנו קצת באמצע. וזה יהיה עליון בתוספת נמוכה יותר מ -2. מדהים. הנה אנחנו מתחילים. למטה בשורה אחת. אתם בדרך שלך. אז עכשיו שיש לנו שלנו אמצע, מה אנחנו רוצים לעשות? רק באופן כללי. אתה לא צריך קוד זה. כן. תלמיד: [לא ברור]? מנחה: אז זה תוספת בגלל שאתה מציאת הממוצעת בין שני שלהם. אז אם אתה חושב עליהם כעל סוג של הגדלת מהצדדים, אחשוב על זה כאשר אתה מתקרב האמצע, אתה רוצה כמו ש. אז אם הייתם משני צדי אמצע, ויש לי כמו 5 ו -7. כאשר אתה מוסיף אותם יחד אתה מקבלים 12, אתה מחלק על ידי 2, הוא 6. לפעמים קשה ל להסביר למה זה עובד, אבל אם אתה עובד דרך דוגמא לפעמים, זה יעזור לך להבין אם זה צריך להיות תוספת או בניכוי. כן. תלמיד: [לא ברור] בדיוק באמצע אם היה להם מקרה שבו יש הרבה מספרים קטנים יותר וכמו מספר אחד גדול? מנחה: אז כל מה שאתה צריך הוא אמצע המערך. אז אם היה לך חבורה של מספרים קטנים ולאחר מכן מספר אחד גדול באמת בסוף, זה לא משנה. כל מה שמשנה הוא ש הם מסודרים, אתה פשוט רוצה להסתכל על אמצע המערך בגלל שאתה עדיין חותך את הבעיה שלך במחצית. מגניב. אז עכשיו שיש לנו אמצע, מה עושים עכשיו? תלמיד: שקלו. מנחה: להשוות. אז להשוות מרכז לvalue_wanted. מגניב. אז אתה רואה כאן יש לנו ערך זה שאנחנו רוצים כאן. זכור את זה הוא מערך. אז אמצע מתייחס למדד. אז אנחנו רוצים לעשות ערכים של אמצעי. אל תשכחו, אם אתה רוצה כדי להשוות, שווים כפולים. אתה עושה אחד שווה אתה רק הולך להקצות מחדש אותו, ואז, כמובן, זה הולך להיות הערך שאתה רוצה. אז לא עושה את זה. אז אנחנו הולכים כדי לראות אם הערכים באמצע שווה לערך שאנחנו רוצים. אל תשכח הפלטה שלך. Dropbox צריך ללכת. אז מה עושים במקרה זה? אם זה מה שאנחנו רוצים לחזור? אנחנו מנסים לומר. תלמיד: הדפסה מ. מנחה: ובכן, אנחנו לא רוצה להדפיס את. אז זה בול כאן, כדי ש רוצה לחזור אמת או שקר. אנחנו אומרים, הוא מספר זה [? RRA? ?] אז אם זה, אנחנו פשוט להחזיר אותו נכונים. אם אני יכול לאיית נכון. תלמיד: למה שלא תחזור אפס? מנחה: אז אתה יכול לחזור אפס, אם אתה רוצה. אבל במקרה הזה, כי הפונקציה שלנו חוזרת בול, אנחנו צריכים לחזור אמת או שקר. תלמיד: כשאתה אומר ביטוי בוליאני, אתה יכול להגדיר את זה שווה לשקר? כמו אם אני רוצה לומר, אם זה מצב לא נפגש, כמו הוא עליון שווה כוזב. האם זה להבין אם אתה רק לשים שווא בצד השני? מנחה: כן. אז בעצם אם אתה אי פעם לעשות משהו כמו הוא עליון או נמוך, שמחזיר אמת או שקר וזה סגנון בעצם רע ל למשל שווה שווה אמיתי או שווה שווה כוזב. אתה רוצה להשתמש בתוצאה ש כעצמו כשק שלך. לא מה שרציתי. זה מה שאני רוצה. אז במקרה שלך אתה שואל על משהו כמו לשמור את זה בג. אז אם יש לנו int main (void) ומשהו כזה. ויש לך אם הוא עליון של קצת קלט ואתה שואל אם אתה יכול לעשות משהו כמו זה? נכון? תלמיד: אני מנסה לעשות [לא ברור] זה. כי אם it's-- מנחה: העכבר. אז אתה רוצה שזה יהיה שקר, נכון? סטודנט: כן. מנחה: אז במקרה הזה אתה רוצה אותו לבצע אם זה לא נכון. אז הדבר מגניב שאתה עושה יש את זה. אז לזכור קריאה נקודה שוללת דברים? זה אומר [לא ברור] פירושו לא. אז אם אנחנו מסתכלים רק חלק זה כאן, שהיית אומר שמעריך ל שווא כפי שאתה רוצה אותו. לא שקר הוא אמת ש פירוש זה היה לבצע. האם זה הגיוני? סטודנט: כן. מנחה: מדהימה. אישור. אז אנחנו פשוט יכולים לחזור נכון במקרה הזה. אז עכשיו יש לנו שתי אחרים מקרים במקרה זה. מה הם שני מקרים האחרים שלנו? בואו פשוט נעשה את זה ככה. אז בואו נתחיל עם דבר אחר אם ערכים באמצע הוא פחות מהערך שאנחנו רוצים. אז הערך שלנו במרכז הוא פחות מהערך שאנחנו מחפשים. אז איזה גבול אתה חושב שאנחנו רוצים לעדכן? עליון או תחתון? עליון? אז באיזה צד של המערך אנחנו הולכים להיות מסתכלים? תלמיד: נמוך. מנחה: אנחנו אנחנו הולכים להיות מסתכל מהשמאל. אז אחר אם הערך קטן הוא פחות. אז הערך האמצעי שלך כאן הוא פחות ממה שאנחנו רוצים. אז אנחנו רוצים לקחת צד ימני של המערך שלנו. אז אנחנו הולכים ל לעדכן את הגבול התחתון שלנו. כך תהיה לנו להקצות מחדש נמוך שלנו. ומה אתה חושב נמוך צריך להיות? תלמיד: הערך האמצעי? מנחה: אז value-- האמצע תלמיד: פלוס 1. מנחה: --plus 1. מישהו יכול להגיד לי למה יש לנו שתוספת 1? תלמיד: [? אין ערך?] יותר שווה לזה. מנחה: העכבר. כי אנחנו כבר יודעים ש הערך האמצעי שלנו אינו שווה ל את זה ואנחנו רוצים להוציא את זה מכל החיפושים שלאחר מכן. אם אתה שוכח שתוספת 1, זה יאהב את הלולאה ללא הגבלת זמן. ואתה פשוט נתפס ב לולאה אינסופית ואז אתה segfault והדברים הולכים רעים. אז תמיד לוודא שאתה לא כולל ערך שזה עתה הסתכל. אז אנחנו דואגים שעם פלוס 1. אז עכשיו יש לנו המצב האחרון שלנו שבו אני תמיד למען הבטיחות אתה יכול לבדוק כאן, אם ערך באחר האמצע הוא גדול מהערך אנחנו רוצים. זה אומר שאנחנו רוצים יד המחצית השמאלית. אז איזה מהם אנחנו הולכים לעדכן? עליון. ומה זה הולך להיות שווה? התיכון מינוס 1, כי, כמובן, אנחנו רוצים כדי לוודא שאנחנו לא מסתכל על שערך מרכזה שוב. ולאחר מכן יש לנו את זה. זֶה הַכֹּל. זה כל מה שהחיפוש בינארי הוא. זה לא שרע, נכון? זה כמו 10 שורות של קוד עם שטח לבן. אז מאוד חזק, מאוד שימושי, אתה יהיה אשתמש בו באחד מpsets מאוחר יותר. אולי לא במקרה הזה, אבל מאוחר יותר. אז ללמוד את זה. אוהב את זה. זה יתייחס אליך גם. אז האם מישהו יש לך שאלות על החיפוש בינארי? כן. תלמיד: האם זה משנה אם n שלך הוא או אפילו מוזר? מנחה: מס ' מכיוון שאנו מטילים אותו לאמצע כ int, זה יהיה פשוט לחתוך אותו. אז הוא יישאר שלם וזה יהיה סופו של דבר למיין את הכל. אז אתה לא צריך לדאוג בקשר לזה. כולם טובים? מדהים. מגניב. אז, אתם קיבלת את זה. מצגת. אז כפי שאנחנו מדברים על, אני יודע דוד הזכיר זמני ריצת מורכבות. אז במקרה הטוב, זה רק אחד, שאנו מכנים זמן קבוע. מישהו יכול להגיד לי למה שעשוי להיות? איזה סוג של תרחיש יהיה כרוך? ממ-הממ. תלמיד: [לא ברור] first-- מנחה: אז האמצע להיות אלמנט ראשון שאנו מגיעים ל, נכון? אז או מערך של אחד או כל מה שאנחנו מחפשים רק קורה להיות טיפה, ממש באמצע. אז זה המקרה הכי טוב שלנו. אתה מקבל בבעיות אמיתיות, כנראה שלא הולך להגיע [לא ברור] שלעתים קרובות. מה לגבי המקרה הגרוע ביותר שלנו? במקרה הגרוע ביותר שלנו הוא n יומן. וכי יש לעשות עם כל כוחות של שני דברים שאני מדבר עליהם. אז במקרה הגרוע ביותר זה אומר שהיינו צריך לקצוץ את המערך מטה עד שזה היה אלמנט של אחד. אז הייתי צריך לכרות אותו במחצית כמספר פעמים שאנחנו יכולים להיות. זו הסיבה שזה n היומן כי אתה פשוט ממשיך להתחלק על ידי שתי. אז הנחות, דברים שאתה צריך לדעת אם אתה אי פעם הולך להשתמש בחיפוש בינארי. האלמנטים שלך חייבים להיות מסודרים. יש להם להיות מסודר, כי כי זו הדרך היחידה ש יכול לדעת אם אתה מסוגל לזרוק חצי מזה. אם היה לך שקית מעורבבת זה של מספרים ואתה אומר, אישור, אני הולך לבדוק את האמצע מספר והמספר שאני מחפש הוא פחות מזה, אני פשוט הולך לזרוק באופן שרירותי את מחצית. אתה לא יודע אם שלך מספרים שבמחצית השנייה. הרשימה שלך צריכה להיות מסודרת. כמו גם, זה עשוי להיות הולך קדימה קצת, אבל אתה צריך להיות גישה אקראית. אתה צריך להיות מסוגל רק ללכת שלאלמנט אמצעי. אם אתה צריך לעבור באמצעות משהו ש או שלוקח צעדים נוספים כדי להגיע לזה אלמנט אמצע, זה לא להתחבר n יותר, כי אתה מוסיף עוד עבודה לתוכה. וזה יגרום לי קטן יותר הגיוני בשבועות, אבל אני פשוט סוג של רציתי להקדים, לתת לכם מושג על מה לבוא. אבל אלה שני הנחות חשובות שאתה צריך לרשימת ינארי. ודא זה מסודרים. זה אחד הגדול ל אתם עכשיו. ועל זה אנחנו יכולים ללכת ל שאר מיני שלנו. אז ארבע בועת sorts--, הכנסה, בחירה, ומיזוג. הם כולם הסוג של מגניב. אם אתם מחליטים לקחת CS 124, תוכל ללמוד על כל מיני מיני. ואם אתה אוהד xkcd, שם הוא על קומיקס ממש מגניב כמו מיני באמת לא יעילים, שבו אני מאוד ממליץ לך הולך להסתכל. אחד מהם הוא כמו סוג פאניקה, ש זה כמו, הו לא, תחזור מערך אקראי. מערכת כיבוי. השאר. אז הומור חנונית הוא תמיד טוב. אז האם מישהו זוכר את סוג כמו רק רעיון כללי איך מיון בועות עובד. אתה זוכר? סטודנט: כן. מנחה: לכו על זה. תלמיד: אז אתם עוברים ו אם זה גדול יותר, אז אתה להחליף את שני. מנחה: ממ-הממ. בדיוק. אז אתה פשוט לחזר דרך. אתה בודק את שני מספרים. אם אחד לפני יותר גדול יותר מזה שלאחר מכן, אתה פשוט להחליף אותם כל כך, כי ב זה כל המספרים גבוהים יותר בדרך בועה עד לקראת סוף הרשימה ואת כל המספרים הנמוכים בועה למטה. האם הוא להראות לכם מגניב אפקט צליל מיון וידאו? זה סוג של מגניב. אז כפי שרוברט פשוט אמר, האלגוריתם כי אתה פשוט המשך ברשימה, החלפת הערכים הסמוכים אם הם לא במטרה. ואז פשוט ממשיך לחזור עד שאתה לא עושה חילופים. אז לא רע, נכון? אז רק שיש לנו דוגמא מהירה כאן. אז זה הולך למיין שלהם בעולים סדר. לכן, כאשר אנחנו עוברים הראשונים זמן, אנחנו מסתכלים דרך שמונה ושישה הם כמובן לא על מנת, שלהחליף אותם. אז מסתכל על הבא. שמונה וארבעה לא כדי. להחליף אותם. ואז בת שמונה ושני, להחליף אותם. הנה אנחנו מתחילים. אז אחרי המסירה הראשונה שלך, לך יודע שהמספר הגדול ביותר שלך הולך להיות כל הדרך בראש כי זה פשוט הולך להיות כל הזמן גדול יותר מכל דבר אחר וזה רק הולך לבועה את כל הדרך עד הסוף שם. האם זה הגיוני לכולם? מגניב. אז אנחנו מסתכלים על המעבר השני שלנו. שישה וארבעה, מתג. שישה ושני, מתג. ועכשיו יש לנו כמה דברים כדי. אז לכל מסירה ש לעשות דרך כל הרשימה שלנו, אנו יודעים כי כמו שמספרים רבים בסוף יהיה כבר מסודרים. אז אנחנו עושים גיחה שלישית, אשר היא החלפה אחת. ולאחר מכן על הרביעי שלנו עובר, יש לנו אפס חריצים. וכך אנו יודעים כי מערך כבר ממוין. וזה גדול דבר עם מיון בועות. אנו יודעים כי כאשר אנו יש אפס עסקות החלף, ש משמעות הדבר היא כל מה ש הוא בסדר גמור. זה סוג של איך אנחנו בודקים. אז אנחנו גם הולכים לקוד בועה סוג שגם הוא לא כל כך נורא. אף אחד מאלה שרעים. אני יודע שהם יכולים להיראות קצת מפחידים. אני יודע מתי אני לקחתי הכיתה, גם כשאני לימד את הכיתה ל בפעם הראשונה בשנה שעברה, אני היה כמו, איך אני עושה את זה? זה הגיוני בתאוריה, אבל איך אנחנו באמת עושים את זה? וזו הסיבה שאני גם רוצה ללכת באמצעות קוד שאתם פה. אז יש לי פסאודו קוד בשבילכם זה זמן. כל כך פשוט לשמור את זה בחשבון כ אנחנו עומדים להעביר מעל. אז יש לנו כמה דלפק ש עוקב אחר ההחלפות שלנו, כי אנחנו צריכים לוודא ש שאנחנו בודקים את זה. ושנעמיק את המערך כל כפי שאנו רק עשינו עם דוגמא זו. אם האלמנט לפני גדול מ האלמנט אחרי שבו אנחנו נמצאים בבית, אנו להחליף אותם ואנחנו להגדילנו הדלפק כי ברגע שאנחנו מחליפים, אנחנו רוצים לתת לדלפק שלנו יודע את זה. כל שאלות שם? משהו נראה מצחיק כאן. תלמיד: האם אתה מגדיר את המונה לאפס בכל פעם שאתה עובר את הלולאה? אתה לא להמשיך חזרה לאפס בכל פעם? מנחה: לא בהכרח. אז מה שקורה הוא שאנחנו עוברים כאן. אז לעשות בזמן, לזכור, זה יתבצע פעם אחת מבלי להיכשל. אז זה הולך להגדיר את דלפק שווה לאפס, אז זה הולך לחזר דרך. כפי שזה סובב בין, זה עדכן דלפק. כפי שמעדכן דלפק, כאשר זה נעשה, כאשר הוא הגיע לקצה המערך, אם הרשימה שלנו לא מסודרים, מונה עודכן. אז הוא בודק את מצבו ואת זה אומר, בסדר, הוא דלפק גדול מאפס. אם זה, לעשות את זה שוב. ברצונך לאפס, כך שכאשר אתה לעבור, הדלפק שווה לאפס. אם אתה עובר מיון מערך, שום דבר לא משתנה, זה נכשל, ואתה להחזיר את הרשימה הממוינת. האם זה הגיוני? תלמיד: זה אולי בקצת. מנחה: אישור. אם יש אחר שאלה שעולה. כן. תלמיד: מה היה התפקיד להיות להעברת האלמנטים? מנחה: אז אנחנו באמת יכולים לכתוב שאם אנחנו הולכים עכשיו. מגניב. אז בנימה זאת, אליסון הולך כדי לעבור בחזרה למכשיר. זה הולך להיות כיף. ויש לנו נחמד שלנו דבר מיון בועות כאן. אז אני כבר עשיתי רכיבה על אופניים באמצעות המערך. יש לנו עסקות החלף שלנו ש שווים לאפס. אז אנחנו רוצים להחליף סמוכים אלמנטים אם הם מקולקלים. אז הדבר הראשון שאנחנו צריכים לעשות הוא לחזר באמצעות המערך שלנו. אז איך אתה חושב שיש סיכוי איטרציות במערך שלנו? יש לנו ולאני שווה 0. אנחנו רוצים אני להיות פחות מ n מינוס 1 מינוס k. ואני אסביר, כי בשני. אז זה אופטימיזציה כאן איפה, זוכר איך אמרתי אחרי כל מסירה דרכנו המערך יודע שכל מה שהוא on-- אז אחרי מעבר האחד יודע שזה מסודרים. אחרי שני מעברים שאנו מכירים שכל זה הוא מסודר. לאחר שלושה עוברים יודע שזה מסודרים. אז כמו שאני iterating באמצעות המערך כאן, הוא זה והקפד ללכת רק דרך מה שאנחנו יודעים הוא לא ממוינים. בסדר? זה בדיוק אופטימיזציה. אתה יכול לכתוב את זה בתמימות רק iterating דרך כל דבר, זה ייקח זמן רב יותר רק. עם ארבע לולאה זה זה רק אופטימיזציה נחמדה כי אנחנו יודעים שאחרי כל מלאים איטרציה באמצעות המערך כאן, כמו כל לולאה מלאה כאן, אנחנו יודעים שאחד יותר מאלמנטים אלו ימויין בסוף. אז אנחנו לא צריכים לדאוג לאלה. האם זה הגיוני לכולם? את הטריק הקטן הזה מגניב? אז במקרה זה, אם אנחנו iterating דרך, אנחנו יודעים שאנחנו רוצים לבדוק אם n המערך וn בתוספת 1 הוא בסדר. אישור. אז הנה פסאודו הקוד. אנחנו רוצים לבדוק אם n מערך וn בתוספת 1 הוא בסדר. אז מה ביכולתנו שם? זה הולך להיות קצת מותנה. זה יהיה אם. תלמיד: אם n המערך הוא פחות ממערך n בתוספת 1. מנחה: ממ-הממ. ובכן, פחות או יותר מ. תלמיד: גדול מ. אז אנחנו רוצים להחליף אותם. בדיוק. אז עכשיו אנחנו מקבלים לתוך מה מנגנון להעברתם? וכך עברו את בקצרה, סוג של פונקצית swap בשבוע שעבר. מישהו זוכר איך זה עובד? אז אנחנו לא יכולים פשוט להקצות מחדש אותם, נכון? כי אחד מהם ילך לאיבוד. אם אמרו שווה ל- B ואז B שווה, כל שניהם פתאומיים הם פשוט שווים ל- B אז מה שאנחנו צריכים לעשות הם יש לי משתנה זמני זה הולך להחזיק משלנו בזמן אנחנו בתהליך של החלפה. אז מה יש לנו הוא שנהיה לנו כמה int זמני הוא שווה to-- אתה יכול להקצות אותו לאיזה אחד אתה רוצה, רק הקפד לעקוב אחר it-- כך במקרה זה, אני הולך להקצות אותו למערך n בתוספת 1. אז זה הולך להחזיק כל מה ש ערך הוא שבבלוק השני שאנחנו מסתכלים. ואז אנחנו יכולים לעשות הוא שאנחנו יכולים ללכת קדימה ומערך להקצות מחדש n בתוספת 1, כי אנחנו יודעים שאנחנו יש ערך שמאוחסן. זהו גם אחד הגדול things-- אני לא יודע אם מישהו מכם היו בעיות שבו אם אתה עובר שני שורות קוד פתאום דברים עבדו. להזמין חשוב מאוד בCS. כדי לוודא שאתה שרטטת דברים אם ניתן לעשות כלמה שבאמת קורה. אז עכשיו אנחנו הולכים ל להקצות מחדש n מערך פלוס 1, כי אנחנו יודעים שאנחנו יש ערך שמאוחסן. ואנחנו יכולים להקצות את זה למערך n או במקרה מערך זה אני. יותר מדי משתנה. אישור. מערך אז עכשיו מחדש אני בתוספת 1 שווה מה שיש במערך i. ועכשיו אנחנו יכולים לחזור ו להקצות מערך i למה? כל אחד? תלמיד: 10. מנחה: 10. בדיוק. ועוד דבר אחד אחרון. אם יש לנו החלפנו את זה עכשיו, מה שאנחנו צריכים לעשות? מה הדבר אחד זה הולך לספר לנו אם אי פעם לסיים תכנית זו? מה אומר לנו שאנו יש רשימה ממוינת? אם אנחנו לא לבצע כל עסקות החלף, נכון? אם חילופים שווים ל אפס בסוף זה. אז בכל פעם שאתה מבצע החלפה, כפי שאנו רק עשיתי כאן, אנחנו רוצים לעדכן את חילופים. ואני יודע שלא היה שאלה קודם לכן על שאתה יכול להשתמש אפס או אחד במקום של אמת או שקר. וזה מה שזה עושה כאן. אז זה אומר שאם לא חילופי. אז אם חילופים הוא אפס, שis-- תמיד לקבל האמיתות שלי וfalses שלי מעורבות. אנחנו רוצים אותנו להעריך לנכון, וזה לא. אז אם זה אפס, אז זה שקר. אם אתה שולל אותו עם [? לדפוק?] הוא הופך להיות אמיתי. אז קו זה מבצע. אמיתות ושקר ו אפסים ואחדים לקבל מטורפים. רק אם אתה הולך לאט דרכו זה יהיה הגיוני. אבל זה מה שזה קטן קצת קוד כאן עושה. אז זה בודק אנחנו עשינו כל עסקות החלף. אז אם זה כל דבר חוץ מזה אפס, זה הולך להיות כוזב וכל העניין הוא הולך לבצע שוב. מגניב? תלמיד: מה הפסקה עושה? מנחה: לשבור רק שובר אותך מחוץ לעניינים. אז במקרה הזה זה היה בדיוק כמו בסופו של התכנית ואתה פשוט היית יש לך רשימה הממוינת. תלמיד: מדהים. מנחה: אני מצטער? תלמיד: בגלל שאנחנו בעבר השתמש בכתב 1 על כתב אפס להציג שאם זה יעבוד או לא. מנחה: כן. כך שאתה יכול לחזור אפס או 1. במקרה זה, כי אנחנו לא ממש עושה שום דבר עם הפונקציה, אנחנו רק רוצים את זה כדי לשבור. באמת לא אכפת לנו על זה. הבלם טוב גם אם הוא משמש לפריצה של ארבע לולאות או תנאים ש אתה לא רוצה לשמור על ביצוע. זה פשוט לוקח אותך מהם. זה קצת של דבר ניואנס. אני מרגיש שיש שם הרבה נפנוף יד, כמו שאתה תלמד על זה בקרוב. אבל תוכל ללמוד על זה בקרוב. אני מבטיח. אישור. אז האם כולם מקבלים מיון בועות? לא רע. איטרציות ב, דברים החלפת שימוש ב משתנה זמני, וכולנו מוכנים לשם? מגניב. מדהים. אישור. חזור ל- PowerPoint. כל שאלות באופן כללי על אלה עד כה? מגניב. ממ-הממ. תלמיד: [לא ברור] int ראשי בדרך כלל. האם יש לך כדי לקבל אותו לזה? מנחה: אז אנחנו פשוט מחפשים רק באלגוריתם המיון בפועל. אם היה לו שאתה בתוך כמו תכנית גדולה יותר, היית במקום עיקרי int. תלוי איפה אתה להשתמש באלגוריתם זה, זה יהיה לקבוע מה הוחזר על ידו. אבל למקרה שלנו, אנחנו בהחלט מסתכל איך עושה את זה בפועל לחזר באמצעות מערך. אז אנחנו לא לדאוג בקשר לזה. אז אנחנו מדברים על המקרה הטוב ביותר ו התרחישים הגרועים ביותר לחיפוש בינארי. אז זה גם חשוב לעשות כי לכל אחד מהמינים שלנו. אז מה אתה חושב שהוא הגרוע ביותר מקרה זמן ריצה של מיון בועות? אתם זוכרים? תלמיד: N מינוס 1. מנחה: N מינוס 1. אז זה אומר שיש n מינוס 1 השוואות. אז דבר אחד הוא להבין כי בגרסה הראשונה, אנו עוברים, אנו משווים two-- אלה אז זה 1. שני אלה, שלוש, ארבעה. אז אחרי איטרציה האחת כבר יש ארבע השוואות. כאשר על זמן ריצה וn אני מדבר. N מייצג את מספר ההשוואות כפונקציה של מרכיבים כמה יש לנו. בסדר? אז אנחנו עוברים, יש לנו ארבעה. בפעם הבאה שאתה יודע שאנחנו לא צריך לטפל בזה. אנו משווים את שני אלה, שני אלה, שני אלה, ואם לא היה לנו כי אופטימיזציה עם ארבע הלולאה שכתבתי, היית להשוות בכאן בכל מקרה. אז היית צריך לרוץ דרך המערך ולעשות השוואות n n פעמים, כי בכולנו זמן לרוץ דרכו אנחנו פחות דבר אחד. ובכל פעם שאנחנו מריצים דרך המערך, אנחנו עושים השוואות n. אז זמן הריצה שלנו לכך היא למעשה n בריבוע, ש הרבה יותר גרוע בנו יומן הסוף בגלל ש משמעות הוא שאם היו לנו ארבעה מיליארדים אלמנטים, זה הולך לקחת לנו ארבעה מליארד בריבוע במקום 32. אז לא זמן הריצה הטובה ביותר, אבל עבור כמה דברים, אתה יודע, אם אתה נמצא ב טווח מסוים של אלמנטים מיון בועות יכול להיות בסדר להשתמש. אישור. אז עכשיו מה שקורה זמן הריצה הטובה ביותר? תלמיד: אפס? או 1? מנחה: אז 1 היית להיות השוואה אחת. תקין. תלמיד: N מינוס 1? מנחה: אז, כן. אז n מינוס 1. בכל פעם שיש לך מושג כמו n מינוס 1, אנחנו נוטים פשוט שחררו אותו ואנחנו רק אומרים n כי יש לך כדי להשוות כל אחד מthese-- כל זוג. כך שזה יהיה n מינוס 1, שבו אנו אנחנו רק רוצים לומר הוא כ n. עם זמן ריצה כאשר יש לך עסק, הכל בקירוב. כל עוד המעריך הוא נכון, אתה די טוב. זה איך אנחנו מתמודדים עם זה. כך שהמקרה הטוב הוא n, ש משמעות הדבר היא שהרשימה כבר מסודרים, וכל מה שאנחנו צריכים לעשות זה לרוץ דרך ולבדוק שזה מסודרים. מגניב. בְּסֵדֶר. אז כפי שאתם רואים כאן, אנחנו רק צריכים כמה גרפים יותר. אז n בריבוע. כיף. הרבה יותר גרוע מn כפי שאנו רואים, ו הרבה, הרבה יותר גרוע מ2n היומן. ואז אתה גם מקבל לתוך יומני יומן. ואתה לקחת את 124, אתה נכנסת ל כמו כוכב יומן, שהוא כמו משוגע. אז אם אתה מעוניין, יומן בדיקת כוכב. זה סוג של כיף. אז יש לנו התרשים הגדול הזה. , רק ראש בראש זה תרשים נפלא שיש לאמצע הקדנציה שלך, כי אנחנו עוד לשאול אותך המדלל אלה. אז פשוט ראש בראש, יש לי זה עליך אמצע הקדנציה בגיליון לרמות נחמד שלך יש. אז אנחנו פשוט הסתכלנו על מיון בועות. במקרה הגרוע ביותר, n בריבוע, מקרה טוב, n. ואנחנו הולכים להסתכל על אחרים. וכפי שאתם יכולים לראות, רק אחד שבאמת עושה טוב הוא סוג של מיזוג, אשר נגיע למה. אז אנחנו הולכים ללכת ל הסוג הבא here-- בחירה. מישהו זוכר איך מבחר עבד מין? לכו על זה. תלמיד: בעיקרון לעבור סדר וליצור רשימה חדשה. ובדיוק כפי שאתה שם את המרכיבים ב, לשים אותם במקום הנכון ברשימה החדשה. מנחה: אז שצלילים יותר כמו סוג ההכנסה. אבל אתה ממש קרוב. הם דומים מאוד. גם אני מקבל אותם מעורב לעתים. לפני סעיף זה הייתי כמו, לחכות. אישור. אז מה אתה רוצה לעשות הוא מיון בחירה, הדרך שאתה יכול לחשוב על זה ועל הדרך אני מוודא שאני משתדל לא להיכנס לערבב אותם, זה עובר והוא בוחר המספר הקטן ביותר ואת זה מכניס כי בתחילת הרשימה שלך. זה מחליף אותו עם זה מקום ראשון. למעשה יש להם דוגמא בשבילי. מדהים. אז רק דרך לחשוב על בחירת it-- סוג, בחר את הערך הקטן ביותר. ואנחנו הולכים לרוץ דרך דוגמא כי אני חושב שאעזור לי כי אני חושב חזותיים תמיד לעזור. אז אנחנו מתחילים עם משהו כי הוא לא ממוינים לחלוטין. האדום יהיה ממוין, ירוק ימויין. כל זה יהיה הגיוני בשני. אז אנחנו עוברים ושנעמיק מההתחלה ועד הסוף. ואנחנו אומרים, בסדר, 2 הוא המספר הקטן ביותר שלנו. אז אנחנו הולכים לקחת 2 ואנחנו הולכים כדי להעביר אותה מול המערך שלנו כי זה המספר הקטן ביותר שיש לנו. אז זה מה שזה עושה כאן. זה רק הולך להחליף את שני אלה. אז עכשיו יש לנו מסודרים חלק וחלק לא ממוינת. ומה טוב לזכור על מיון בחירה הוא שאנחנו בחירה היחידה מחלק לא ממוינים. חלק ממוין אתה פשוט להשאיר לבד. ממ-הממ? תלמיד: איך הוא יודע מה הוא הקטן ביותר ללא השוואתה לכל ערך אחר במערך. מנחה: זה להשוות את זה. אנחנו אוהבים לדלג עליה. זה רק כללי כללי. כן. כאשר אנו כותבים את הקוד אני בטוח שאתה אהיה מרוצה יותר. אבל לך לאחסן את זה ראשון אלמנט כקטן ביותר. אתה משווה את ואתה אומר, בסדר, זה קטן יותר? כן. שמור את זה. הנה הוא קטן יותר? לא? זה הקטן ביותר שלך, להקצות מחדש אותו לערך שלך. ואתה תהיה הרבה יותר מאושר כאשר אנו עוברים את הקוד. אז אנחנו עוברים, אנחנו להחליף אותו, אז אנחנו מסתכלים על חלק לא ממוינים זה. אז אנחנו הולכים כדי לבחור שלוש מתוך. אנחנו הולכים לשים על זה ב סוף החלק ממוין שלנו. ואנחנו פשוט הולכים להמשיך לעשות ש, עושה את זה, ועושה את זה. אז זה הסוג שלנו של פסאודו קוד כאן. אנחנו לקודד אותו כאן בשניים. אבל רק משהו ללכת דרך ברמה גבוהה. אתה הולך לעבור מ אני שווה 0 עד n מינוס 2. זה ייעול נוסף. אל תדאגו יותר מדי על זה. אז כפי שאתם אומרים. כיעקב אמר, איך אנחנו לעקוב אחר מה הוא המינימום שלנו? איך אנחנו יודעים? אנחנו צריכים להשוות כל מה שברשימה שלנו. אז מינימום שווה i. זה רק אומר שבמקרה זה המדד של הערך המינימאלי שלנו. אז זה הולך לחזר דרך וזה הולך מj שווה i בתוספת 1. אז אנחנו כבר יודעים ש זה האלמנט הראשון שלנו. אנחנו לא צריכים להשוות את זה לעצמו. אז אנחנו מתחילים להשוות אותו למשנהו אחד וזו הסיבה שזה אני בתוספת 1 לn מינוס 1, שהוא קצה המערך שם. ואנחנו אומרים שאם מערך ב j הוא פחות מ דקות מערך, אז להקצות מחדש בי המדדים המינימליים שלנו הוא. ואם דקות לא שווה לי, כ שבבו היינו חוזר לכאן. אז כמו בעת שעשינו את זה ראשון. במקרה זה, זה היה מתחיל ב אפס, זה יהיה סופו של דבר שני. אז דקות לא הייתם שווה לי בסופו של הדבר. ש מאפשר לי יודע ש אנחנו צריכים להחליף אותם. אני מרגיש כמו דוגמא מוחשית יעזור הרבה יותר מזה. אז אני לקודד את זה איתכם עכשיו ואני חושב שזה יהיה טוב יותר. מיני נוטים לעבוד ככה שב זה בדרך כלל טוב יותר, רק כדי לראות אותם. אז מה שאנחנו רוצים לעשות הוא אנחנו רוצים ראשון הקטנים ביותר אלמנט בעמדתה במערך. בדיוק מה שיעקב אמר. אתה צריך לאחסן, שאיכשהו. אז אנחנו הולכים להתחיל כאן iterating על המערך. אנחנו הולכים להגיד שזה שלנו ראשון, רק כדי להתחיל עם. אז אנחנו הולכים להיות int הקטן ביותר הוא שווה למערך בi. אז דבר אחד שם לב, כל לולאת זמן זה מבצע, אנחנו מתחילים צעד אחד קדימה לאורך. כאשר אנחנו מתחילים להסתכל על זה אחד. בפעם הבאה שנעמיק דרך, אנחנו מתחילים בזה והקצאה את הערך הקטן ביותר שלנו. אז זה מאוד דומה למיון בועות שבו אנחנו יודעים שאחרי מעבר אחד, המרכיב האחרון הוא מסודרים. עם מיון בחירה, זה בדיוק ההפך. בכל מסירה, אנו יודעים ש הראשון הוא מסודר. לאחר המעבר שני, שנייה אחת ימויין. וכפי שראית בדוגמאות השקופיות, החלק מסודרים שלנו רק הולך וגובר. זאת על ידי הגדרה הקטנה ביותר שלנו למערכים אני, כל מה שהוא עושה הוא ההצרה מה אנחנו מסתכלים על כך כ כדי למזער את המספר השוואות שאנחנו עושים. האם זה הגיוני לכולם? האם אתה צריך אותי כדי לרוץ דרך ש שוב איטי יותר או במילים אחרות? אני שמח. אישור. אז אנחנו אחסון ערך בנקודה זו, אבל אנחנו גם רוצים לאחסן את המדד. אז אנחנו הולכים לחנות עמדה של קטן אחד, שרק הולך להיות אני. אז עכשיו יעקב הוא מרוצה. יש לנו דברים מאוחסנים. ועכשיו אנחנו צריכים להסתכל דרך החלק ממוין של המערך. אז במקרה הזה זה יהיה ממוין שלנו. זה אני. אישור. אז מה אנחנו הולכים לעשות הולך להיות ללולאה. בכל פעם שאתה צריך לחזר באמצעות מערך, המוח שלך יכול ללכת ללולאה. אז לכמה k int equals-- מה שאנחנו חושבים k הולך שווה להתחיל? זה מה שאנחנו מוגדרים כקטנים ביותר שלנו ערך ואנחנו רוצים להשוות אותו. מה אנחנו רוצים להשוות את זה ל? זה הולך להיות הבא זה, נכון? ולכן אנחנו רוצים k להיות מאותחלים כדי שאני ועוד 1 כדי להתחיל. ואנחנו רוצים k במקרה זה אנו כבר גודל מאוחסן כאן, כדי שנוכל פשוט להשתמש בגודל. גודל להיות הגודל של המערך. ואנחנו רק רוצים לעדכן את k ידי אחד בכל פעם. מגניב. אז עכשיו אנחנו צריכים למצוא האלמנט הקטן ביותר כאן. אז אם אנחנו לחזר דרך, אנחנו רוצה לומר, אם מערך בk הוא פחות מ value-- הקטן ביותר שלנו זה מקום שבי שאנחנו בעצם שמירה על המסלול של מה here-- הקטן ביותר אז אנחנו רוצים להקצות מחדש מהו ערך הקטן ביותר שלנו. משמעות דבר היא כי, הו, אנחנו iterating דרך כאן. לא משנה מה הערך הוא כאן הוא לא הדבר הקטן ביותר שלנו. אנחנו לא רוצים את זה. אנחנו רוצים להקצות מחדש אותו. אז אם אנחנו reassigning זה, מה לעשות אתה חושב שאולי יהיה בקוד זה כאן? אנחנו רוצים להקצות מחדש הקטן ביותר ומיקום. אז מה הוא הקטן ביותר עכשיו? תלמיד: k מערך. מנחה: k מערך. ומה היא עמדה עכשיו? מה המדדים הערך הקטן ביותר שלנו? זה פשוט k. אז k מערך, k, הם מתאימים. לכן אנחנו רוצים להקצות מחדש ש. ואז אחרי שמצאנו הקטן ביותר שלנו, כך בסוף זה ללולאה כאן מצאנו מה הקטן ביותר שלנו הערך הוא, אז אנחנו פשוט להחליף אותו. במקרה זה, כמו לומר שלנו הערך הקטן ביותר הוא כאן. זהו הערך הקטן ביותר שלנו. אנחנו רק רוצים להחליף אותו כאן, שהוא מה שפונקצית swap בתחתית עשה, שאנחנו פשוט כתבנו את יחד לפני כמה דקות. אז זה צריך להיראות מוכר. ואז זה יהיה פשוט לחזר דרך עד שהוא מגיע כל הדרך עד הסוף, מה שאומר שאתה יש אפס אלמנטים שהם לא ממוינים וכל דבר אחר כבר מסודרים. הגיוני? קצת יותר קונקרטי? העזרה הקוד? תלמיד: לגודל, אתה אף פעם לא להגדיר אותו או לשנות אותו, איך הוא יודע? מנחה: אז דבר אחד תבחין כאן הוא גודל int. אז אנחנו אומרים בסוג sort-- זה היא פונקציה בזה case-- זה מיון בחירה, זה עבר עם הפונקציה. אז אם זה לא עבר ב, היית עושה משהו כמו עם האורך של המערך או שהיית איטרציות ב כדי למצוא את האורך. אבל בגלל זה עבר ב, אנחנו יכולים פשוט להשתמש בו. אתה פשוט מניח שהמשתמש נתתי לך גודל חוקי ש מייצג למעשה גודל של המערך שלך. מגניב? אם יש לכם בעיות עם אלה או רוצה מיני יותר תרגול קידוד בעצמך, אתה צריך ללכת לstudy.cs50. זה כלי. יש להם בודק ש למעשה אתה יכול לכתוב. הם עושים פסאודו קוד. יש להם עוד קטעי וידאו ושקופיות כולל אלה שאני משתמש כאן. אז אם אתה עדיין מרגיש קצת מטושטש, לנסות את זה. כמו תמיד, באו לדבר איתי, מדי. שאלה? תלמיד: האם אתה אומר גודל מוגדר בעבר? מנחה: כן. גודל המוגדר עד בעבר כאן בהצהרה על הפונקציה. אז אתה מניח שזה כבר עבר ב על ידי המשתמש, ולמען הפשטות, אנחנו הולכים להניח ש משתמשים נתנו לנו את הגודל הנכון. מגניב. אז זה מיון בחירה. חבר'ה, אני יודע שאנחנו לומדים הרבה היום. זה נתונים צפופים לסעיף. אז עם זה, אנחנו הולכים ללכת למיון הכנסה. אישור. אז לפני שאנחנו צריכים לעשות ניתוח זמן הריצה שלנו כאן. אז במקרה הטוב, מובן מאליו מאז שהראיתי לך השולחן כבר סוג של נתן אותו. אבל מקרה זמן הריצה הטובה ביותר, מה אנחנו חושבים? הכל מסודרים. N בריבוע. למישהו יש הסבר למה אתה חושב? תלמיד: אתה משווה through-- מנחה: העכבר. אתה משווה דרך. בכל איטרציה, למרות ש אנחנו decrementing זה על ידי אחד, אתה עדיין מחפש דרך הכל כדי למצוא לו הקטן ביותר. אז גם אם הערך הקטן ביותר שלך הוא כאן בתחילת, אתה עדיין אתה משווה את זה נגד כל דבר אחר כדי לוודא שזה הדבר הקטן ביותר. אז תקבלו בסופו פועל באמצעות כ n בריבוע פעמים. בְּסֵדֶר. ומה במקרה הגרוע ביותר? גם n בריבוע בגלל שאתה הולך לעושה אותו הליך. אז במקרה הזה, בחירה סוג יש משהו כי אנחנו גם קוראים לריצה צפויה. אז באחרים, אנחנו רק יודעים הגבולות העליונים ותחתונים. בהתאם לאופן מטורף שלנו רשימה היא או איך לא ממוינים זה, הם נעים בין n או n בריבוע. אנחנו לא יודעים. אבל בגלל שיש לי מיון בחירה זהה הגרוע ביותר ומקרה הטוב ביותר, שאומר לנו ש לא משנה איזה סוג של קלט אנו יש לי, בין אם זה לחלוטין מיון או לחלוטין להפוך מסודרים, זה הולך לקחת את אותה הכמות של זמן. אז במקרה זה, אם אתה זוכר מהשולחן שלנו, זה באמת היה ערך ש שני מיני אלה לא צריכים, וזה זמן ריצה צפויה. כך אנו יודעים כי בכל פעם ש אנו מפעילים מיון בחירה, זה מובטח לרוץ זמן n בריבוע. אין שונות קיימים. זה פשוט צפוי. ו, שוב, אם אתה רוצה ללמוד יותר, לקחת CS 124 באביב. בְּסֵדֶר. אנחנו כבר ראינו את זה. מגניב. סוג אז הכנסה. ואני כנראה הולך ללהבה לעבור את זה. אני לא יש לכם קוד זה. אנחנו פשוט לעבור את זה. אז מיון ההכנסה הוא סוג של דומה למיון בחירה שביש לנו שני לא ממוינת ומסודר על חלק מהמערך. אבל מה ששונה הוא ש כפי שאנו עוברים אחד אחד, רק שאנחנו לוקחים כל מספר הוא הבא לא ממוינים שלנו, וכראוי למיין את זה למערך ממוין שלנו. זה יהיה הגיוני יותר עם דוגמא. אז כל מה שמתחיל כלא ממוין, בדיוק כמו עם מיון בחירה. ואנחנו הולכים כדי למיין את זה עולה סדר כפי שאנו כבר. אז בסיבוב הקודם שלנו אנחנו לוקחים את הערך הראשון ואנחנו אומרים, בסדר, אתה עכשיו ברשימה בעצמך. מכיוון שאתה ברשימה בעצמך, אתה מסודרים. ברכות על היותו האלמנט ראשון במערך זה. אתה כבר מסודרים כל בעצמך. אז עכשיו יש לנו מסודרים ומערך לא ממוינת. אז עכשיו אנחנו לוקחים הראשונים. מה קורה בין כאן וכאן הוא שאנחנו אומרים, בסדר, אנחנו הולכים להסתכל על הערך הראשון של המערך ממוין שלנו ואנחנו הולכים להכניס אותה בה מקום נכון במערך ממוין. אז מה אנחנו הוא לקחת 5 ו אנחנו אומרים, בסדר, 5 גדול מ- 3, אז אנחנו פשוט להכניס את זה נכון בצד הימין של זה. אנחנו טובים. אז אנחנו הולכים לצד אחד שלנו. ואנחנו לוקחים 2. אנחנו אומרים, בסדר, 2 פחות מ -3, כך שאנחנו יודעים שזה צריך להיות ב מול הרשימה שלנו עכשיו. אז מה שאנחנו עושים זה לדחוף 3 ו -5 למטה ואנחנו עוברים 2 שלחריץ הראשון. אז אנחנו רק הכנסתו ל המקום הנכון זה צריך להיות. ואז אנחנו מסתכלים עלינו הבא, ואנחנו אומרים 6. אישור, 6 גדול מ כל דבר במערך ממוין שלנו, אז אנחנו פשוט לתייג אותו עד הסוף. ואז אנחנו מסתכלים על 4. 4 הוא פחות מ -6, זה פחות מ 5 אבל זה יותר מ 3. אז אנחנו פשוט להכניס אותו ישר לתוך האמצע בין 3 ל 5. אז כדי לעשות את זה קצת קצת יותר קונקרטי, כאן הוא סוג של רעיון של מה שקרה. אז עבור כל רכיב לא ממוינים, אנחנו לקבוע היכן בחלק ממוין זה. אז תוך התחשבות מסודרים ולא ממוין, אנחנו צריכים לעבור דרך ודמות איפה זה משתלב במערך ממוין. ואנחנו מכניסים אותו על ידי העברה אלמנטים בצד הימין שלו למטה. ואז אנחנו פשוט לשמור iterating דרך עד ש יש רשימה ממוינת לחלוטין שבו לא ממוינים כעת אפס וממוין תופס שלמות של הרשימה שלנו. אז, שוב, לעשות עוד דברים יותר קונקרטי, יש לנו פסאודו קוד. אז בעצם להוא אני שווה ל0 עד n מינוס 1, זה רק האורך של המערך שלנו. יש לנו כמה אלמנט שהוא שווה ל המערך הראשון או המדדים הראשונים. אנו קובעים j שווה לזה. אז בזמן j גדול מ אפס והמערך, j מינוס 1 גדול מ אלמנט, אז כל מה שעושה הוא לוודא ש j שלך באמת מייצג החלק ממוין של המערך. אז בזמן שעדיין יש דברים כדי למיין ומינוס j אחד is-- מה הוא היסוד שלה? J לא הוגדר כאן. זה סוג של מעצבן. אישור. בכל אופן. אז j מינוס 1, אתה בודק האלמנט לפני ש. אתה אומר, בסדר, הוא האלמנט לפני כל המקום שאני am-- בוא למעשה לצייר את זה. אז בואו נגיד שזה הוא כמו במעבר השני שלנו. אז אני הולך להיות שווה ל1, שהוא כאן. אז אני הולך להיות שווה ל 1. זה יהיה 2, 4, 5, 6, 7. בְּסֵדֶר. אז האלמנט שלנו במקרה זה הולך להיות שווה ל 4. ויש לנו כמה j זה הולך להיות שווה ל 1. אה, j הוא decrementing. כי זה מה שזה. אז j שווה ל i, אז מה זה אמרה היא שככל שאנו מתקדמים, אנחנו רק לוודא שאנחנו לא מעל אינדקס בדרך זו, כאשר אנחנו מנסים להכניס דברים לרשימה הממוינת שלנו. לכן, כאשר j שווה ל -1 במקרה זה ו מינוס j מערך one-- כך 1 מינוס j מערך הוא 2 בcase-- זה אם זה גדול יותר מהאלמנט, אז כל זה עושה הוא הסטה את רוחות. אז במקרה הזה, אחד מינוס j מערך יהיה מערך אפס, אשר 2. 2 הוא לא גדולים יותר מ -4, אז זה לא מתבצע. אז השינוי לא זז כלפי מטה. מה שזה עושה כאן הוא פשוט נע המערך ממוין שלך למטה. במקרה זה, בעצם, אנחנו יכול do-- בואו נעשה את זה 3. אז אם אנחנו ללכת דרך עם דוגמא זו, אנחנו עכשיו כאן. זה מסודרים. זה לא ממוינים. מגניב? אז היא i שווה ל 2, כך האלמנט שלנו הוא שווה ל- 3. וי שלנו הוא שווה ל 2. אז אנחנו מסתכלים דרך ואנחנו אומר, בסדר, הוא מינוס j מערך אחד גדול יותר מהאלמנט שאנחנו מסתכלים? והתשובה היא כן, נכון? 4 הוא יותר מ 3 וי הוא 2, כך הקוד הזה. אז עכשיו מה שאנחנו עושים מערך ב 2, כל כך כאן, אנו להחליף אותם. אז אנחנו פשוט אומרים, בסדר, מערך ב -2 עכשיו הולך להיות 3. וי הולך להיות שווה מינוס j 1, שהוא 1. זה נורא, אבל אתם מבינים את הרעיון. J הוא שווה ל 1 עכשיו. וי מערך הוא רק הולך להיות שווה לאלמנט שלנו, שהיה 4. אני מחקתי משהו שאני לא צריך יש להם או משהו miswrote, אבל אתם מבינים את הרעיון. זה לעבור בn. ואז, אם זה היה, היית זה לולאה שוב וזה הייתי אומר, בסדר, j הוא 1 עכשיו. ומינוס j מערך 1 הוא כעת 2. האם 2 פחות מהאלמנט שלנו? לא? זה אומר שיש לנו הכניס את האלמנט הזה במקום הנכון במערך ממוין שלנו. אז אנחנו יכולים לקחת את זה ואנחנו אומרים, אישור, מערך המיון שלנו הוא כאן. וזה היה לוקח מספר זה 6 ולהיות כמו, אישור, הוא 6 פחות ממספר זה? לא? מגניב. אנחנו בסדר. לעשות את זה שוב. אנחנו אומרים 7. האם 7 פחות מהסוף של המערך ממוין שלנו? מס ' אז אנחנו בסדר. אז זה יהיה מסודר. בעיקרון כל זה עושה האם זה אומר לקחת האלמנט הראשון של המערך לא ממוינת שלך, להבין לאן זה הולך במערך ממוין שלך. וזה רק מטפל של חילופים לעשות את זה. אתה בעצם רק החלפה עד שזה במקום הנכון. הדימוי החזותי הוא שאתה נע בכל מה שעל ידי עושה את זה. אז זה כמו מחצית בועת סוג-בבניין. עזיבה מחקר 50. אני מאוד ממליץ לנסות לקוד זה בעצמך. אם יש לך בעיות או שאתה רוצה לראות את הקוד לדוגמה עבור סוג הכנסה, אנא הודע לי. אני תמיד בסביבה. מקרה הגרוע ביותר זמן הריצה אז ומקרה זמן הריצה הטובה ביותר. כפי שראית בחור מהשולחן אני כבר הראיתי לך, זה גם וגם n בריבוע וn. אז סוג של הנוסע של מה שדברנו על עם מיני הקודמים שלנו, הגרוע ביותר מקרה ריצה היא שאם זה לא ממוינים לחלוטין, אנחנו צריכים להשוות את כל הפעמים n אלה. אנחנו עושים המון השוואות כי אם זה בסדר הפוך, אנחנו הולכים להגיד, בסדר, זה הוא אותו, זה טוב, וזה אחד לא צריך להיות בהשוואה נגד הראשונה שחזרה. וכמו שאנחנו מקבלים ל קצה הזנב, יש לנו כדי להשוות, להשוות, ו להשוות נגד כל מה. אז זה בסופו להיות כ n בריבוע. אם זה נכון אז אתה אומר, בסדר, 2, אתה טוב. 3, אתה לעומת 2. אתה טוב. 4, אתה פשוט להשוות את הזנב. אתה טוב. 6, להשוות את הזנב, אתה בסדר. אז לכל נקודה אם זה כבר מסודרים, אתה עושה השוואה אחד. כך שזה רק n. וכי יש לנו מקרה של זמן ריצה הטובה ביותר של n ומקרה זמן ריצה הגרועה ביותר של n בריבוע, אין לנו זמן ריצה צפויה. זה פשוט תלוי ב תוהו ובוהו של הרשימה שלנו יש. ושוב, אחר גרף וטבלה אחרת. אז הבדלים בין מיני. אני רק הולך לרוח באמצעות, אני מרגיש כמו שדיברנו בהרחבה על איך שהם כל הסוג של להשתנות וקישור יחד. אז מיון מיזוג הוא האחרון אני נשא אתכם עם. יש לנו תמונה יפה וצבעונית. אז למזג מיון הוא אלגוריתם הרקורסיבי. אז אתם יודעים מה פונקציה רקורסיבית היא? כל אחד רוצה לומר? אתה רוצה לנסות? אז פונקציה רקורסיבית היא רק פונקציה שקוראת לעצמו. אז אם אתם מכירים עם רצף פיבונאצ'י, זה ייחשב רקורסיבית כי אתה לוקח את שני הקודמים ולהוסיף אותם ביחד לתפוס את הבא בתור שלך. אז רקורסיבית, אני תמיד חושב של רקורסיה ככמו ספירלה אז אתה כמו מתפתל במורדו. אבל זה רק פונקציה שקורא לעצמו. ו, למעשה, ממש במהירות אני יכול להראות לך מה שנראה כמו. אז רקורסיבית כאן, אם אנחנו מסתכלים, זה הוא הדרך רקורסיבית כדי לסכם על מערך. אז כל מה שאנחנו עושים זה יש לנו פונקצית סכום סכום שלוקח גודל ומערך. ואם אתה שם לב, גודל decrements על ידי אחד בכל פעם. וכל שהיא עושה הוא אם x הוא שווה ל zero-- כך שאם הגודל של המערך שווה לzero-- היא מחזירה אפס. אחרת זה מסכם את זה האלמנט האחרון של המערך, ואז לוקח את הסכום של שאר המערך. אז זה פשוט לשבור אותו בבעיות קטנות יותר ויותר. סיפור ארוך קצרה, רקורסיה, פונקציה שקוראת לעצמו. אם זה כל מה שיצאת מזה, זה מה שהיא פונקציה רקורסיבית. אם אתה לוקח 51, תקבל מאוד, מאוד נוח עם רקורסיה. זה ממש מגניב. זה נראה הגיוני כב 03:00 לילה אחד יצא. ואני הייתי כמו, למה יש לי אף פעם לא משתמש בזה? אז לסוג מיזוג, בעצם מה זה הולך לעשות הוא זה הולך לפרק אותו ולשבור אותו מטה עד שהאלמנטים רק אחת. האלמנטים בודדים קלים למיין. אנחנו רואים את זה. אם יש לך אלמנט אחד, זה כבר נחשב ממוין. אז על קלט של n אלמנטים, אם n הוא פחות מ 2, רק לחזור כי אמצעים ש זה או 0 או 1 כפי שראינו. אלה נחשבים אלמנטים ממוינים. אחרת לשבור אותו לשתיים. מיין את המחצית הראשונה, למיין את השנייה מחצית, ואז למזג אותם יחד. למה זה נקרא סוג המיזוג. אז יש לנו כאן אנחנו נטפל אלה. אז אנחנו שומרים שיש להם עד שגודל המערך הוא 1. לכן, כאשר התוצאה 1, אנחנו פשוט לחזור בגלל זה הוא מערך ממוין, ואת זה הוא מערך ממוין, וזה מערך ממוין, כולנו מסודרים. אז מה שאנחנו עושים זה להתחיל ממזג אותם יחד. אז כפי שאתה יכול לחשוב על מיזוג הוא אתה פשוט להסיר את קטן יותר מספר של כל אחד ממערכים תת ורק להוסיף אותו למערך יצא. אז אם אתה מסתכל כאן, כאשר יש לנו ערכות אלה יש לנו 4, 6, ו -1. כאשר אנו רוצים למזג אלה, אנחנו מסתכלים על שני ראשונים אלה ואנחנו אומרים, בסדר, 1 קטן, זה הולך לחזית. 4 ו -6, אין מה להשוות זה ל, רק לתייג אותו עד הסוף. כאשר אנחנו משלבים את שני אלה, אנחנו פשוט לקחת את קטן יותר באחת משני אלה, אז זה 1. ועכשיו אנחנו שותים קטן יותר של שני אלה, כך 2. קטן יותר של שני אלה, 3. קטן יותר של שני, 4, 5, 6 הבאים. אז אתה פשוט מושך את אלה. וכי יש להם מוין בעבר, רק יש לך אחד השוואה בכל פעם שיש. אז עוד קוד כאן, רק ייצוג. אז אתה מתחיל באמצע ו אתה סוג ימין ומהשמאל ואז אתה פשוט למזג אותם. ואין לנו קוד למיזוג ממש כאן. אבל, שוב, אם אתה רוצה ללכת על ללמוד 50, היא תהיה שם. אחרת תבואו לדבר איתי אם אתה עדיין מבולבל. אז דבר מגניב כאן הוא שהמקרה הטוב ביותר, במקרה הגרוע ביותר, וזמן ריצה צפוי כולם ביומן n, ש הרבה יותר טוב מאשר יש לנו ראיתי לשאר מיני שלנו. ראינו n בריבוע ומה שאנחנו באמת להגיע לכאן הוא n n יומן, וזה נהדר. תראה כמה טוב שהוא. כגון עקומה יפה. כל כך הרבה יותר יעיל. אם אי פעם שאתה יכול, להשתמש במיזוג מהסוג. זה יחסוך לך זמן. ואז שוב, כפי שאמרנו, אם אתה למטה באזור הנמוך הזה, זה לא עושה ש הרבה הבדל. אתה קם לאלפים ואלפי כניסות, אתה בהחלט רוצה אלגוריתם יעיל יותר. ושוב, השולחן היפה שלנו, של כל מיני שאתם למדו היום. אז אני יודע שזה היה יום צפוף. זה לא הולך בהכרח כדי לעזור עם pset שלך אתה. אבל אני רק רוצה להפוך את כתב ויתור הסעיף שהוא לא רק על psets. כל החומר הזה הוא הוגן משחק למבחני אמצע הסמסטר שלך. וגם אם אתה עושה להמשיך עם CS, אלה הם יסודות חשובים באמת שהיית צריך לדעת. אז כמה ימים יהיו עזרה נוספת pset קטנה, אבל כמה שבועות יהיו תוכן ממשי הרבה יותר שאולי לא נראה סופר שימושי לך עכשיו, אבל אני מבטיח אם תמשיך ביהיה מאוד, מאוד שימושי. אז זהו זה לסעיף. עד לחוט. אני עשיתי את זה בתוך דקה אחת. אבל הנה לך. ויהיה לי סופגניות או ממתקים. האם מישהו אלרגי ל כל דבר, דרך אגב? ביצים וחלב. אז סופגניות הן לא? אישור. בְּסֵדֶר. לא שוקולד? מטר של כוכבים. מטר כוכבים טובים. אישור. אנחנו הולכים יש לי מטר של כוכבים בשבוע הבא ולאחר מכן. זה מה שאני אקבל. יש לכם שבוע נהדר. לקרוא את האפיון שלך. תודיע לי אם יש לך שאלות. שתי כיתות Pset צריכה להיות יוצא לך עד יום חמישי. אם יש לך שאלות על איך אני מדורג משהו או למה אני מדורג משהו כמו שאני לא, אנא שלח לי, תבואו לדבר איתי. אני זה מטורף קצת שבוע, אבל אני מבטיח אני עדיין אשיב תוך 24 שעות. אז יש לי שבוע, כולם נהדרים. מזל טוב על pset שלך.