How to implement Bubble Sort in Java

Posted on Updated on

Bubble Sort

Bubble sort also termed as sinking sort, is simple sorting algorithm which sort the list of data in ascending order by repeatedly stepping into it. In this algorithm, two adjacent element from list is compared and swapped if preceding element is greater than its next element. This will proceed throughout the list until all the elements are arranged into ascending order.

Bubble sort makes multiple passes to get the final result. Below figure shows the first pass-
The number of pairs from ‘N’ number of elements that will be required to compare in first pass is (N-1). Let us see a graphical representation how it is done in first pass-

Bubble-sort
In the example we’ve five numbers of elements and number of pairs that will be required in first pass is (N-1) i.e. 4. This will go on until we’ve got a sorted series.

Let us see how this can be implemented in Java.

 

Output:

 

The number of passes required to complete the sorting is explained below:

Pass No. of pairs
1 N-1
2 N-2
3 N-3
- -
N-1 1

As we can see the number of comparison required on first pass is N-1 and in second it is N-2 and it goes on until it reaches to one. Hence the complexity of Bubble Sort is O(n2).

The bubble sorting is considered to be most inefficient as it is required to make exchange of data before the final location is known. This involves lots of unnecessary exchanges and cost performance.

Advantage of using bubble sort is the simplicity of the algorithm.Space complexity for Bubble Sort is O(1), because only single additional memory space is required for temp variable

Best-case Time Complexity will be O(n), it is when the list is already sorted.

Leave a Reply

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

Time limit is exhausted. Please reload CAPTCHA.