Bubble Sort

Bubble Sort is used to sort the elements of an array in ascending order.It is the simplest sorting algorithm.This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order.

It is called Bubble sort, because with each iteration the largest element in the list bubbles up towards the last place, just like a water bubble rises up to the water surface.

Bubble sort Flow Chart:

Let us understand this sorting technique with a flow:

For Bubble sort,you have to begin with 0th element and compare it with the first element. If the 0th element is found greater than the 1st element then the swapping operation will be performed i.e. the two values will get interchanged. In this way all the elements of the array gets compared.



Below given figure shows how Bubble Sort works:

Bubble Sort Algorithm in C

    Bubble Sort(a[],n)
For i=0 to n-1
Swap=false
For j=i+1 to n
if a[j-1] >a[j]
Swap(a[j-1],a[j])
Swap=true
Break if not swapped


⇒Bubble Sort Java:http://bit.ly/2ORSLcC
⇒Bubble Sort C:http://bit.ly/2U1rogW

Bubble sort complexity calculation:

In Bubble Sort, n-1 comparisons will be done in 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be

(n-1)+(n-2)+(n-3)+.....+3+2+1

Sum = n(n-1)/2

i.e O(n^2)

Hence the complexity of Bubble Sort is O(n^2).

The main advantage of Bubble Sort is the simplicity of the algorithm. Space complexity for Bubble Sort is O(1), because only single additional memory space is required i.e. for temp variable

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

Bubble Sort Complexity:

• Worst Case Time Complexity : O(n^2)
• Best Case Time Complexity : O(n)
• Average Time Complexity : O(n^2)
• Space Complexity : O(1)