Bubble Sort Algorithm

Bubble sort algorithm, sometimes referred to as sinking sort, is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.

The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

The algorithm, which is a comparison sort, is named for the way smaller or larger elements “bubble” to the top of the list.

Although the algorithm is simple, it is too slow and impractical for most problems compared to other sorting algorithms.

Complexity of this algorithm is as below :

Performance
  • Worst-case performance:- O(n2)
  • Best-case performance:- O(n)
  • Average performance:- O(n2)
  • Worst-case space complexity:- O(1) auxiliary
Example Steps With Description

Given Array:- 20, 3, 35, 21, 12

First Iteration:

( 20 3 35 21 12 ) -> ( 3 20 35 21 12 ), Algorithm compares first two elements, and swaps because 20 > 3.

( 3 20 35 21 12 ) –> ( 3 20 35 21 12 ), No Swap needed as 20 < 35.

( 3 20 35 21 12 ) –> ( 3 20 21 35 12 ), Swap since 35 > 21.

( 3 20 21 35 12 ) –> ( 3 20 21 12 35 ), Swap since 35 > 12.

Second Iteration:

(3 20 21 12 35 ) -> (3 20 21 12 35 ), No Swap needed as 3 < 20.

(3 20 21 12 35 ) -> (3 20 21 12 35 ), No Swap needed as 20 < 21.

(3 20 21 12 35 ) -> (3 20 12 21 35 ), Swap, as 21>12.

(3 20 12 21 35 ) -> (3 20 12 21 35 ), No Swap needed as 21 < 35.

Third Iteration:

(3 20 12 21 35 ) -> (3 20 12 21 35 ), No Swap needed as 3 < 20.

(3 20 12 21 35 ) -> (3 12 20 21 35 ) , Swap needed as 20 > 12, Now our array is sorted.But algorithm don’t know that it’s already sorted.

(3 12 20 21 35 ) -> (3 12 20 21 35 ).

(3 12 20 21 35 ) -> (3 12 20 21 35 ).

Java Program Of Bubble Sort

Output

Input Array before Bubble Sort. 20 3 35 21 12 Sorted Array after Bubble Sort. 3 12 20 21 35

The above code always runs O(n2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn’t swap any elements.

Java Program Of Optimized Bubble Sort

Output

Input Array before Bubble Sort. 20 3 35 21 12 Breaking loop on iteration :- 4 , as array is sorted and no swapping occurred in last iteration. Sorted Array After Bubble sort. 3 12 20 21 35

Run again with sorted array as input (Already provided in program with comment)

Output

Input Array before Bubble Sort. 10 20 30 50 70 Breaking loop on iteration :- 1 , as array is sorted and no swapping occurred in last iteration. Sorted Array After Bubble sort. 10 20 30 50 70

Some theory part of this article uses material from the Wikipedia article “Bubble Sort”, which is released under the CC BY-SA 3.0.

It's good to share...Share on FacebookTweet about this on TwitterShare on LinkedInPin on PinterestShare on Google+Email this to someone

Leave a Reply

Your email address will not be published. Required fields are marked *