Bubble sorting algorithm


Introduction to bubble sort:-

Bubble sorting algorithm is the first and easiest algorithm we think of generally when it comes to sorting. This is the general algorithm we follow if we want to sort anything in our daily life. Yes, what ever you reading is correct. Let’s Imagine you have 10 apples to sort according to their size in increasing order.

Generally what we do is, Compare the first two apples and swap them if the second apple is bigger than first one. Now the apples at 2nd and 3rd position are compared and swapped to second position if third apple is smaller than second one. The same procedure is followed till 10th apple. Essentially by the end of the first 10 comparisons we will have the biggest apple in the 10th position. Now the same procedure is(comparing 1st and 2nd apple, 2nd and 3rd apple …….., 8th and 9th apple) repeated to get the second biggest in 9th position. If we repeat the same procedure for 8 more times we will have all apples sorted according to their size.

It is called bubble sort because we are bubbling the bigger element in each comparison to the end.

Now Observe the following video. By the end of each comparison, we will have the biggest element in the nth position.

 
Bubble sort

Bubble sort pseudocode:-

Before getting into the actual coding part, let’s dissolve the above logic into the pseudocode. Bubble sorting pseudocode as follows.

  1.  start a loop with a variable i till the length of the array i.e n
  2. start another loop with a variable j starting from 1 till length of array-i. This is because we need to repeat the inner loop n times for the first time, n-1 times second time and goes on.
  3. if element at array[j-1] is greater than a[j] swap them. otherwise continue.
  4. return the sorted array.
Now using this pseudocode, let’s feast on the coding part.
public class BubbleSort {
public static int[] bubbleSort(int[] a) {
int lengthOfArray=a.length;
for(int i=0;i<lengthOfArray;i++) {
for(int j=1;j<lengthOfArray-i;j++) {
if(a[j-1]>a[j]) {
int temp= a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
return a;
}
public static void main(String[] args) {
int[] unsortedArray= {-2,0,100,10,3};
for(int a :bubbleSort(unsortedArray)) {
System.out.println(a);
}
}
}

function bubbleSort(arrayToBeSorted) {
     var lengthOfArray = arrayToBeSorted.length;
     for (var i =0; i < lengthOfArray; i++) {
         for (var j =1; j < lengthOfArray - i; j++) {
            if (arrayToBeSorted[j -1] > arrayToBeSorted[j]) {
                var tempValue = arrayToBeSorted[j -1];
                arrayToBeSorted[j - 1] = arrayToBeSorted[j]
                arrayToBeSorted[j] = tempValue
             }
         }
     }
     return arrayToBeSorted;
}

Time complexity of Bubble sort:-

Bubble sort is the very first and simplest sorting algorithm. The Time complexity of the bubble sort is very easy to derive as the logic is very simple. Observe the logic shown above. Irrespective of coding language we need multiple loops to sort the values. By following the rules of the time complexity the derivation of the complexity comes down to O(n2).

Space complexity of Bubble sort:-

Space complexity is nothing but the amount of space the algorithm is going to consume as the input increases. Observe the coding part of the bubble sort. We are sorting the array in the given input itself. Such type of algorithms are called in place algorithms. But we are creating some local variables to keep track of the indexes in the array. These variables are created and being reused throughout the process. So they take a constant amount of space. Thus we can generalize the space complexity of the bubble sort algorithm as O(1).