Code Pumpkin

Bubble Sort | Sorting Algorithm

October 15, 2017
Posted by Pumpkin
Subscribe

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.

Bubble Sort Average Case

This GIF Image is generated through  Algorithms mobile app

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(N2) time complexity.

Average Case

Bubble Sort Average Case

Worst Case (Reverse List)

Bubble Sort Worst Case

Above GIF Images are generated through  Algorithms mobile app.


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(N2) 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 n2 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.  

Bubble Sort

Bubble Sort Average Case

Selection Sort

Selection Sort Average Case

Above GIF Images are generated through  Algorithms mobile app.

However, both Selection sort and Bubble Sort take O(n2) 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.

That's all for this topic. If you guys have any suggestions or queries, feel free drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here

Happy Learning 🙂

Tags: , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank