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

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

במאמר זה תוכלו ללמוד על פעולתו של אלגוריתם מיון הבועות, ה- pseudocode של מיון הבועות אלגוריתם, מורכבות הזמן והמרחב שלו, והטמעתו בשפות תכנות שונות כמו C ++, Python, C ו- JavaScript.

כיצד פועל אלגוריתם מיון הבועות?

מיון בועות הוא אלגוריתם המיון הפשוט ביותר שעובר שוב ושוב ברשימה, משווה אלמנטים סמוכים ומחליף אותם אם הם בסדר הלא נכון. ניתן להסביר מושג זה בצורה יעילה יותר בעזרת דוגמא. שקול מערך לא ממוין עם האלמנטים הבאים: {16, 12, 15, 13, 19}.

דוגמא:

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

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

בפסאוד-קוד, אלגוריתם מיון הבועות יכול לבוא לידי ביטוי כ:

bubbleSort (Arr [], גודל)
// לולאה כדי לגשת לכל אלמנט מערך
עבור i = 0 לגודל -1 לעשות:
// לולאה להשוואת אלמנטים במערך
עבור j = 0 עד גודל-i-1 לעשות:
// השווה את האלמנטים הסמוכים





instagram viewer


אם Arr [j]> Arr [j + 1] אז
// החלף אותם
החלף (Arr [j], Arr [j + 1])
לסיים אם
סוף ל
סוף ל
סוֹף

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

לפיכך, הפסאוד-קוד של אלגוריתם מיון הבועות המותאם יכול לבוא לידי ביטוי כ:

bubbleSort (Arr [], גודל)
// לולאה כדי לגשת לכל אלמנט מערך
עבור i = 0 לגודל -1 לעשות:
// לבדוק אם מתבצעת החלפה
החלפה = שקר
// לולאה להשוואת אלמנטים במערך
עבור j = 0 עד גודל-i-1 לעשות:
// השווה את האלמנטים הסמוכים
אם Arr [j]> Arr [j + 1] אז
// החלף אותם
החלף (Arr [j], Arr [j + 1])
התחלף = נכון
לסיים אם
סוף ל
// אם לא הוחלפו אלמנטים זה אומר שהמערך ממוין כעת, אז שבור את הלולאה.
אם (לא מוחלף) אז
לשבור
לסיים אם
סוף ל
סוֹף

מורכבות זמן ומרחב עזר של אלגוריתם מיון הבועות

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

מורכבות הזמן הטובה ביותר של אלגוריתם מיון הבועות היא O (n). זה קורה כאשר המערך כבר ממוין.

קָשׁוּר: מהי סימון ביג-או?

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

שטח העזר הנדרש לאלגוריתם מיון הבועות הוא O (1).

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

להלן הטמעת C ++ של אלגוריתם מיון הבועות:

// יישום C ++ של ה-
// אלגוריתם מיון בועות מותאם
#לִכלוֹל 
באמצעות std namespace;
// פונקציה לביצוע מיון בועות
void bubbleSort (int arr [], size int) {
// לולאה כדי לגשת לכל אלמנט במערך
עבור (int i = 0; אני // משתנה כדי לבדוק אם מתרחשת החלפה
החלפת בול = שקר;
// לולאה להשוואה בין שני אלמנטים סמוכים של המערך
עבור (int j = 0; j // השוואת שני אלמנטים מערכים סמוכים
אם (arr [j]> arr [j + 1]) {
// החלף את שני האלמנטים אם הם
// לא בסדר נכון
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
התחלף = נכון;
}
}
// אם לא הוחלפו אלמנטים זה אומר שהמערך ממוין עכשיו,
// ואז לשבור את הלולאה.
אם (מוחלף == false) {
לשבור;
}
}
}
// מדפיס את מרכיבי המערך
בטל printArray (int arr [], גודל int) {
עבור (int i = 0; אני cout << arr [i] << "";
}
cout << endl;
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// מציאת אורך המערך
int גודל = sizeof (arr) / sizeof (arr [0]);
// הדפסת המערך הלא ממוין הנתון
cout << "מערך לא ממוין:" << endl;
printArray (arr, גודל);
// פונקציית שיחת bubbleSort ()
bubbleSort (arr, גודל);
// הדפסת המערך הממוין
cout << "מערך ממוין בסדר עולה:" << endl;
printArray (arr, גודל);
החזר 0;
}

תְפוּקָה:

מערך לא ממוין: 
16 12 15 13 19 
מערך ממוין בסדר עולה:
12 13 15 16 19

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

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

# יישום פייתון של
# אלגוריתם מיון בועות אופטימלי
# פונקציה לביצוע מיון בועות
def bubbleSort (arr, גודל):
# לולאה כדי לגשת לכל רכיב ברשימה
עבור אני בטווח (גודל -1):
משתנה כדי לבדוק אם מתרחשת החלפה
התחלף = שקר
לולאה # להשוואת שני אלמנטים סמוכים ברשימה
עבור j בטווח (גודל-i-1):
# השוואה בין שני רכיבי רשימה סמוכים
אם arr [j]> arr [j + 1]:
temp = arr [j]
arr [j] = arr [j + 1]
arr [j + 1] = טמפ '
החלף = נכון
# אם לא הוחלפו רכיבים זה אומר שהרשימה ממוינת כעת,
# ואז לשבור את הלולאה.
אם הוחלף == שקר:
לשבור
# מדפיס את רכיבי הרשימה
def printArray (arr):
לאלמנט arr:
הדפס (אלמנט, סוף = "")
הדפס("")
arr = [16, 12, 15, 13, 19]
# מציאת אורך הרשימה
גודל = len (arr)
# הדפסת הרשימה הלא ממוינת הנתונה
הדפס ("רשימה לא ממוינת:")
printArray (arr)
# פונקציית שיחת bubbleSort ()
bubbleSort (arr, גודל)
# הדפסת הרשימה הממוינת
הדפס ("רשימה ממוינת בסדר עולה:")
printArray (arr)

תְפוּקָה:

רשימה לא ממוינת:
16 12 15 13 19 
רשימה ממוינת בסדר עולה:
12 13 15 16 19

קָשׁוּר: כיצד להשתמש עבור לולאות בפייתון

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

להלן יישום C של אלגוריתם Bubble Sort:

// יישום C
// אלגוריתם מיון בועות מותאם
#לִכלוֹל 
#לִכלוֹל 
// פונקציה לביצוע מיון בועות
void bubbleSort (int arr [], size int) {
// לולאה כדי לגשת לכל אלמנט במערך
עבור (int i = 0; אני // משתנה כדי לבדוק אם מתרחשת החלפה
החלפת בול = שקר;
// לולאה להשוואה בין שני אלמנטים סמוכים של המערך
עבור (int j = 0; j // השוואת שני אלמנטים מערכים סמוכים
אם (arr [j]> arr [j + 1]) {
// החלף את שני האלמנטים אם הם
// לא בסדר נכון
int temp = arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
התחלף = נכון;
}
}
// אם לא הוחלפו אלמנטים זה אומר שהמערך ממוין עכשיו,
// ואז לשבור את הלולאה.
אם (מוחלף == false) {
לשבור;
}
}
}
// מדפיס את מרכיבי המערך
בטל printArray (int arr [], גודל int) {
עבור (int i = 0; אני printf ("% d", arr [i]);
}
printf ("\ ⁠n");
}
int main () {
int arr [] = {16, 12, 15, 13, 19};
// מציאת אורך המערך
int גודל = sizeof (arr) / sizeof (arr [0]);
// הדפסת המערך הלא ממוין הנתון
printf ("מערך לא ממוין: \ ⁠n");
printArray (arr, גודל);
// פונקציית שיחת bubbleSort ()
bubbleSort (arr, גודל);
// הדפסת המערך הממוין
printf ("מערך ממוין בסדר עולה: \ ⁠n");
printArray (arr, גודל);
החזר 0;
}

תְפוּקָה:

מערך לא ממוין: 
16 12 15 13 19 
מערך ממוין בסדר עולה: 
12 13 15 16 19

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

להלן הטמעת JavaScript של אלגוריתם Bubble Sort:

// יישום JavaScript של
// אלגוריתם מיון בועות מותאם
// פונקציה לביצוע מיון בועות
function bubbleSort (arr, size) {
// לולאה כדי לגשת לכל אלמנט במערך
עבור (תן i = 0; אני// משתנה כדי לבדוק אם מתרחשת החלפה
var swapped = false;
// לולאה להשוואה בין שני אלמנטים סמוכים של המערך
עבור (תן j = 0; j// השוואת שני אלמנטים מערכים סמוכים
אם (arr [j]> arr [j + 1]) {
// החלף את שני האלמנטים אם הם
// לא בסדר נכון
תן לטמפ '= arr [j];
arr [j] = arr [j + 1];
arr [j + 1] = temp;
התחלף = נכון;
}
// אם לא הוחלפו אלמנטים זה אומר שהמערך ממוין עכשיו,
// ואז לשבור את הלולאה.
אם (מוחלף == false) {
לשבור;
}
}
}
}
// מדפיס את מרכיבי המערך
function printArray (arr, גודל) {
עבור (תן i = 0; אניdocument.write (arr [i] + "");
}
document.write ("
")
}
var arr = [16, 12, 15, 13, 19];
// מציאת אורך המערך
גודל var = אורך arr.
// הדפסת המערך הלא ממוין הנתון
document.write ("מערך לא ממוין: 
");
printArray (arr, גודל);
// פונקציית שיחת bubbleSort ()
bubbleSort (arr, גודל);
// הדפסת המערך הממוין
document.write ("מערך ממוין בסדר עולה: 
");
printArray (arr, גודל);

תְפוּקָה:

מערך לא ממוין:
16 12 15 13 19
מערך ממוין בסדר עולה:
12 15 13 16 19

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

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

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

כיצד להתחיל עם פייתון באמצעות סקריפט "שלום עולם"

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

קרא הבא

על הסופר