In Bubble sort, each element is compared with its adjacent element. If the first element is smaller than the second one, then the positions of the elements are interchanged, otherwise it is not changed.

Then next element is compared with its adjacent element and the same process is repeated for all the elements in the array until we get a sorted array.

If the size of the array is n,

• Then in First Pass,  (n-1) comparisions are required i.e. in above example, 8 comparisons are required to Bubbled up the '1' at the left most position.
• In Second Pass, (n-2) comparisions are required i.e. 7 comparisions are required to Bubbled up the '2' on the second left most position.
• And so on.

Algorithm

The pseudocode for the bubble sort will be as below:

bubbleSort( list : array of items )

   n = list.count;
   
   for i = 0 to n-1 do:

      swapped = false
      for j = 0 to n-i-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, break the loop.*/
      if(swapped == false) then
         break
      end if

   end for

return list

Java Program Implementation

public static int[] bubbleSort(int[] inputArr)
{
	boolean swapped = false;
	int n = inputArr.length;
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-i-1;j++)
		{
			if(inputArr[j]>inputArr[j+1])
			{
				int temp = inputArr[j];
				inputArr[j]=inputArr[j+1];
				inputArr[j+1]=temp;

				swapped = true;
			}
		}

		if(!swapped)
		{
			break;
		}
	}

	return inputArr;
}

Bubble Sort is sometimes also referred as Sinking sort as instead of Bubbling up the smallest element to the left side, some developer write an algorithm to moving (sinking) largest element to right side.

Time Complexity

Now if we consider time taken by each comparison is constant C. Then the total time taken for the above sorting will be C*( N-1 + N-2 + … + 2 + 1 )  which on solving becomes O(N²) time complexity.

Space Complexity

The space complexity for the same will be O(1) as all operations are almost in space and only a single variable is used in loop for holding value.

Bubble sort gives stable and in place sorting.

Advantage

• When data set is small, bubble sort is efficient
• Easy to implement
• Memory efficient
• It gives stable sort

Disadvantage

• It is time-inefficient as it is having O(N²) time complexity.
• For large data set it is not very efficient as time grows exponentially.

Bubble Sort vs Selection Sort

In Selection sort, a maximum of n swap operations are required, whereas in Bubble Sort, up to n swap operation happens for each element, so up to n² total swap operation are required. These swap (write) operations are memory-intensive, so Selection sort becomes even more efficient than Bubble sort for large lists.

In short, Selection Sort is used normally in cases where memory writes are quite expensive than memory reads.  

However, both Selection sort and Bubble Sort take O(n²) time, so it is not recommanded to use them in real-life applications. 

You can also check the other articles on sorting and searching such as selection sort, binary search, fibonacci search, merge sort etc. you can also go through our other articles on different algorithms and data structures.