bubble sort

Bubble Sort in Java and Complexity Analysis

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list to be sorted and compares each pair of adjacent elements in the list and swaps them if they are not in order.

This algorithm is too slow when compared to insertion sort. It’s better to use bubble sort only if the input list is mostly sorted already with few elements not-in-order and that needs to be sorted.

Bubble Sort Java Example

Output

Time Complexity

In general, if “n” is the number of elements in the array, there are (n-1) comparisons on the first pass, (n-2) comparisons on the second pass, and so on. The formula for the sum of such series is

You can say the algorithm makes about (n2/2) comparisons, Ignoring the -1 as it does not make much difference if n is large. Let’s say if swap is necessary about half the time i.e., (n2/4) swaps. So both swaps and comparisons are proportional to n2.

Since we don’t count constants in Big O notation, so ignore 2 and 4 and we can say that bubble sort runs in O(n2) time.

Space Complexity

The space for bubble sort is O(1), because the above algorithm requires only a single additional memory space for temp variable.

Recommended Posts

References

Leave a Reply

avatar
  Subscribe  
Notify of