# Bubble Sort | Sorting Algorithm

October 15, 2017
Posted by Pumpkin

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.

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

Worst Case (Reverse List)

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.

• When data set is small, bubble sort is efficient
• Easy to implement
• Memory efficient
• It gives stable sort

• 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

Selection Sort

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.

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>
```