Bubble Sort using Golang

In this post, i am going to explain about bubble sort, which is simplest of sorting algorithm, in this we just need to swap the number based on condition.

 

In the above scenario, we need to traverse on array and each time we are going to compare with rest of the value and when the second number arr[j] is less than current number in that case we need to swap that number.

There are some draw back in this algorithm if the array is sorted already still this going to check and do compare which still going to use O(n^2).

 

 
 package main

import "fmt"

//swap used to swap arr value at given index
func swap(arr []int, i, j int) {
	arr[i], arr[j] = arr[j], arr[i]
}

//bubblesort
func bubbleSort(arr []int) {
	for i := 0; i < len(arr); i++ {
		for j := i; j < len(arr); j++ {
			if arr[i] > arr[j] {
				swap(arr, i, j)
			}
		}
	}
}

//printlIst use to check list is sorted or not
func printList(arr []int) {
	for _, val := range arr {
		fmt.Println("Value: ", val)
	}
}

func main() {
	arr := []int{10, 34, 9, 2, 50}
	bubbleSort(arr) // used to sort the list
	printList(arr)
}

 

Run the program using:

go run bubllesort.go
Before Sorting:  [10 34 9 2 50]
After Sorting: [2 9 10 34 50] 

 

This program is taking time complexity O(n^2), Can we can optimize  it to O(n), let us know in comment that how can we optimize it.

I am working on my interview preparation where i am going to solve all the algorithm problems and also implement and share with you all, In upcoming post i will post about other sorting algorithm using Go like Insertion Sort, Recursive Bubble sort, Merge Sort, Quick sort, Heap Sort, Heap Sort and all.

Please share your interview experience with us.