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:

	/*************************************************************************
	> File Name: bubblesort.go
	> Author: Rohit Mourya
	> Blog: https://mouryarohit.blogspot.in/
	> Created Time: Mon April 24 2017
	************************************************************************/
	package main
	import (
	"fmt"
	"strconv"
	)
	type student struct {
	rollNo int
	name string
	marks float64
	}
	func main () {
	var stdArr[] student
	stdArr = make([]student, 10)
	for i:=0;i<10;i++ {
	stdArr[i].rollNo = i
	stdArr[i].name = "Student " + strconv.Itoa(i+1)
	stdArr[i].marks = (70.06 + float64(i))
	}
	bubbleSort(stdArr,10)
	fmt.Printf("\nSorted Student details:")
	fmt.Printf("\nRoll No\tName\tMarks\n")
	for i:=0;i<10;i++ {
	printStudeDetails(stdArr[i])
	}
	}
	func bubbleSortTraditional(stdArr[] student,n int) {
	swapped := 1
	for i:=0;i<n && swapped == 1;i++ {
	swapped = 0
	for j:= i+1; j < n;j++ {
	if(stdArr[i].marks < stdArr[j].marks) {
	std := stdArr[i]
	stdArr[i] = stdArr[j]
	stdArr[j] = std;
	swapped = 1
	}
	}
	}
	}
	func bubbleSortModified(stdArr[] student,n int) {
	swapped := 1
	for i:=0;i&lt;n &amp;&amp; swapped == 1;i++ {
	swapped = 0
	for j:= i+1; j &lt; n;j++ {
	if(stdArr[i].marks &lt; stdArr[j].marks) {
	std := stdArr[i]
	stdArr[i] = stdArr[j]
	stdArr[j] = std;
	swapped = 1
	}
	}
	}
	}
	func printStudeDetails(std1 student) {
	fmt.Printf("\n%d\t%s\t%f",std1.rollNo,std1.name,std1.marks)
	}

view raw bubblesort.go hosted with ❤ by GitHub

Time Complexity: O(n)

Space Complexity: O(1)