Bubble sort in Data structure is the most simple and basic sorting algorithm technique in Data structure. It is used for sorting element in ascending or descending order.

Bubble Sort Technique

What is bubble sort?: The main idea behind the bubble sort algorithm is to compare the adjacent elements repeatedly and swap their positions if they were in the wrong order.

In this technique we compare the first element with preceding element if the number next to that is small then we perform swapping so that the smaller number become a first, Then again go for next preceding number this process will continue till end of iteration and we perform N number of iteration to a sorting element, at last, we will get sorted list.

Using this technique at first iteration we bubble up either the first or last element while arranging in ascending or descending order respectively.

Bubble Sort Example:

Consider following a set of numbers and perform bubble sort.

Iteration 1:

Bubble Sort

Compare 70 with 50, 70 > 50, So swap 70 and 50.

Compare 70 with 60, 70 > 60, So swap 70 and 60.

Compare 70 with 20, 70 > 20 so swap 70 and 20.

Compare 70 with 10, 70 > 10 so swap 70 and 10.

After iteration 1 we got 70 at its position.

Iteration 2:

Now start with the first element again.

Compare 50 with 60, 50 > 60 so don’t change anything move forward.

Compare 60 with 20, 60 > 20 so swap 60 and 20.

Compare 60 with 10, 60 > 10 so swap 60 and 10.

After this iteration, we get 60 at its position.

Iteration 3:

Compare 50 with 20, 50 > 20 so swap 50 and 20.

Compare 50 with 10, 50 > 10 so swap 50 and 10.

 

In this iteration, we get 50 at its position.

Iteration 4:

Compare 20 with 10, 20 > 10 so swap 20 and 10.

After this iteration, we got our all elements are arranged in ascending order.

Sorted array – 10 20 50 60 70

Passes(iteration) required = N-1 = 5-1 =4

Bubble sort algorithm

  1. Start
  2. declare variables n, i=0
  3. Input n=5
  4. Input array array[5]={10,2,5,3,1};
  5. Traverse the array
  6. Compare element a[i]>a[i+i]
  7. if yes, swap elements
  8. else continue
  9. print sorted an array
  10. End

Flowchart for Bubble sort

Flowchart for Bubble sort

Bubble sort program

#include <stdio.h>
 
int main()
{
  int array[100], n, c, d, swap;
 
  printf("Enter number of elements\n");
  scanf("%d", &n);
 
  printf("Enter %d integers\n", n);
 
  for (c = 0; c < n; c++)
    scanf("%d", &array[c]);
 
  for (c = 0 ; c < n - 1; c++)
  {
    for (d = 0 ; d < n - c - 1; d++)
    {
      if (array[d] > array[d+1]) /* For decreasing order use < */
      {
        swap       = array[d];
        array[d]   = array[d+1];
        array[d+1] = swap;
      }
    }
  }
 
  printf("Sorted list in ascending order:\n");
 
  for (c = 0; c < n; c++)
     printf("%d\n", array[c]);
 
  return 0;
}

Output:

Complexity of bubble sort

The time complexity of bubble sort
The worst-case and average-case complexity: O(n2).It occurs when an array is in reverse order.
The Best case complexity of bubble sort: O(n). When an array is already sorted.
Space complexity for bubble sort: O(1)

Advantages of bubble sort

  • Bubble sort is easy to implement.
  • No extra space required while implementation.

Disadvantages of bubble sort

  • It’s not possible to implement bubble sort if we have a large number of the array.
  • Not suitable for real-time application

Write A Comment