מיון בועות - מדריך DS

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

כמה סרטי משימה בלתי אפשרית יש שם

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

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

בועה קצר משמש בעיקר כאשר -

המורכבות לא משנה
פשוט וקוד קצר מועדף

אַלגוֹרִיתְם

באלגוריתם המובא להלן, נניח arr הוא מערך של נ אלמנטים. ההנחה לְהַחלִיף הפונקציה באלגוריתם תחליף את הערכים של רכיבי מערך נתונים.

 begin BubbleSort(arr) for all array elements if arr[i] &gt; arr[i+1] swap(arr[i], arr[i+1]) end if end for return arr end BubbleSort

עבודה של אלגוריתם מיון בועה

עכשיו, בואו נראה את פעולתו של אלגוריתם מיון בועה.

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

תן לרכיבי המערך להיות -

מעבר ראשון

המיון יתחיל משני האלמנטים הראשונים. בואו להשוות אותם כדי לבדוק מה גדול יותר.

כאן, 32 גדול מ-13 (32 > 13), אז זה כבר ממוין. כעת, השווה בין 32 ל-26.

כאן, 26 קטן מ-36. לכן נדרשת החלפה. לאחר החלפת מערך חדש ייראה כך -

עכשיו, השוו בין 32 ו-35.

כאן, 35 גדול מ-32. לכן, אין צורך בהחלפה מכיוון שהם כבר ממוינים.

כעת, ההשוואה תהיה בין 35 ל-10.

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

כעת, עבור לאיטרציה השנייה.

מעבר שני

אותו תהליך יתבצע עבור איטרציה שנייה.

jfx מדריך Java

כאן, 10 קטן מ-32. לכן נדרשת החלפה. לאחר ההחלפה, המערך יהיה -

כעת, עבור לאיטרציה השלישית.

מעבר שלישי

אותו תהליך יבוצע עבור איטרציה שלישית.

כאן, 10 קטן מ-26. לכן נדרשת החלפה. לאחר ההחלפה, המערך יהיה -

כעת, עבור לאיטרציה הרביעית.

מעבר רביעי

באופן דומה, לאחר האיטרציה הרביעית, המערך יהיה -

לפיכך, אין צורך בהחלפה, ולכן המערך ממוין לחלוטין.

מורכבות מיון בועות

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

1. מורכבות זמן

מקרה	מורכבות זמן
המקרה הטוב ביותר	עַל)
מקרה ממוצע	עַל²)
במקרה הגרוע ביותר	עַל²)

עַל).

עַל²).

2. מורכבות החלל

מורכבות החלל	O(1)
יַצִיב	כן

מורכבות החלל של מיון בועות היא O(1). הסיבה לכך היא שבמיון בועות, נדרש משתנה נוסף להחלפה.
מורכבות החלל של מיון בועות אופטימלי היא O(2). הסיבה לכך היא שני משתנים נוספים נדרשים במיון בועות אופטימלי.

כעת, בואו נדון באלגוריתם מיון הבועות המאופטימלי.

אלגוריתם מיון בועות אופטימלי

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

כדי לפתור את זה, נוכל להשתמש במשתנה נוסף הוחלף. הוא מוגדר ל נָכוֹן אם יש צורך בהחלפה; אחרת, הוא מוגדר ל שֶׁקֶר.

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

שיטה זו תפחית את זמן הביצוע וגם תייעל את מיון הבועות.

אלגוריתם למיון בועות אופטימלי

 bubbleSort(array) n = length(array) repeat swapped = false for i = 1 to n - 1 if array[i - 1] &gt; array[i], then swap(array[i - 1], array[i]) swapped = true end if end for n = n - 1 until not swapped end bubbleSort

יישום מיון בועה

כעת, בואו נראה את התוכניות של Bubble ממוינות בשפות תכנות שונות.

ipconfig עבור אובונטו

תכנית: כתוב תוכנית ליישום מיון בועות בשפת C.

 #include void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { printf('%d ',a[i]); } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main () j,temp; a[5]="{" 10, 35, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" printf('before sorting array elements are - 
'); print(a, n); bubble(a, printf('
after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-13.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C++ language.</p> <pre> #include using namespace std; void print(int a[], int n) //function to print array elements { int i; for(i = 0; i <n; i++) { cout< <a[i]<<' '; } void bubble(int a[], int n) function to implement bubble sort i, j, temp; for(i="0;" i < n; for(j="i+1;" j j++) if(a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" main() j,temp; a[5]="{45," 1, 32, 13, 26}; n="sizeof(a)/sizeof(a[0]);" cout<<'before sorting array elements are - 
'; print(a, n); bubble(a, cout<<'
after return 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-14.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in C# language.</p> <pre> using System; public class Bubble { static void print (int[]a) //function to print array elements { int n = a.Length; int i; for (i = 0; i <n; 26 i++) { console.write (' ' + a[i]); } static void bubble (int[]a) function to implement sort int n="a.Length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main () int[] a="{" 45, 1, 32, 13, }; ('
 before sorting array elements are - 
'); print (a); console.writeline (); after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-15.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in Java.</p> <pre> public class Bubble { static void print (int a[]) //function to print array elements { int n = a.length; int i; for (i = 0; i <n; i++) { system.out.print(a[i] + ' '); } static void bubblesort (int a[]) function to implement bubble sort int n="a.length;" i, j, temp; for (i="0;" i < n; (j="i" 1; j j++) if (a[j] a[i]) temp="a[i];" a[i]="a[j];" a[j]="temp;" public main(string[] args) a[]="{35," 10, 31, 11, 26}; b1="new" bubble(); system.out.println('before sorting array elements are - b1.print(a); b1.bubblesort(a); system.out.println(); system.out.println('after pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-16.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in JavaScript.</p> <pre> var a = [35, 10, 31, 11, 26]; function print() //function to print array elements { for(i = 0; i <5; i++) { document.writeln(a[i]); } document.write('before sorting array elements are - ' + <br>&apos;); print(); for(i = 0; i <5; i++) { for (j="0;" j < 5; j++) if(a[i] a[j]) temp="a[i];" a[i]="a[j];" a[j]="temp;" } document.write(' <br> After sorting array elements are - &apos; + &apos; <br>&apos;); print(); </5;></5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-17.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in PHP.</p> <pre> <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo ' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;></pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-18.webp" alt="Bubble sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement bubble sort in python.</p> <pre> a = [35, 10, 31, 11, 26] print(&apos;Before sorting array elements are - &apos;) for i in a: print(i, end = &apos; &apos;) for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print('
after sorting array elements are - ') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:></pre></n;></pre></n;></pre></n;></pre></n;>

תְפוּקָה

תכנית: כתוב תוכנית ליישום מיון בועות ב-PHP.

 <?php $a = array(2, 45, 88, 11, 5); function printArray($a) { for($i = 0; $i < 5; $i++) { print_r($a[$i]); echo \' \'; } } echo \'Before sorting array elements are - <br>&apos;; printArray($a); for($i = 0; $i <5; $i++) { for ($j="0;" $j < 5; $j++) if($a[$i] $a[$j]) $temp="$a[$i];" $a[$i]="$a[$j];" $a[$j]="$temp;" } echo \' <br> After sorting array elements are - <br>&apos;; printArray($a); ?&gt; </5;>

תְפוּקָה

תכנית: כתוב תוכנית ליישום מיון בועות בפיתון.

 a = [35, 10, 31, 11, 26] print(&apos;Before sorting array elements are - &apos;) for i in a: print(i, end = &apos; &apos;) for i in range(0,len(a)): for j in range(i+1,len(a)): if a[j] <a[i]: temp="a[j]" a[j]="a[i]" a[i]="temp" print(\'
after sorting array elements are - \') for i in a: print(i, end=" " ) < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/52/bubble-sort-algorithm-19.webp" alt="Bubble sort Algorithm"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm&apos;s complexity, working, optimized form, and implementation in different programming languages.</p> <hr></a[i]:>