Bubble Sort

The Simplest Sorting Technique

A sorting algorithm is used to arrange elements in ascending/descending order. Bubble Sort is a simplest sorting algorithm. It compares the adjacent elements and swaps them if they are in the wrong order.

How does bubble sort work?

• Compare the first and second elements, starting with the first index.
• They are swapped if the first element is greater than the second.
• Compare the second and third elements now. If they are not in the correct order, swap them.
• The preceding procedure is repeated until it reaches the final element.

Code:

public static void Bubblesort(int[] arr){// Taking array as parameter
  int i,j;//declaring variables
  int temp;
  for(i=0;i<arr.length-1;i++) {
    for(j=0;j<arr.length-1;j++){
      if(arr[j]>arr[j+1]) {
         temp=arr[j];
         arr[j]=arr[j+1];
         arr[j+1]=temp;
       }
     }
  }
  //printing array after sorting
  System.out.println("Array after sorting");
  System.out.println("Number of passes required "+i);
  for(i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }

Let us see how this works with the help of a diagram:

For example, given below is an unsorted array, we will sort it in ascending order, based on the steps given above:

Given array to sort in ascending order. Source

In each pass, the largest element bubbles out at the end. Source

In an array with 5 elements, we required only 4 passes to sort the data. Source

What do we observe from this example?

• If number elements to sort is n then Maximum number of passes required to sort it are n-1
• As we could see after every pass the largest element bubbles out, that is placed at its correct position.

Is there any way to optimise the Bubble sort algorithm?

• Not necessarily we require all passes to sort therefore we need to find the pass where no swapping occurs and stop after that.
• As we could see after every pass the largest element is placed at its correct position so we can stop comparing that element from next pass.

Code for the optimised bubble sort:

//Method for optimized bubble sort
 public static void optimisedBubblesort(int[] arr){
  int i,j,temp;//declaring variables
  boolean flag;
  for(i=0;i<arr.length-1;i++){   
   flag=false;
   for(j=0;j<arr.length-i-1;j++){
      if(arr[j]>arr[j+1]){  
       temp=arr[j]; 
       arr[j]=arr[j+1];
       arr[j+1]=temp;
       flag=true;
      }
   }
   if(flag==false) {
    break;
   }
  }
  //printing array after sorting
  System.out.println("Array after sorting with optimised code");
  System.out.println("Number of passes required "+i);
  for(i=0;i<arr.length;i++) {
   System.out.print(arr[i]+" ");
  }
 }

What are the different features of Bubble Sort?

• Bubble Sort is a Stable sorting algorithm because we only swap when two elements A and B if A is less than B. If A is equal to B then we don’t swap therefore their relative order is maintained.
• Bubble Sort is an In-place algorithm meaning it does not need an extra space and produces an output in the same memory that contains the data.
• Worst case and best case time complexity of bubble sort are O(N²) and O(N) Hence it is efficient for small datasets.

Where is Bubble Sort used in real-life?

• The contact list on your phone is sorted in alphabetical order by using bubble sort.
• We use bubble sort algorithms when students are lined up in random order and need to be arranged in ascending order of height.

Upcoming topics for the blogs:

For queries regarding the content, please drop a mail to loop@cumminscollege.in Links for in-depth studying and practice problems are sent via mail to students of the college on the date of publishing of the blog by Loop Club. The content is a part of DSA Bulletins started by Team Loop, to provide thorough knowledge and facilitate the learning of new topics of DSA. We are a group of students who are passionate about CP and DSA and want to create awareness and help students in the above topics.