>> [השמעת מוסיקה]
דאג LLOYD: בסדר, כל כך מיון בועות הוא אלגוריתם
אתה יכול להשתמש בו כדי למיין את סט של אלמנטים.
בואו נסתכל על איך זה עובד.
>> אז הרעיון הבסיסי מאחורי מיון בועות הוא זה.
בדרך כלל אנחנו רוצים להעביר גבוהים יותר אלמנטים מוערכים בדרך כלל בצד הימין,
ולהוריד את האלמנטים מוערכים בדרך לשמאל, כפי שהיינו מצפה.
אנחנו רוצים את הדברים הנמוכים להיות ב ההתחלה, והדברים גבוהים יותר
להיות בסוף.
>> איך עושים את זה?
ובכן בקוד פסאודו קוד, אנחנו יכולים לומר, בואו
להגדיר נגד החלפה לערך שאינו אפס.
אנחנו תראו למה אנחנו עושים את זה בשנייה.
ואז אנו חוזרים הבאים תהליך עד לדלפק ההחלפה הוא 0,
או עד שלא עושים שום חילופים בכלל.
>> לאפס את מונה ההחלפה ל 0 אם זה לא כבר 0.
אז להסתכל על כל זוג סמוך של אלמנטים.
אם שני אלה הם מרכיבים לא כדי, להחליף אותם,
ולהוסיף 1 לדלפק ההחלפה.
אם אתה חושב על זה לפני שאתה לדמיין את זה,
שם לב שזה יעבור נמוך אלמנטים מוערכים לשמאל
יותר ויותר מוערך אלמנטים בצד הימין, יעילות עושה את מה שאנחנו רוצים לעשות,
אשר הוא להעביר קבוצות אלה של אלמנטים שבדרך.
בואו לדמיין איך זה עשוי להיראות באמצעות המערך שלנו
שמשמשים לבדיקה את האלגוריתמים הללו.
יש לנו מערך לא ממוינים כאן שוב, שצוין על ידי כל הגורמים
להיות באדום.
ואני מגדיר את דלפק ההחלפה שלי לערך שונה מאפס.
אני באופן שרירותי בחרתי שלילי 1-- זה לא 0.
אנחנו רוצים לחזור על תהליך זה עד דלפק ההחלפה הוא 0.
זו הסיבה שאני מגדיר את ההחלפה שלי בניגוד לכמה ערך שאינו אפס,
כי אחר דלפק החלפה יהיה 0.
אנחנו אפילו לא מתחילים תהליך של האלגוריתם.
אז שוב, הצעדים הן-- לאפס את מונה ההחלפה
0, ואז להסתכל על כל סמוך זוג, ואם הם מקולקלים,
להחליף אותם, ולהוסיף 1 לדלפק ההחלפה.
אז בואו נתחיל בתהליך זה.
אז הדבר הראשון שאנחנו עושים הוא אנו קובעים את דלפק ההחלפה 0,
ואז אנחנו מתחילים לחפש בכל זוג סמוך.
>> אז אנחנו מתחילים ראשון מסתכלים על 5 ו -2.
אנו רואים שהם נמצאים מחוץ ל להזמין ולכן אנחנו להחליף אותם.
ואנחנו מוסיפים 1 לדלפק ההחלפה.
אז עכשיו נגד ההחלפה שלנו הוא 1, ו 2 ו -5 כבר עברו.
עכשיו אנחנו חוזרים על התהליך שוב.
>> אנחנו מסתכל על הזוג הסמוך הבא, 5 ו1-- הם גם מקולקלים,
ולכן אנחנו להחליף אותם ולהוסיף 1 לדלפק ההחלפה.
אז אנחנו מסתכלים על 5 ו -3.
הם מקולקלים, ולכן אנחנו להחליף שלהם ואנו מוסיפים 1 לדלפק ההחלפה.
אז אנחנו מסתכלים על 5 ו -6.
הם בהזמנה, כך שאנחנו לא ממש צריך להחליף משהו הפעם.
אז אנחנו מסתכלים על 6 ו -4.
הם גם מקולקלים, ולכן אנחנו להחליף שלהם ואנו מוסיפים 1 לדלפק ההחלפה.
>> עכשיו שם לב מה קרה.
אנחנו כבר עברנו 6 כל הדרך עד הסוף.
אז במיון בחירה, אם יש לך ראה וידאו זה, מה שעשינו היה
בסופו שלנו נע האלמנטים הקטנים ביותר בבניין
מערך המיון במהותה מ משמאל לימין, הקטן ביותר לגדול ביותר.
במקרה של מיון בועות, אם אנחנו הבא אלגוריתם מיוחד זה,
אנחנו באמת הולכים להיות בנייה המערך ממוין מימין
לשמאל, הגדול ביותר לקטן ביותר.
יעילות יש לנו בועות 6, הערך הגדול ביותר, כל הדרך עד הסוף.
>> וכך אנו יכולים עכשיו להכריז שמסודר,
ובעתיד iterations-- עובר המערך again--
אנחנו לא צריכים לשקול 6 יותר.
אנחנו רק צריכים לשקול אלמנטים לא ממוינים
כאשר אנו מסתכלים על זוגות סמוכים.
אז יש לנו גמר אחד עובר מיון בועות.
אז עכשיו אנחנו חוזרים לשאלה, לחזור עד דלפק ההחלפה הוא 0.
ובכן דלפק ההחלפה הוא 4, אז אנחנו הולכים
כדי לשמור חוזר על תהליך זה שוב.
>> אנחנו הולכים לאפס את מונה ההחלפה 0, ומסתכלים על כל זוג סמוך.
אז אנחנו מתחילים עם 2 ו1-- הם מקולקל, ולכן אנחנו להחליף אותם
ואנחנו מוסיפים 1 לדלפק ההחלפה.
2 ו -3, שהם במטרה.
אנחנו לא צריכים לעשות שום דבר.
3 ו -5 הם בסדר.
אנחנו לא צריכים לעשות שום דבר שם.
>> 5 ו -4, הם יצאו סדר, וכדי ש
צריך להחליף אותם ולהוסיף 1 לדלפק ההחלפה.
ועכשיו אנחנו כבר עברנו 5, האלמנט הגדול הבא,
בסופו של החלק לא ממוינים.
אז עכשיו אנחנו יכולים לקרוא לזה חלק מהחלק מסודרים.
>> עכשיו אתה מסתכל על מסך וכנראה יכול להגיד,
כאני יכול, כי המערך מיון עכשיו.
אבל אנחנו לא יכולים להוכיח את זה עדיין.
אין לנו ערובה שזה מסודרים.
אבל זה המקום שבו ההחלפה דלפק עומד להיכנס לפעולה.
>> אז אנחנו כבר הושלמו מעבר.
דלפק ההחלפה הוא 2.
אז אנחנו הולכים לחזור תהליך זה שוב,
לחזור עד דלפק ההחלפה הוא 0.
לאפס את מונה ההחלפה ל- 0.
אז אנחנו לאפס אותה.
>> עכשיו תסתכל על כל זוג סמוך.
זה כדי, 1 ו -2.
2 ו -3 בהזמנה.
3 ו -4 הם בסדר.
לכן בשלב זה, שם לב שהשלמנו מסתכל על כל זוג סמוך,
אבל דלפק ההחלפה הוא עדיין 0.
>> אם אין לנו לעבור כל אלמנטים, אז הם
חייב להיות בצו, על ידי כוחו של תהליך זה.
וכך יעילות של מיני, שמדעני המחשב שאנחנו אוהבים,
הוא עכשיו אנחנו יכולים להכריז כל המערך חייב
להיות מסודר, כי אנחנו לא צריך להחליף כל אלמנטים.
זה די נחמד.
>> אז מה במקרה הגרוע ביותר תרחיש עם מיון בועות?
במקרה הגרוע ביותר הוא המערך בסדר הפוכים לחלוטין,
ולכן אנחנו צריכים כל בועה של האלמנטים הגדולים כל
הדרך פני המערך.
ואנחנו ביעילות גם ל בועה כל האלמנטים הקטנים בחזרה
כל הדרך על פני המערך, מדי.
אז כל אחד מהאלמנטים n יש להעביר על פני כל האלמנטים n האחרים.
אז זה תרחיש המקרה הגרוע ביותר.
במקרה הטוב ביותר תרחיש אם כי, זה
שונה מעט מסוג הבחירה.
המערך הוא כבר מסודרים כשאנחנו הולכים ב.
אנחנו לא צריכים לעשות כל חילופים במעבר הראשון.
אז אולי צריך להסתכל בפחות אלמנטים, נכון?
אנחנו לא צריכים לחזור על זה לעבד מספר פעמים.
>> אז מה זה אומר?
אז מה התרחיש הגרוע ביותר למיון בועות, ומה
התרחיש הטוב ביותר למיון בועות?
האם אתה מניח שזה?
במקרה הגרוע ביותר אתה צריך לחזר בכל אלמנטי n n פעמים.
אז במקרה הגרוע ביותר הוא ריבוע n.
>> אם המערך הוא בצורה מושלמת מיון אם כי, אתה רק
צריך להסתכל על כל של האלמנטים פעם.
ואם דלפק ההחלפה הוא עדיין 0, אתה יכול להגיד מערך זה מסודרים.
וכך, במקרה הטוב, זה הוא למעשה טוב יותר מבחירה
sort-- זה אומגה של n.
>> אני דאג לויד.
זה CS50.