תוֹכֶן

• טבלת השוואה
• הגדרת סוג בועה
• הגדרת סוג הבחירה
• סיכום

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

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

1. טבלת השוואה
2. הגדרה
3. הבדלים עיקריים
4. סיכום

טבלת השוואה

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

הגדרת סוג בועה

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

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

הגדרת סוג הבחירה

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

במיון הבחירה, המערך הממוין והלא ממוין אינו משנה את הצורך וצורך סדר של n² (O (n²)) במורכבות הטובה ביותר ובמקרה הגרוע ביותר. מיון הבחירה מהיר יותר ממיון בועה.

1. במין הבועה, משווים בין כל רכיב לבין האלמנט הצמוד שלו ומחליפים במידת הצורך. מצד שני, מיון הבחירה עובד על ידי בחירת האלמנט והחלפת האלמנט הספציפי עם האלמנט האחרון. האלמנט שנבחר יכול להיות הגדול ביותר או הקטן ביותר, תלוי בסדר, כלומר עולה או יורד.
2. המורכבות במקרה הגרוע זהה בשני האלגוריתמים, כלומר O (n²), אך המורכבות הטובה ביותר היא שונה. מיון בועות לוקח סדר של זמן בעוד שמיון הבחירה צורך סדר של n² זמן.
3. מיון בועות הוא אלגוריתם יציב, לעומת זאת, סוג הבחירה אינו יציב.
4. אלגוריתם מיון הבחירה הוא מהיר ויעיל לעומת מיון בועות שהוא איטי ובלתי יעיל מאוד.

סיכום

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