Bubble Sort in Action: Implementation and Performance

What is Bubble Sort?

Bubble sorting algorithm is a comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

This algorithm is not suitable for large datasets as its average and worst case complexity is of ?(n²) where n is the number of items.

Bubble sort is a simple sorting algorithm. Bubble Sort Algorithm is used to arrange N elements in ascending order, and for that you have to begin with 0^th element and compare it with the first element. If the 0^th element is found greater than the 1^st element then the swapping operation will be performed i.e. the two values will get interchanged. In this way all the elements of the array gets compared.

Logic to sort array in ascending order

There are numerous logic to sort given set of numbers. Here I am using general algorithm which we apply in real life for simplicity. To sort array we select an element and place it to its correct position by comparing with subsequent elements.

Step by step descriptive logic to sort array in ascending order.

1. Input size of array and elements in array. Store it in some variable say size and arr.
2. To select each element from array, run an outer loop from 0 to size - 1. The loop structure must look like for(i = 0; i < size; i++) .
3. Run another inner loop from i + 1 to size - 1 to place currently selected element at its correct position. The loop structure should look like for(j = i + 1; j < size; j++) .
4. Inside inner loop to compare currently selected element with subsequent element and swap two array elements if not placed at its correct position.

   Which is if(arr[i] > arr[j]) then swap arr[i] with arr[j].

Algorithm for Bubble Sort

1. algorithm Bubble_Sort(list)
2. Pre: list != fi
3. Post: list is sorted in ascending order for all values
4. for i <- 0 to list:Count – 1
5. for j <- 0 to list:Count – 1
6. if list[i] < list[j]
7. Swap(list[i]; list[j])
8. end if
9. end for
10. end for
11. return list
12. end Bubble_Sort

Different Approach to see the iteration

Pseudocode

We observe in the algorithm that Bubble Sort compares each pair of array element unless the whole array is completely sorted in an ascending order. This may cause a few complexity issues like what if the array needs no more swapping as all the elements are already ascending.

To ease-out the issue, we use one flag variable swapped which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will come out of the loop.

Pseudocode of BubbleSort algorithm can be written as follows ?

 procedure bubbleSort( list : array of items )

   loop = list.count;
   
   for i = 0 to loop-1 do:
      swapped = false
		
      for j = 0 to loop-1 do:
      
         /* compare the adjacent elements */   
         if list[j] > list[j+1] then
            /* swap them */
            swap( list[j], list[j+1] )		 
            swapped = true
         end if
         
      end for
      
      /*if no number was swapped that means 
      array is sorted now, break the loop.*/
      
      if(not swapped) then
         break
      end if
      
   end for
   
end procedure return list

Bubble sort in C language using function

C programming code for bubble sort to sort numbers or arrange them in ascending order. You can modify it to print numbers in descending order.

Program:

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

Output:

Enter number of elements
9
Enter 9 integers
9 8 7 6 5 4 3 2 1
Sorted list in ascending order:
1
2
3
4
5
6
7
8
9
Press any key to continue . . .

You can also sort strings using Bubble sort, it is less efficient as its average and worst case complexity is high, there are many other fast sorting algorithms like quicksort, heapsort, etc. Sorting simplifies problem-solving in computer programming.

Bubble sort algorithm implementation in descending order using C Programming Language

Program:

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

Program:

Enter number of elements
9
Enter 9 integers
1 2 3 4 5 6 7 8 9
Sorted list in ascending order:
9
8
7
6
5
4
3
2
1
Press any key to continue . . .