Bubble Sort

Lets discuss Bubble Sort today.

Problem : Given a list of integers in random order, arrange them in either ascending or descending order.

For example consider this list of integers : 4 2 8 1 6 then output should be 1 2 4 6 8 or 8 6 4 2 1 .

There are many sorting algorithms which we can use to solve above problem. But lets start with basic simple and easiest algorithm of sorting i.e. Bubble Sort.

Logic

In Bubble sort for ascending order,as the name suggests we will bubble out the largest number to last position (i.e its correct position in sorted array) in the array. And after that we will repeat the same procedure for the rest of the array until all the numbers are at their correct position.

So how do we bubble out largest number ?

We compare adjacent elements with each other and if the number on left side is greater than the number of right side we swap them. So at the end we have the largest number at the end.

Lets take an example :

Implementation: To sort numbers in ascending order

void BubbleSort(in[] input)
{
  for(int j = input.Length - 1; j > 0; j--)
  {
    for(in i = 0; i < j; i++)
    {
       if(input[i] > input[i+1])
       {
          int temp = input[i];
          input[i] = input[i + 1];
          input[i + 1] = temp;
        }
     }
   }
  Console.WriteLine("Numbers sorted in ascending order: ");
  for(int n = 0; n < input.Length; i++)
    Console.Write(+input[n] + " ");
}

void BubbleSort(in[] input)

{

for(int j = input.Length - 1; j > 0; j--)

{

for(in i = 0; i < j; i++)

{

if(input[i] > input[i+1])

{

int temp = input[i];

input[i] = input[i + 1];

input[i + 1] = temp;

}

Console.WriteLine("Numbers sorted in ascending order: ");

for(int n = 0; n < input.Length; i++)

Console.Write(+input[n] + " ");

}

Analysis:

In this sort, on every pass we will bubble out the largest element from the array to its correct position (i.e. last) this takes O(n) time and we repeat this for every element in array.

After we shift the first largest element to its correct position we reduce the array size by 1.

So, to place 1st element at it’s correct position , number of operations required is : n-1

to place 2nd element at it’s correct position, number of operations required is: n-2 and so on…

So, to sort ‘n’ elements total number of operations required are : (n-1) + (n-2) + (n-3) + …+1 , which is n(n+1)/2. After ignoring constants , result is n². Therefore time complexity of bubble sort in O(n²). Also the number of swaps in bubble sort will be n² in worst case !

Highlights:

-Bubble out the largest element to end by swapping adjacent elements

-Time Complexity O(n²).

-Space Complexity O(1) or constant.

-Number of swaps in worst case is n²

-Bubble sort is Stable sort i.e. it maintains the relative order of elements.

Recent Posts

Algotutor