מיון בועות בג'אווה
1. הקדמה
במאמר מהיר זה נחקור את אלגוריתם מיון הבועות בפירוט, תוך התמקדות ביישום Java.
זהו אחד מאלגוריתמי המיון הפשוטים ביותר; הרעיון המרכזי הואהמשך להחליף אלמנטים סמוכים של מערך אם הם בסדר שגוי עד למיון האוסף.
פריטים קטנים "מבעבעים" בראש הרשימה כשאנחנו מחזירים את מבנה הנתונים. לפיכך, הטכניקה מכונה מיון בועות.
מכיוון שהמיון מתבצע על ידי החלפה, אנו יכולים לומר שהוא מבצע מיון במקום.
גַם, אם לשני אלמנטים יש אותם ערכים, הנתונים המתקבלים ישמרו על הסדר שלהם - מה שהופך אותו למיון יציב.
2. מתודולוגיה
כפי שצוין קודם לכן, כדי למיין מערך, אנו חוזרים דרכו תוך השוואת אלמנטים סמוכים ומחליפים אותם במידת הצורך. למערך בגודל נ, אנחנו מופיעים n-1 איטרציות כאלה.
בואו ניקח דוגמה להבנת המתודולוגיה. ברצוננו למיין את המערך בסדר עולה:
4 2 1 6 3 5
אנו מתחילים את האיטרציה הראשונה בהשוואה בין 4 ו -2; הם בהחלט לא בסדר הנכון. החלפה תביא:
[2 4] 1 6 3 5
עכשיו, חוזר על אותו הדבר במשך 4 ו -1:
2 [14] 6 3 5
אנחנו ממשיכים לעשות את זה עד הסוף:
2 1 [4 6] 3 5
2 1 4 [36] 5
2 1 4 3 [5 6]
כפי שאנו רואים, בסוף האיטרציה הראשונה, קיבלנו את האלמנט האחרון במקומו הראוי. כעת, כל שעלינו לעשות הוא לחזור על אותו הליך באיטרציות נוספות. אלא שאנחנו לא כוללים את האלמנטים שכבר ממוינים.
באיטרציה השנייה, נחזור דרך כל המערך למעט האלמנט האחרון. באופן דומה, עבור איטרציה שלישית, אנו משמיטים את שני האלמנטים האחרונים. באופן כללי, עבור איטרציה ח 'אנו חוזרים על מדד עד n-k (לא נכלל). בסוף n-1 איטרציות, נקבל את המערך הממוין.
עכשיו כשאתה מבין את הטכניקה, בואו נצלול לתוך היישום.
3. יישום
בואו לממש את המיון עבור מערך הדוגמאות עליו דנו באמצעות גישת Java 8:
בטל bubbleSort (מספר שלם [] arr) {int n = arrlength; IntStream.range (0, n - 1) .flatMap (i -> IntStream.range (1, n - i)) .forEach (j -> {if (arr [j - 1]> arr [j]) {int temp = arr [j]; arr [j] = arr [j - 1]; arr [j - 1] = temp;}}); }ומבחן JUnit מהיר לאלגוריתם:
@ מבחן ציבורי בטל כאשרSortedWithBubbleSort_thenGetSortedArray () {מערך שלם [] = {2, 1, 4, 6, 3, 5}; מספר שלם [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = BubbleSort חדש (); bubbleSort.bubbleSort (מערך); assertArrayEquals (array, sortedArray); }4. מורכבות ואופטימיזציה
כמו שאנו יכולים לראות, לממוצע ולמקרה הגרוע ביותר, מורכבות הזמן היאO (n ^ 2).
בנוסף, מורכבות החלל, אפילו בתרחיש הגרוע ביותר, הוא O (1) מכיוון שאלגוריתם של מיון בועות אינו דורש זיכרון נוסף והמיון מתבצע במערך המקורי.
על ידי ניתוח הפתרון בזהירות, אנו יכולים לראות זאת אם לא נמצאות החלפות באיטרציה, איננו צריכים לחזור ולהמשיך.
במקרה של הדוגמה שנדונה קודם לכן, לאחר החזרה השנייה, אנו מקבלים:
1 2 3 4 5 6
בתבנית השלישית, איננו צריכים להחליף שום זוג אלמנטים סמוכים. כדי שנוכל לדלג על כל החזרות שנותרו.
במקרה של מערך ממוין, לא יהיה צורך בהחלפה באיטרציה הראשונה עצמה - מה שאומר שאנחנו יכולים לעצור את הביצוע. זה התרחיש הטוב ביותר מורכבות הזמן של האלגוריתם היא O (n).
עכשיו, בואו נשתמש בפיתרון המותאם.
חלל ציבורי optimizedBubbleSort (מספר שלם [] arr) {int i = 0, n = arrllength; החלפה בוליאנית Needed = true; בעוד (i <n - 1 && swapNeeded) {swapNeeded = false; עבור (int j = 1; j arr [j]) {int temp = arr [j - 1]; arr [j - 1] = arr [j]; arr [j] = temp; swapNeeded = נכון; }} אם (! swapNeeded) {break; } i ++; }}בואו לבדוק את הפלט לאלגוריתם המותאם:
@Test הציבור בטל givenIntegerArray_whenSortedWithOptimizedBubbleSort_thenGetSortedArray () {מערך שלם [] = {2, 1, 4, 6, 3, 5}; מספר שלם [] sortedArray = {1, 2, 3, 4, 5, 6}; BubbleSort bubbleSort = BubbleSort חדש (); bubbleSort.optimizedBubbleSort (מערך); assertArrayEquals (array, sortedArray); }5. מסקנה
במדריך זה ראינו כיצד Bubble Sort פועל, והטמעתו ב- Java. ראינו גם כיצד ניתן לייעל את זה. לסיכום, זהו אלגוריתם יציב במקום, עם מורכבות זמן:
- המקרה הגרוע והממוצע: O (n * n), כאשר המערך בסדר הפוך
- המקרה הטוב ביותר: O (n), כאשר המערך כבר ממוין
האלגוריתם פופולרי בגרפיקה ממוחשבת, בשל יכולתו לאתר כמה שגיאות קטנות במיון. לדוגמא, במערך כמעט ממוין, יש להחליף רק שני אלמנטים כדי לקבל מערך ממוין לחלוטין. מיון בועות יכול לתקן שגיאות כאלה (כלומר למיין מערך זה) בזמן ליניארי.
כמו תמיד, ניתן למצוא את הקוד ליישום האלגוריתם הזה ב- GitHub.
