[Powered by Google Translate] [מיון בועות] [JACKSON STEINKAMP אוניברסיטת הרווארד] [זה CS50. CS50TV] מיין בועה היא דוגמה לאלגוריתם מיון - כלומר, הליך המיון של אלמנטים ב בסדר עולה או יורד. לדוגמה, אם אתה רוצה למיין מערך מורכב של המספרים [3, 5, 2, 9], יישום נכון של מיון בועות יחזור מערך ממוין [2, 3, 5, 9] בסדר עולה. עכשיו, אני הולך להסביר בpseudocode כיצד האלגוריתם עובד. 

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

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

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

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

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

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

אחרי חזרות מ 'דרך כל המערך, האלמנטים מ 'הימניים ביותר מובטחים למיון למקום הנכון שלהם. אם אתה רוצה לראות את זה בעצמך, אנחנו יכולים לנסות אותו ברשימה לחלוטין אחורה [9, 6, 5, 3, 2]. לאחר מעבר אחד דרך כל הרשימה, [קול של כתיבה] [6, 9, 5, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9] האלמנט הימני ביותר הוא 9 במקום הראוי לו. לאחר 2 תמסורת, 6 יהיו 'בעבע למעלה "כדי מקום הימני ביותר 2. שני האלמנטים בימין - 6 ו 9 - יהיו במקומות הנכונים אחרי שני Pass-throughs 1. 

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

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

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

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

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

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