מיון בועות

שיעור 13 מתוך 26 בקורס מערכים ב-C++ של Coddy.

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

1. הכריזו על משתנה בשם counter ואתחלו אותו לערך 1. המשתנה counter שומר את מספר האיברים שמוינו.

2. צרו לולאת while עם תנאי שהאיטרציה תימשך כל עוד counter קטן מ-n.

int counter=1;
while(counter<n){
     
}

3. צרו לולאת for בתוך לולאת ה-while ואיטרצו בה מ-0 עד n-counter פעמים. זאת מכיוון שמספר האיברים השווה ל-counter כבר מוין, ואין צורך לבדוק אותם שוב.

int counter=1;
while(counter<n){
     for(int i=0;i<n-counter;i++){
     
     }
}

4. לאחר מכן השוו את האיבר ה-i לאיבר הבא אחריו, כלומר לאיבר ה-(i+1), ואם arr[i]>arr[i+1], החליפו ביניהם.

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

int counter=1;
while(counter<n){
  for(int i=0;i<n-counter;i++){
    if(arr[i]>arr[i+1]){
      int temp=arr[i];
      arr[i]=arr[i+1];
      arr[i+1]=temp;
    }
  }
  counter++;
}

ניתוח סיבוכיות זמן

אנחנו מריצים לולאת while n פעמים, ובכל לולאת while, לולאת for רצה כמעט n פעמים; לכן סיבוכיות הזמן היא O(n²).

כדי לראות איך האלגוריתם פועל בפועל, שלב אחר שלב.

המחשה של מיון בועות

אתגר

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

נסו בעצמכם

#include<iostream>
using namespace std;


int main(){
  
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
  cin>>arr[i];
}

//Code Here




return 0;

}