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

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

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

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

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

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

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

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

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

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

אנו מוצאים כי חמישה הוא האלמנט הקטן ביותר. אנחנו להחליף אותו עם הראשון אלמנט של חלק לא ממוינים. ועכשיו חמש ממוין. 

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

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

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

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

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

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

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