Bubble Sort in O(n)

We all know bubble sort is a comparison based sorting algorithm with a time complexity of O(n²). However we can reduce this time complexity to O(n) by simply introducing one flag.

Traditional bubble sort algorithm:

 func bubbleSort(stdArr[] student,n int) {  
      for i:=0;i<n;i++ {  
           for j:= i+1; j < n;j++ {  
                if(stdArr[i].marks < stdArr[j].marks) {  
                     std := stdArr[i]  
                     stdArr[i] = stdArr[j]  
                     stdArr[j] = std;  
                }  
           }  
      }  
 }  

Time Complexity: O(n²)
Space Complexity: O(1)

Above example is sorting students based on their marks using Golang. Above code can be optimized with time complexity as O(n) by simply introducing one flag in a for loop. This flag prevents execution of loop if items are already swapped.

Complete Program:

Time Complexity: O(n)

Space Complexity: O(1)