מיון בועות לעומת הכנסה מיון
מיון בועה הוא אלגוריתם מיון הפועל על ידי מעבר על הרשימה כדי להיות ממוינת שוב ושוב תוך השוואת זוגות של אלמנטים צמודים. אם זוג אלמנטים בסדר שגוי הם מוחלפים כדי למקם אותם בסדר הנכון. מעבר זה חוזר על עצמו עד שאין צורך בהחלפות נוספות. מיון הכנסה הוא גם אלגוריתם מיון, הפועל על ידי הכנסת אלמנט ברשימת הקלט למיקום הנכון ברשימה שכבר ממוינת. תהליך זה מיושם שוב ושוב עד שהרשימה ממוינת.
מהו מיון בועה?
מיון בועות הוא אלגוריתם מיון הפועל על ידי מעבר על הרשימה כדי להיות ממוינת שוב ושוב תוך השוואת זוגות של אלמנטים סמוכים. אם זוג אלמנטים בסדר שגוי הם מוחלפים כדי למקם אותם בסדר הנכון. מעבר זה חוזר על עצמו עד שלא נדרשים החלפות נוספות (מה שאומר שהרשימה ממוינת). מכיוון שהאלמנטים הקטנים יותר ברשימה מגיעים לראש כשבועה עולה על פני השטח, הוא מקבל את השם מיון בועות. מיון בועות הוא אלגוריתם מיון פשוט מאוד אך יש לו מורכבות זמן ממוצעת של מקרה של O(n2) בעת מיון רשימה עם n אלמנטים. בשל כך, מיון בועות אינו מתאים למיון רשימות עם מספר רב של אלמנטים. אבל בשל הפשטות שלו, מיון בועות נלמד במהלך היכרות עם אלגוריתמים.
מהו מיון הכנסה?
Insertion sort הוא אלגוריתם מיון נוסף, הפועל על ידי הכנסת אלמנט ברשימת הקלט למיקום הנכון ברשימה (שכבר ממוינת).תהליך זה מיושם שוב ושוב עד שהרשימה ממוינת. במיון ההכנסה, המיון מתבצע במקום. לכן לאחר האיטרציה ה-ith של האלגוריתם, ערכי ה-i+1 הראשונים ברשימה ימוינו ושאר הרשימה לא ממוינת. בכל איטרציה, האלמנט הראשון בחלק הלא ממוין של הרשימה יילקח ויוכנס למקום הנכון בחלק הממוין של הרשימה. למיון ההכנסה יש מורכבות זמן ממוצעת של מקרה של O(n2). בשל כך, מיון הכנסה אינו מתאים גם למיון רשימות גדולות.
מה ההבדל בין מיון בועות למיון הכנסה?
למרות שגם לאלגוריתם מיון הבועות וגם לאלגוריתם של מיון הבועות יש סיבוכיות ממוצעת של זמן מקרה של O(n2), מיון הבועות מקבל כמעט כל הזמן ביצועים טובים יותר על ידי מיון ההכנסה. זה נובע ממספר ההחלפות הדרושים לשני האלגוריתמים (מיון בועות צריך יותר החלפות). אבל בשל הפשטות של מיון בועות, גודל הקוד שלה קטן מאוד.כמו כן, יש וריאנט של מיון הכנסה שנקרא מיון מעטפת, שיש לו מורכבות זמן של O(n3/2), מה שיאפשר להשתמש בו באופן מעשי. יתר על כן, מיון הוספה יעיל מאוד למיון רשימות "כמעט ממוינות", בהשוואה למיון הבועות.
