Optimized Bubble Sort Algorithm.

In previous article of Bubble Sort, we saw modified code. In this we will optimize that code so that we can get time complexity of O(N).

Optimized Code: We need to check if we get any pass in which there is no swapping done, then we break the loop.

Optimized code can be obtained by using flag variable of int datatype and you can also use boolean datatype.

---

ADVERTISEMENT

---

Let's understand the below code:

• Firstly flag is initialized to 0, then control will enter the second loop if condition comes to be true then there will be swapping and flag will have the value 1.
• On the other hand, if the condition comes out to be false so no swapping will be done and it will come out of 2nd loop and if (flag==1) then the loop will get break. and it get repeated until all conditions gets false.
• Best case is when Array is sorted Time complexity O(N).

public class BubbleSortFlag {
    //in this program of bubble sort we will be using flag variable.
    // if there is no sorting found (it means array is already sorted)
    // then loop will get break and for this best case time complexity will be O(n).
   //optimized version
    static class bubbsort {
         void bubblesortflag(int arr[], int n) {
            n = arr.length;
            int flag;
            for(int i=0; i<n-1; i++)
            {
             flag =0;
                {
                    for(int j=0; j<n-1-i;j++)
                    {
                        if(arr[j]>arr[j+1])
                        {
                            //swapping will be done
                            int temp;
                            temp=arr[j];
                            arr[j]=arr[j+1];
                            arr[j+1]=temp;
                            flag =1;
                        }
                    }
                    if(flag==0)
                        break;
                }
            }
        }
    }
      public static class printArr
    {
     void printArr(int arr[],int n)
     {
         n = arr.length;
         for(int i=0; i<n; i++)
         {
             System.out.print(arr[i]+" ");
         }
     }
    }
    public static void main(String[] args) {
        int arr[]={1,2,3,5,6,8};
        int n;
        n=arr.length;
        bubbsort bs = new bubbsort();
        bs.bubblesortflag(arr,n);
        System.out.println("Sorted Arrays: ");
        printArr pa = new printArr();
        pa.printArr(arr,n);

    }
}

 

 

To understand basic approach of Bubble Sort Algorithm, click here.

To understand modified code of Bubble Sort Algorithm, click here.