[Powered by Google Translate] טומי: בואו נסתכל על מיון בחירה, אלגוריתם
לקחת רשימה של מספרים ומיונם.
אלגוריתם, לזכור, הוא פשוט צעד אחר צעד
הליך להשגת משימה.
הרעיון הבסיסי מאחורי מיון בחירה הוא לחלק את
הרשימה שלנו לשני חלקים -
חלק ממוין וחלק לא ממוין.
בכל צעד של האלגוריתם, מספר מועבר מ
חלק ממוין לחלק מסודר עד סופו של הדבר
כל הרשימה ממוינת.
אז הנה רשימה של שישה מספרים -
23, 42, 4, 16, 8, ו 15.
נכון לעכשיו כל הרשימה נחשבת ללא מיון.
למרות מספר כמו 16 מאי כבר יהיה בנכון
מיקום, האלגוריתם שלנו אין דרך לדעת שעד
כל הרשימה ממוינת.
כך יהיה לנו לשקול כל מספר שיש המיון, עד שנמיין
זה בעצמנו.
אנחנו יודעים שאנחנו רוצים את הרשימה כדי להיות בסדר עולה.
אז אנחנו רוצים לבנות את החלק הממוין של הרשימה שלנו
משמאל לימין, הקטן ביותר לגדול ביותר.
כדי לעשות זאת, יצטרך למצוא את האלמנט הממוין המינימום
ולשים אותו בסוף החלק הממוין.
מאז רשימה זו אינה ממוינת, הדרך היחידה לעשות זאת היא
להסתכל על כל אלמנט בחלק הממוין, נזכר
איזה רכיב הוא נמוך ביותר ומשווה
כל רכיב לזה.
כך יהיה לנו קודם להסתכל 23.
זהו היסוד הראשון שראינו, ולכן אנחנו זוכרים
זה כמינימום.
כעת נדון בגיל 42.
42 הם גדולים יותר מאשר 23, ולכן 23 הם עדיין מזעריים.
הבא הוא 4 שהם פחות מ 23, ולכן אנחנו זוכרים 4
כמינימום החדש.
הבא הוא 16 שהוא גדול יותר מ 4, אז 4
עדיין המינימום.
8 הן גדולים יותר מאשר 4, ו 15 הן גדולים יותר מאשר 4, ולכן 4 חייבות להיות
האלמנט הקטן ביותר הממוין.
אז למרות שכבני אדם אנחנו יכולים לראות מייד ש4 הם
האלמנט המינימאלי, האלגוריתם שלנו צריך להסתכל על
כל אלמנט לא ממוין, גם לאחר שמצאנו את 4 -
אלמנט מינימום.
אז עכשיו שמצאנו את האלמנט המינימאלי, 4, אנחנו רוצים
כדי להעביר אותו לחלק הממוין של הרשימה.
מכיוון שזו היא הצעד הראשון, זה אומר שאנחנו רוצים לשים ב4
תחילת הרשימה.
נכון לעכשיו 23 הם בתחילת הרשימה, כך
בואו להחליף 4 ו 23.
אז עכשיו הרשימה שלנו נראית כך.
אנו יודעים כי 4 חייבים להיות במיקומה הסופי, משום שהוא
גם האלמנט הקטן ביותר והאלמנט בתחילה
מהרשימה.
אז זה אומר שאנחנו אף פעם לא נצטרך לעבור את זה שוב.
אז בואו נחזור על תהליך זה כדי להוסיף אלמנט נוסף
חלק ממוין של הרשימה.
אנחנו יודעים שאנחנו לא צריכים להסתכל על 4, כי זה
כבר ממוין.
אז אנחנו יכולים להתחיל ב42, שאנו נזכור כ
אלמנט מינימום.
אז הבא שנסתכל על 23 שהם פחות מ 42, ולכן אנחנו
זוכר את 23 הוא המינימום החדש.
הבא אנו רואים 16 שהן פחות מ 23, ולכן
16 הם המינימום החדש.
עכשיו אנחנו מסתכלים על 8 שהם פחות מ 16, ולכן
8 הם המינימום החדש.
ולבסוף 8 הם פחות מ 15, כך אנו יודעים כי 8 הם מינימום
אלמנט לא ממוין.
אז זה אומר שאנחנו צריכים לצרף 8 למיון
חלק מהרשימה.
כרגע 4 הם האלמנט מסודר בלבד, ולכן אנחנו רוצים למקם
8 לצד 4.
מאז 42 הוא האלמנט הראשון בחלק הממוין של
רשימה, אנחנו רוצים להחליף 42 ו 8.
אז עכשיו הרשימה שלנו נראית כך.
4 ל 8 מייצגים את החלק הממוין של הרשימה, ו
מספרים שנותרו לייצג הממוינים
חלק מהרשימה.
אז בואו נמשיך עם איטרציה אחרת.
אנחנו מתחילים עם 23 הפעם, מכיוון שאנחנו לא צריכים להסתכל על
4 ו 8 יותר, כי יש להם
כבר ממוין.
16 הם פחות מ 23, ולכן אנחנו זוכרים
16 כמינימום החדש.
16 הם פחות מ 42, אבל 15 הוא פחות מ 16, ולכן חייבים להיות 15
האלמנט הממוין המינימום.
אז עכשיו אנחנו רוצים להחליף 15 ו 23 ל
לתת לנו את הרשימה הזאת.
החלק הממוין של הרשימה מורכבת מ4, 8 ו 15, ו
אלמנטים אלה עדיין לא ממוינים.
אבל זה פשוט כל כך קורה כי האלמנט הבא לא ממוין, 16,
כבר ממוין.
עם זאת, אין דרך לאלגוריתם שלנו לדעת כי 16
כבר במיקום הנכון שלו, ולכן אנחנו עדיין צריכים
חוזר בדיוק על אותו התהליך.
כך אנו רואים כי 16 הם פחות מ 42, ו 16 הוא פחות מ 23, ולכן
16 חייבים להיות אלמנט המינימום.
אי אפשר להחליף את האלמנט הזה בעצמו, כדי שנוכל
פשוט להשאיר אותו במיקום זה.
אז אנחנו צריכים עוד אחד של האלגוריתם שלנו עוברים.
42 גדולים מ 23, ולכן חייבים להיות 23
אלמנט ממוין מינימום.
ברגע שאנו מחליפים 23 ו 42, אנחנו בסופו של דבר עימנו סופי
רשימה ממוינת -
4, 8, 15, 16, 23, 42.
אנחנו יודעים 42 חייבים להיות במקום הנכון, מכיוון שזה
אלמנט היחיד שנותר, וזה מיון בחירה.
בואו עכשיו למסד האלגוריתם שלנו עם כמה
pseudocode.
בשורה אחת, אנו יכולים לראות שאנחנו צריכים לשלב יותר
כל אלמנט של הרשימה.
מלבד האלמנט האחרון, מאז היסוד 1
רשימה כבר ממוינת.
על קו 2, אנו רואים במרכיב הראשון של ממוין
חלק מהרשימה כדי להיות המינימום, כפי שעשינו עימנו
למשל, אז יש לנו מה להשוות.
קו 3 מתחיל לולאה שנייה בה אנו לחזר על
כל רכיב לא ממוין.
אנחנו יודעים שאחרי שחזרות, החלק מסודר
הרשימה שלנו חייב להיות i אלמנטים בזה מאז כל צעד
מיני אלמנט אחד.
אז האלמנט הממוין הראשון חייב להיות בעמדתי ועוד 1.
על קו 4, אנו משווים את האלמנט הנוכחי למינימום
אלמנט שראינו עד כה.
אם הרכיב הנוכחי הוא קטן יותר מהמינימום
אלמנט, אז אנחנו זוכרים את האלמנט הנוכחי כחדשים
מינימום על קו 5.
לבסוף, על קווים שישה ושבעה, אנחנו מחליפים את המינימום
אלמנט עם האלמנט הממוין הראשון, ובכך
הוספתו לחלק הממוין של הרשימה.
ברגע שיש לנו אלגוריתם, שאלה חשובה לשאול
את עצמנו כמו מתכנתים הם כמה זמן זה ייקח?
נשאלים את השאלה הראשונה כמה זמן לוקח לזה
אלגוריתם לרוץ במקרה הגרוע ביותר?
זוכרים שאנחנו מייצגים את זה פועל
זמן עם סימון O גדול.
על מנת לקבוע את האלמנט הממוין המינימום, אנחנו
למעשה הייתי צריך להשוות כל רכיב ברשימה כדי
כל אלמנט אחר ברשימה.
באופן אינטואיטיבי, זה נשמע כמו O של מבצע ריבוע n.
כאשר מסתכלים על pseudocode שלנו, יש לנו גם מקוננת בתוך לולאה
עוד לולאה, שאכן נשמעת כמו O
פעולת ריבוע n.
עם זאת, יש לזכור שאנחנו לא צריכים להסתכל על
כל רשימה בעת קביעת המרכיב הממוין המינימום?
ברגע שידענו ש4 מוינו, למשל, לא אצלנו
צריך להסתכל על זה שוב.
אז עושה את זה נמוך זמן הריצה?
לרשימה של 6 אורך שלנו, אנחנו צריכים לעשות 5
השוואות לאלמנט הראשון, ארבעה להשוואות
האלמנט השני, וכן הלאה.
זה אומר שהמספר הכולל של צעדים הוא הסכום של
המספרים השלמים מ 1 עד האורך של רשימת מינוס 1.
אנו יכולים לציין זאת בסיכום.
אנחנו לא נכנסנו לסיכומים לכאן.
אבל מתברר שסיכום זה שווה לפעמי n
n מינוס 1 מעל 2.
או באופן שקול, n בריבוע מעל 2 מינוס n מעל 2.
כאשר מדברים על זמן ריצת אסימפטוטי, מונח בריבוע זה n
הולך לשלוט טווח n זה.
אז מיון בחירה הוא O של n בריבוע.
כזכור, בדוגמא שלנו, מיון בחירה עדיין צריך
לבדוק אם מספר שכבר מסודר
צורך להתרגש.
אז זה אומר שאם רץ מיון בחירה מעל כבר
מסודר על רשימה, זה ידרוש את אותו המספר של צעדים כמו זה
היית כאשר פועלים על רשימה לחלוטין לא ממוינת.
אז מיון בחירה יש מקרה ביצועים טובים ביותר של n בריבוע,
שאנו מייצגים עם אומגת n בריבוע.
וזהו זה למיון בחירה.
זהו רק אחד מהאלגוריתמים הרבים אנו יכולים
להשתמש כדי למיין רשימה.
השמי הוא טומי, וזה cs50.