Quick sort implementation using golang

In today post, I am going to implement Quick sort using go or golang.

Quicksort is an in-place sorting algorithm which follow divide-and-conquer algorithm.Time complexity of quicksort shows that, on average, the algorithm takes O(n log n) comparisons to sort n items. In the worst case, it makes O(n^2) comparisons, though this behavior is rare.

Application where quick sort use:

1. Commercial computing: Used in various government and private organizations for the purpose of sorting various data like sorting of accounts/profiles by name or any given ID, sorting transactions by time or locations, sorting files by name or date of creation etc.
2. Numerical computations: Most of the efficiently developed algorithms use priority queues and inturn sorting to achieve accuracy in all the calculations.
3. Information search: Sorting algorithms aid in better search of information and what faster way exists than to achieve sorting using quick sort.

Quick sort is used everywhere for faster result.

Image source from Wikipedia.

Algorithm: 

Please follow bellow steps to implement Quick sort.

1. Step  − Make any element as pivot
2. Step  − Partition the array on the basis of pivot
3. Step  − Apply quick sort on left partition recursively
4. Step  − Apply quick sort on right partition recursively
5. step  - Apply step 3 to step 4 till start index is less than endindex
6. step  - Apply step 1 to 4 till step 5 condition break.
   

The complicated part is pivot element, there are multiple way we can select pivot element, you can select pivot element as first element of array or last element of array, or you can select randomly, once you select pivot element sort the array based on pivot element and track the partition index which going to use in divide and conquer because we are going to split the array from that position.

Algorithm for Partition:

1. Select partition index, partition-index = startIndex-1
2. Select pivot-element: pivot-element = arr[highest-index]
3. Iterate over array and check arr-element is less than pivot-element in that case swap the number and track partition-index.
4. swap the partition-index with selected arr[highest-index], because we sort our array based on pivot-element
5. Return partition index so in next iteration quick sort divide the array based on the partition.
   

These are the step which we need to apply while calling the partition function. When you see the code most of your doubt is clear,

Code:

 

package main

import (
	"fmt"
)

func getPivotIndex(arr []int, startIndex, endIndex int) int {
	pivotIndex := startIndex - 1
	pivotElement := arr[endIndex]

	for i := startIndex; i < endIndex; i++ {
		if arr[i] < pivotElement {
			pivotIndex++
			arr[i], arr[pivotIndex] = arr[pivotIndex], arr[i]
		}
	}
	arr[pivotIndex+1], arr[endIndex] = arr[endIndex], arr[pivotIndex+1]
	return pivotIndex + 1
}

func quickSort(arr []int, startIndex, endIndex int) {
	if startIndex < endIndex {
		pivotIndex := getPivotIndex(arr,
			startIndex, endIndex)
		quickSort(arr, startIndex, pivotIndex-1)
		quickSort(arr, pivotIndex+1, endIndex)
	}

}

func main() {
	arr := []int{10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0}
	quickSort(arr, 0, len(arr)-1)
	fmt.Println(arr)
}

 

Above golang code is for quicksort. Please check and let me know if you have any doubt regarding that.

I added other sorting algorithm implementation as well like, bubble sort using go, insertion sort using go, merger sort using go, binary search using golang.