Golang Quick Sort Algorithm

1. Introduction

Quick Sort is a divide-and-conquer sorting algorithm that works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.

2. Implementation Steps

1. Choose an element from the array as the pivot.

2. Partition the array around the pivot so that elements smaller than the pivot come before it and elements greater than the pivot come after it.

3. Recursively apply Quick Sort to the two sub-arrays.

4. Combine the sub-arrays and the pivot to get the sorted array.

3. Implementation in Golang

package main
import (
	"fmt"
)
// partition rearranges the elements by partitioning around the pivot
func partition(arr []int, low, high int) int {
	pivot := arr[high]  // choosing last element as pivot
	i := low - 1        // index of smaller element
	for j := low; j < high; j++ {
		if arr[j] < pivot {
			i++
			arr[i], arr[j] = arr[j], arr[i]  // swap
		}
	}
	arr[i+1], arr[high] = arr[high], arr[i+1]  // swap pivot into its correct position
	return i + 1
}
// QuickSort sorts the array using quick sort algorithm
func QuickSort(arr []int, low, high int) {
	if low < high {
		pi := partition(arr, low, high)  // pi is partitioning index
		QuickSort(arr, low, pi-1)  // sort elements before partition
		QuickSort(arr, pi+1, high) // sort elements after partition
	}
}
func main() {
	data := []int{10, 80, 30, 90, 40, 50, 70}
	fmt.Println("Original array:", data)
	QuickSort(data, 0, len(data)-1)
	fmt.Println("Sorted array:  ", data)
}

Output:

Original array: [10 80 30 90 40 50 70]
Sorted array:   [10 30 40 50 70 80 90]

Explanation:

1. The partition function takes in an array and its low and high indices. It chooses the last element as the pivot and places all smaller elements before the pivot and all larger ones after it. This function returns the index of the pivot in the partitioned array.

2. The QuickSort function is the main sorting function. It partitions the array using the partition function and then recursively applies QuickSort to the resulting sub-arrays.

3. Inside the main function, an array is initialized, displayed in its original state, sorted using QuickSort, and then displayed in its sorted state.

4. The efficiency of Quick Sort comes from the fact that on average, it's able to partition the array into two roughly equal pieces. In the average and best cases, its time complexity is O(n log n). However, in the worst-case, which is rare, its time complexity can degrade to O(n^2).

This provides a detailed understanding of the Quick Sort algorithm in Golang.