Bubble Sort | Sorting Algorithm
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.
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(N^{2}) time complexity.
Average Case
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.
Advantage
- When data set is small, bubble sort is efficient
- Easy to implement
- Memory efficient
- It gives stable sort
Disadvantage
- It is time-inefficient as it is having O(N^{2}) 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 n^{2} 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
However, both Selection sort and Bubble Sort take O(n^{2}) 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.
Tags: Algorithms, bubble sort, sinking sort, Sorting
Comments and Queries
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>For more information on supported HTML tags in disqus comment, click here.