C Program to sort an array in ascending order using Bubble Sort

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:

  1. Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
  2. Compare arr[1] with arr[2]. If arr[1] > arr[2], swap them.
  3. 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:

  1. Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
  2. Compare arr[1] with arr[2]. If arr[1] > arr[2], swap them.
  3. 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:

  1. Compare arr[0] with arr[1]. If arr[0] > arr[1], swap them.
  2. Compare arr[1] with arr[2]. If arr[1] > arr[2], swap them.
  3. 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:

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:

Step 2: Compare  80 and 90. Since, 80 < 90, we do nothing:

Step 3: Compare  90 and 10. Since, 90 > 10, swap them:

Step 4: Compare  90 and 40. Since, 90 > 40, swap them:

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:

Step 2: Compare  80 and 10. Since, 80 > 10, swap them:

Step 3: Compare  80 and 40. Since, 80 > 40, swap them:

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:

Step 2: Compare  60 and 40. Since, 60 > 40, swap them:

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:

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:

Expected Output:

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:

Leave a Comment

%d bloggers like this: