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