Bubble Sort הוא אלגוריתם מיון פשוט שעובר שוב ושוב ברשימה, משווה אלמנטים סמוכים ומחליף אותם אם הם בסדר הלא נכון. זה נקרא 'Bubble Sort' מכיוון שאלמנטים קטנים יותר 'בועלים' לראש הרשימה. אמנם לא אלגוריתם המיון היעיל ביותר, אך קל להבנה ויישום, מה שהופך אותו לנקודת התחלה טובה ללמידה על אלגוריתמי מיון. במאמר זה נעמיק במושג Bubble Sort, נספק מימוש של Python עם פלט, ונדון במורכבות הזמן של האלגוריתם.
הבנת מיון בועות
הרעיון הבסיסי מאחורי Bubble Sort הוא לחזור על הרשימה מספר פעמים, להשוות אלמנטים סמוכים ולהחליף אותם אם הם לא בסדר. התהליך נמשך עד שאין צורך בהחלפות נוספות, מה שמצביע על כך שהרשימה ממוינת כעת. האלגוריתם מקבל את שמו מהאופן שבו אלמנטים קטנים יותר עוברים בהדרגה לראש הרשימה, בדומה לבועות שעולות לפני השטח.
בואו נפרק את השלבים של אלגוריתם מיון הבועות:
עבור לולאה java
- חזור על הרשימה: התחל מתחילת הרשימה והשווה כל זוג אלמנטים סמוכים.
- השוו והחליפו: אם האלמנטים נמצאים בסדר שגוי, החליפו אותם. זה מבטיח שהאלמנט הגדול יותר 'בעבוע למעלה' והקטן ינוע למטה.
- המשך איטרציה: חזור על התהליך עבור כל זוג אלמנטים סמוכים עד שתגיע לסוף הרשימה.
- חזור עד למיון: המשך לחזור על הרשימה עד שאין צורך בהחלפות נוספות. בשלב זה, הרשימה ממוינת.
אמנם מיון בועות הוא פשוט להבנה, אבל זה לא אלגוריתם המיון היעיל ביותר, במיוחד עבור מערכי נתונים גדולים. מורכבות הזמן שלו היא O(n^2) במקרה הגרוע, כאשר 'n' הוא מספר האלמנטים ברשימה. מורכבות הזמן הריבועית הזו הופכת אותו לפחות מתאים למערכי נתונים גדולים בהשוואה לאלגוריתמי מיון מתקדמים יותר.
יישום Python של Bubble Sort
כעת, בואו ליישם מיון בועות ב-Python ונצפה בהתנהגות שלה עם רשימה לדוגמה:
def bubble_sort(arr): n = len(arr) # Traverse through all array elements for i in range(n): # Last i elements are already sorted, so we don't need to check them for j in range(0, n-i-1): # Swap if the element found is greater than the next element if arr[j] > arr[j+1]: arr[j], arr[j+1] = arr[j+1], arr[j] # Example usage if __name__ == '__main__': # Sample list to be sorted sample_list = [64, 34, 25, 12, 22, 11, 90] # Display the original list print('Original List:', sample_list) # Apply Bubble Sort bubble_sort(sample_list) # Display the sorted list print('Sorted List:', sample_list)
ביישום זה, הפונקציה bubble_sort לוקחת רשימה (arr) כפרמטר שלה וממיינת אותה במקום. הלולאה המקוננת משווה אלמנטים סמוכים ומחליפה אותם אם הם בסדר הלא נכון. הלולאה החיצונית מבטיחה שהתהליך חוזר על עצמו עד שהרשימה כולה ממוינת.
פלט והסבר
בואו נריץ את קוד Python שסופק עם רשימת הדוגמאות ונצפה בפלט:
Original List: [64, 34, 25, 12, 22, 11, 90] Sorted List: [11, 12, 22, 25, 34, 64, 90]
כאן, הרשימה המקורית [64, 34, 25, 12, 22, 11, 90] ממוינת בהצלחה באמצעות אלגוריתם מיון הבועה, וכתוצאה מכך הרשימה הממוינת [11, 12, 22, 25, 34, 64, 90].
מה זה 25 מתוך 100
האלגוריתם חוזר על הרשימה מספר פעמים, משווה ומחליף אלמנטים עד שהרשימה כולה ממוינת. בכל מעבר, האלמנט הגדול ביותר שלא ממוין 'בועע' למיקומו הנכון. תהליך זה נמשך עד שאין צורך בהחלפות נוספות, מה שמצביע על כך שהרשימה ממוינת במלואה.
בעוד Bubble Sort ממיין בהצלחה את הרשימה, חשוב לציין שמורכבות הזמן שלה הופכת אותה לפחות יעילה עבור מערכי נתונים גדולים בהשוואה לאלגוריתמי מיון אחרים כמו מיזוג מיון או מיון מהיר.
מורכבות הזמן של מיון בועות
מחולל מספרים אקראיים ב-c
הבנת מורכבות הזמן של אלגוריתם חיונית להערכת יעילותו, במיוחד כאשר עוסקים במערכי נתונים גדולים. מורכבות הזמן של Bubble Sort היא O(n^2) במקרה הגרוע, כאשר 'n' הוא מספר האלמנטים ברשימה.
בואו נפרק את ניתוח מורכבות הזמן:
- הלולאה החיצונית פועלת עבור 'n' איטרציות, כאשר 'n' הוא מספר האלמנטים ברשימה.
- הלולאה הפנימית פועלת גם עבור 'n' איטרציות במקרה הגרוע. עם זאת, ככל שהאלגוריתם מתקדם, מספר האיטרציות בלולאה הפנימית פוחת, כאשר האלמנט הגדול ביותר שלא ממוין מוצב במיקום הנכון שלו בכל מעבר.
- במקרה הגרוע, מספר ההשוואות וההחלפות הוא פרופורציונלי לריבוע של מספר האלמנטים ברשימה, וכתוצאה מכך מורכבות הזמן O(n^2). זה הופך את מיון הבועה לבלתי יעיל עבור מערכי נתונים גדולים, ואלגוריתמי מיון מתקדמים יותר עם מורכבות זמן טובה יותר מועדפים לרוב ביישומים בעולם האמיתי.
סיכום
במאמר זה חקרנו את הרעיון של Bubble Sort, אלגוריתם מיון פשוט המשווה ומחליף שוב ושוב אלמנטים סמוכים עד שהרשימה כולה ממוינת. סיפקנו מימוש Python של Bubble Sort, הרצנו אותו עם רשימה לדוגמה וניתחנו את הפלט. בנוסף, דנו במורכבות הזמן של Bubble Sort, והדגשנו את מורכבות הזמן O(n^2) במקרה הגרוע ביותר ואת ההשלכות שלה על היעילות.