Bubble Sort Algorithm: Modified Code (JAVA)

 In recent article of Bubble Sort Algorithm, we saw the code for Bubble Sort and time complexity for that code is O(N^2). But that code can be modified the coding logic to reduce the time complexity.

During comparisons, when we get two adjacent elements in ascending order(in any pass), then there is no need to compare elements.


Modification of previous code:

   1)  Number of comparisons depends upon value of i.
   2)  i(for passes) value increases, no of comparisons decreases.
   3)  We will modify inner loop for comparisons.

During elements comparison loop, we use j<n-1-i so that comparison of elements which are already sorted can be avoided. Check out the code for clean explanation and code.

 

public class BubbleSort {
  //implementation of bubble sort algorithm v1
      //time complexity is O(n^2)
      public static void main(String args[])
      {
           int arr[]={15,23,22,10,34,0,1};
           int n = arr.length;
           BubbleSort bs = new BubbleSort();
           bs.bubbleSort(arr,n);
           System.out.println("Sorted Array:");
           bs.printArray(arr,n);
      }
      void bubbleSort(int arr[],int n)
      {
          //sorting algo logic
          n=arr.length;
          for(int i=0; i<n-1; i++)     //for passes
          {
              for (int j=0; j<n-1-i; j++)   //for elements comparisons
              {
                  if(arr[j]>arr[j+1])
                  {
                      //swapping will be done
                      int temp;
                      temp=arr[j];
                      arr[j]=arr[j+1];
                     arr[j+1]=temp;
                  }
              }
          }
      }
     void printArray(int arr[],int n)
     {
          n = arr.length;
          for(int i=0; i<n; i++)
          {
              System.out.print(arr[i]+" ");
          }
     }
  

 Output:
 Sorted Array: 0 1 10 15 22 23 34
 Process finished with exit code 0