Let's learn C

מיון בועות

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

מיון זה עובד בצורה הבאה:

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

תהליך המיון:

נראה תהליך זה על ידי דוגמה על המערך הבא:

נבצע עליו מיון בועות.
ראשית, נשווה בין הערכים בתא 0 (1) לתא 1 (5).

בגלל ש 5 גדול יותר מ 1 לא מתבצעת החלפה והמערך נשאר ללא שינוי.

נשווה בין הערכים בתא 1 (5) לתא 2 (2).

בגלל ש 5 גדול מ 2 מתבצעת החלפה והמערך יראה כך:

נשווה בין הערכים בתא 2 (5) לתא 3 (3).

בגלל ש 5 גדול מ 3 מתבצעת החלפה והמערך יראה כך:

נשווה בין הערכים בתא 3 (5) לתא 4 (12).

בגלל ש12 גדול מ 5 לא מתבצעת החלפה והמערך נשאר ללא שינוי.

נשווה בין הערכים בתא 4 (12) לתא 5 (25).

בגלל ש25 גדול מ 12 לא מתבצעת החלפה והמערך נשאר ללא שינוי.

נשווה בין הערכים בתא 5 (25) לתא 6 (9).

בגלל ש25 גדול מ 9 מתבצעת החלפה והמערך יראה כך:

כעת, אנו רואים כי האיבר הגדול ביותר נמצא בתא האחרון (תא 6), אך אנו לא יודעים אם המערך ממוין.
לכן, נתחיל שוב את סבב הבדיקות ללא התא השישי, מכיוון שהוא נמצא במקומו.
כלומר, נבצע כעת את ההשוואות של המערך מתא 0 עד תא 5.
לאחר שנסיים את הסבב השני אנו נדע כי שני הערכים האחרונים ממוינים.
נמשיך כך עד שהמערך יהיה ממוין.

לאחר הסבב השני המערך שלנו יראה כך:

כעת ניתן לראות שהמערך ממוין ואין צורך להמשיך בבדיקות.

דוגמה לקוד של מיון בועות:

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

CODE:


#include <stdio.h>

void swap(int *first,int *second) //swap between two variables.
{
  int temp;
  temp = *first;
  *first = *second;
  *second = temp;
} 

void bubble_sort(int *array,int array_size)
{
  int i ,j;
  for(i=0;i<array_size-1;i++)//in each loop the size of the array is decreased by 1
  {
    for(j=0;j<array_size -(i+1);j++)
    {
      if(array[j] > array[j+1])
      {
        swap(array + j , array + j +1);
      }
    }
  }
}