February 9, 2023

Lets explain Bubble sort by illustrating tow specific examples involving steps where smaller numbers bubbles to first and when larger numbers bubbles to last.

Number list to sort: 2   5   3   0   6   1

Case 1: Smaller numbers bubbles to first

Step 1:    0  5  3  2  6  1

Step 2:   0  3  5  2  6  1

0  2  5  3  6  1

0  1  5  3  6  2

Step 3:   0  1  3  5  6  2

0  1  2  5  6  3

Step 4:    0  1  2  3  6  5

Step 5:    0  1  2  3  5  6

Case 2: Larger numbers bubbles to first

Step 1:   2  3  5  0  6  1

2  3  0  5  6  1

2  3  0  5  1  6

Step 2:   2  0 3  5  1  6

2  0  3  1  5  6

Step 3:  0  2  3  1  5  6

0  2  1  3  5  6

Step 4: 0  1  2  3  5  6

C Algorithm for Bubble Sort (smaller number bubbles to first)

/* n gives no. of integers */
/* X[] stores integers */

for(i = 0; i < n; i++){     
     for(j = i + 1; j < n; j++){
          if(X[j] < X[i]){              
              temp = X[j];
              X[j] = X[i];
              X[i] = temp;
          }
     }
}

Order of above sorting algorithm: Order = (n-1)n = O(n2)

C Algorithm for Bubble Sort (larger numbers bubbles to last)

/* n gives no. of integers */
/* X[] stores integers */

for(i = 0; i < n; i++){     
     for(j = i+1; j < n; j++){
          if(X[i] > X[j]){              
              temp = X[j];
              X[j] = X[i];
              X[i] = temp;
          }
     }
}

Order of above sorting algorithm: Order = (n-1)n = O(n2)