Bubble Sort Algorithm With Examples [Latest]

Bubble Sort Algorithm is a sorting technique that assists with sorting the elements in a simple and efficient manner. Using bubble sort, elements can be sorted in ascending/descending order.

Bubble sort makes a comparison between the adjacent elements and swaps the elements if they are not in a defined order (either ascending or descending).

The Bubble Sort Algorithm

1. Initiate with the first element i.e. position = 0, and compare it with the next element of that particular array.
2. If the element to be compared is greater than the next element, then we need to swap the elements.
3. If the element to be compared is smaller than the next element, move to the next position to check for another element.
4. Repeat Step 1 – 3 until all the elements get sorted in an ascending or descending fashion.

Logic:

bubble_sort(input_array)
  for x <- 1 to index_of_last_element-1
    if left_element > right_element
      swap left_element and right_element
end bubble_sort

Working of Bubble Sort Algorithm

Let’s understand how the Bubble Sort algorithm works with the help of an example.

Our task is to sort the elements in ascending order.

So, we will start from the first element i.e. element at position 0 and compare it with the second (adjacent) element. If the first element is greater than the latter element, they are swapped.

Further, the same process is repeated until all the elements of the array are visited or traversed.

Note: In Bubble sort, if the array contains N elements, then it would perform N iterations.

Consider the elements 10, 7, 20, -1.

Iteration 1:

When i=0, the first element(10) is compared with the second element(7). Since 10 > 7, they are swapped and the array is updated.

Taking the process ahead i.e. i=1, the second element(10) is compared with the third element(20). Since 10 is not greater than 20, they retain their positions in the array.

When i=2, 20 is compared with -1. Since 20 > -1,they are swapped.

Iteration 2:

In the second iteration, 7 is compared with 10. Since 7 is not greater than 10, they retain their positions.

Further, 10 is compared with -1. As 10 > -1, they are swapped and the array is updated.

Then, 10 is swapped with 20. Since 10 is not greater than 20, they retain their positions in the array.

Iteration 3:

In the third iteration, 7 is compared with -1. Since 7 > -1, they are swapped and the array is updated.

Then, 7 is compared with 10. As 7 is not greater than 20, they retain their positions.

Further, 10 is compared with 20. Since 10 is not greater than 20, they retain their positions in the array.

Now as you all can witness, the array has been sorted. But, as mentioned above, for every n elements, bubble sort performs n iterations.

Therefore, in this example, for 4 elements it will perform 4 iterations.

Iteration 4:

Input: 10, 7, 20, -1

Output: -1, 7, 10, 20

Implementation of Bubble Sort in C

#include <stdio.h>
void bubble(int arr[], int size) {
    int temp=0;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - i - 1; j++) { // elements excluding the sorted ones
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main() {
  int arr[100], size;
  printf("Enter the count of elements of the array:n");
  scanf("%d", &size);
  printf("Enter the elements:n");
  for (int i = 0; i < size; i++)
    scanf("%d", &arr[i]);
  bubble(arr, size);
  printf("The sorted array:n");
  for (int i = 0; i < size; i++)
     printf("%dn", arr[i]);
  return 0;
}

Output:

Enter the count of elements of the array:
4
Enter the elements:
10
7
20
-1
The sorted array:
-1
7
10
20

Optimized Algorithm

As seen above, even after getting the sorted array at third iteration, bubble sort continues to iterate n times. These results provide poor efficiency of code.

Thus to improve the efficiency and optimize the code, let’s set a variable element on the inner loop to check whether the elements get swapped or not during a particular iteration process.

Thus, if at a particular iteration no swapping of elements occur, we can simply move out of the for loop instead of having to execute for all the iterations.

Let’s consider the above example.

Input: 10, 7, 20, -1

We will set a variable element, let’s say inspect to the inner loop.

As witnessed above, no elements get swapped in the fourth iteration. Thus, the value of inspect = 0 and we will break out from the loop.

Implementation of Optimized Bubble Sort Algorithm in C

Example:

#include <stdio.h>
void bubble(int arr[], int size) {
    int inspect,temp=0;
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - i - 1; j++) {
  // variable to monitor the swapping of elements in the inner loop
        inspect = 0;
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
         // set inspect = 1, if they function witness swap of elements
               inspect = 1;
   }
        }
// if the value of inspect continues to stay zero after all of the
// iterations of the inner loop, then move out of the loop
        if(!inspect)
        {
            break;
        }
    }
}
int main() {
  int arr[100], size;
  printf("Enter the count of elements of the array:n");
  scanf("%d", &size);
  printf("Enter the elements:n");
  for (int i = 0; i < size; i++)
    scanf("%d", &arr[i]);
  bubble(arr, size);
  printf("The sorted array:n");
  for (int i = 0; i < size; i++)
     printf("%dn", arr[i]);
  return 0;
}

Output:

Enter the count of elements of the array:
4
Enter the elements:
10
7
20
-1
The sorted array:
-1
7
10
20

Complexity Analysis of Bubble Sort

Best Case Time Complexity: O(n^2)

Space Complexity: O(1)

Conclusion

Thus, in this article, we have had a look at bubble sort and its working. Furthermore, we optimized the algorithm and learned its implementation in the C language.