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
package com.sneppets.dsalgo;
public class BubbleSortExample {
public static void doBubbleSort(int inputArray[]){
int n = inputArray.length;
int k;
//one loop nested within another,
//you can suspect that this algorithm runs in O(n^2) time
for (int j=n; j>=0; j--){
for (int i=0; i<n-1; i++) {
k = i + 1;
if(inputArray[i] > inputArray[k])
{
swapElements(i,k,inputArray);
}
}
}
}
private static void swapElements(int i, int j, int[] inputArray) {
int temp = inputArray[i];
inputArray[i] = inputArray[j];
inputArray[j] = temp;
}
public static void main (String args[]){
int[] inputArray = {4,5,2,3,10,15,6,25,7,1};
System.out.println("Array elements before bubble sort");
printArrayElements(inputArray);
doBubbleSort(inputArray);
System.out.println("Array elements after bubble sort");
printArrayElements(inputArray);
}
private static void printArrayElements(int[] inputArray) {
for(int i=0; i<inputArray.length; i++){
System.out.print(inputArray[i] + ", ");
}
System.out.println("\n");
}
}
Output
Array elements before bubble sort 4, 5, 2, 3, 10, 15, 6, 25, 7, 1, Array elements after bubble sort 1, 2, 3, 4, 5, 6, 7, 10, 15, 25,
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
(n-1)+(n-2)+(n-3)+...+1 = n(n-1)/2
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
- Linear Search and Complexity Analysis
- Binary Search Number Guess Game
- How to calculate binary search complexity