## Bubble Sort

Bubble sort is a simple method that sorts the elements of an array into either increasing or decreasing order. It works by comparing the adjacent elements and swapping them if they are out of order. Multiple passes through the array are necessary.

The following are the steps to sort an array of size `N`

in ascending order using bubble sort:

**Passthrough #1**:

- Compare
`arr[0]`

with`arr[1]`

. If`arr[0] > arr[1]`

, swap them. - Compare
`arr[1]`

with`arr[2]`

. If`arr[1] > arr[2]`

, swap them. - Finally, compare
`a[N-2]`

with`arr[N-1]`

, if`arr[N-2] > arr[N-1]`

, swap them.

This completes the first passthrough.

After, the first passthrough, the highest value in the array will be at the end.

**Passthrough #2**:

- Compare
`arr[0]`

with`arr[1]`

. If`arr[0] > arr[1]`

, swap them. - Compare
`arr[1]`

with`arr[2]`

. If`arr[1] > arr[2]`

, swap them. - Finally, compare
`a[N-3]`

with`arr[N-2]`

, if`arr[N-3] > arr[N-2]`

, swap them.

This completes the second passthrough. After, this passthrough, the second highest element will be at the second highest index in the array.

Note that in the final step of the second passthrough, we are not comparing the second last element i.e `a[N-2]`

with the last element i.e `arr[N-1]`

, this is because the last element is already in its correct position.

**Passthrough #3**:

- Compare
`arr[0]`

with`arr[1]`

. If`arr[0] > arr[1]`

, swap them. - Compare
`arr[1]`

with`arr[2]`

. If`arr[1] > arr[2]`

, swap them. - Finally, compare
`a[N-4]`

with`arr[N-3]`

, if`arr[N-4] > arr[N-3]`

, swap them.

This completes the third passthrough. After, this passthrough, the third highest element will be at the third highest index in the array.

In this way, we keep passing through the array. We stop when we encountered a passthrough that’s hasn’t swapped any elements.

Let’s take an example:

Suppose, we have an array `arr`

declared and initialized as:

1 2 |
#define SIZE 5 int arr[SIZE] = {80, 60, 90, 10, 40}; // unsorted array |

Here are the steps to sort this array in increasing order using bubble sort.

**Passthrough #1**:

Step 1: Compare `80`

and `60`

. Since, `80 > 60`

, swap them:

1 |
| 60 | 80 | 90 | 10 | 40 | |

Step 2: Compare `80`

and `90`

. Since, `80 < 90`

, we do nothing:

1 |
| 60 | 80 | 90 | 10 | 40 | |

Step 3: Compare `90`

and `10`

. Since, `90 > 10`

, swap them:

1 |
| 60 | 80 | 10 | 90 | 40 | |

Step 4: Compare `90`

and `40`

. Since, `90 > 40`

, swap them:

1 |
| 60 | 80 | 10 | 40 | 90 | |

This completes the first passthrough. The highest element i.e `90`

, is now at the end of the array. We have made three swaps in this passthrough. So, we need to perform another passthrough. Keep in mind that we keep passing through the array until we encounter a passthrough that hasn’t swapped any elements.

**Passthrough #2**:

Step 1: Compare `60`

and `80`

. Since, `60 < 80`

, we do nothing:

1 |
| 60 | 80 | 10 | 40 | 90 | |

Step 2: Compare `80`

and `10`

. Since, `80 > 10`

, swap them:

1 |
| 60 | 10 | 80 | 40 | 90 | |

Step 3: Compare `80`

and `40`

. Since, `80 > 40`

, swap them:

1 |
| 60 | 10 | 40 | 80 | 90 | |

This completes the second passthrough. The second highest element i.e `80`

, is now at the second highest index in the array. Also, note that we haven’t compared `80`

with `90`

. This is because the element `90`

is already in its correct position from passthrough #1.

We have made 2 swaps in this passthrough. So, we need to perform another one.

**Passthrough #3**:

Step 1: Compare `60`

and `10`

. Since, `60 > 10`

, swap them:

1 |
| 10 | 60 | 40 | 80 | 90 | |

Step 2: Compare `60`

and `40`

. Since, `60 > 40`

, swap them:

1 |
| 10 | 40 | 60 | 80 | 90 | |

This completes the third passthrough. The third highest element i.e `60`

, is now at the third highest index in the array. Also, note that we haven’t compared `60`

with `80`

. This is because the element `80`

is already in its correct position from passthrough #2.

We have made 2 swaps in this passthrough. So, we need to perform another one.

**Passthrough #4**:

Step 1: Compare `10`

and `40`

. Since, `10 < 40`

, we do nothing:

1 |
| 10 | 40 | 60 | 80 | 90 | |

This completes the fourth passthrough. We haven’t made any swaps in this passthrough. So, we need don’t need to perform another one. All the elements in the array are now sorted in ascending order.

## Bubble Sort C Program

The following is a C program which sorts the array in ascending order using Bubble sort algorithm:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
/**************************************************************** * Program to sort an array in ascending order using Bubble sort ****************************************************************/ #include<stdio.h> // include stdio.h library #define MAX 5 void bubble_sort(int arr[]); // function declaration int main(void) { int arr[MAX]; // input array for(int i = 0; i < MAX; i++) { printf("arr[%d] = ", i); scanf("%d", &arr[i]); } printf("\nUnsorted array: \n"); // print unsorted array for(int i = 0; i < MAX; i++) { printf("%d ", arr[i]); } // sort array bubble_sort(arr); printf("\n\nSorted array: \n"); // print sorted array for(int i = 0; i < MAX; i++) { printf("%d ", arr[i]); } return 0; // return 0 to operating system } /* * bubble_sort() takes an array and sorts it * in the ascending order */ void bubble_sort(int arr[]) { int tmp, // temporary variable to hold one of the values while swapping is_swapped; // variable to indicate whether we have made any swaps during the passthrough for(int i = 0; i < MAX; i++) { // re-initialize is_swapped to 0 after every passthrough is_swapped = 0; for(int j = 0; j < MAX - 1 - i; j++) { if(arr[j] > arr[j+1]) // compare adjacent elements { // swap adjacent elements tmp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tmp; // set is_swapped to 1, to indicate // that we have made at least one // swap during the passthrough is_swapped = 1; } } // if no swaps are made in the last passthrough, // exit the outer for loop if (!is_swapped) { break; } } } |

**Expected Output:**

1 2 3 4 5 6 7 8 9 10 11 12 |
Enter array: arr[0] = 80 arr[1] = 60 arr[2] = 90 arr[3] = 10 arr[4] = 40 Unsorted array: 80 60 90 10 40 Sorted array: 10 40 60 80 90 |

## How it works

All the work is done inside the `bubble_sort()`

function:

Here is how it works:

In lines 50 and 51, we have declared two variables: `tmp`

and `is_swapped`

. The `tmp`

variable will hold one of the values while swapping the elements and `is_swapped`

is used as a flag to indicate whether we have made any swaps during the passthrough or not.

In lines 53-81, we have an outer for loop, which runs until the array is not sorted.

The inner for loop in lines 58-72, swaps out of order elements during the passthrough. It runs from the beginning of the array and goes on until the index that hasn’t been sorted yet.

If we made at least one swap during the passthrough we set `is_swapped`

to `1`

(line 70).

At last, the if statement in lines 77-80, checks the value of `is_swapped`

to determine, whether to break out of the outer for loop or not. We break out of the outer for loop when we encountered a passthrough that’s hasn’t swapped any elements.

Keep in mind that the above function sorts the array in increasing order. To sort elements in decreasing order, simply change the if condition in line 60 from `arr[j] > arr[j+1]`

to `arr[j] < arr[j+1]`

.

**Recommended Reading:**