# Implementation For The Sort Algorithms In Golang

## O (N2) -- The comparison-based sort algorithms

1. Bubble sort (BUB)
2. Selection sort (SEL)
3. Insert sort (INS)

The comparison-based sort algorithms compare the elements of the array and then decide whether to swap them. These three sorting algorithms are the easiest ones to implement, but are not the most efficient, because their time complexity is O (N2).

## O (NlogN) -- The comparison-based sort algorithms

1. Heap sort
2. Shell Sort (SHE)
3. Merge sort (MER)
4. Quick sort (QUI)
5. Random Quick Sort (R-Q)

These sorting algorithms are usually implemented recursively.

## O (N) -- The sort algorithms not based on comparison

1. Counting sort (COU)
2. Bucket sort (BUC)

Complexity and stability

Algorithm Time complexity (average) Time complexity (worst) Time complexity (best) Space complexity Stability
Bubble sort O (n2) O (n2) O (n) O (1) Stable
Selection sort O (n2) O (n2) O (n2) O (1) Unstable
Insert sort O (n2) O (n2) O (n) O (1) Stable
Heap sort O(nlog2​n) O(nlog2​n) O(nlog2​n) O (1) Unstable
Shell sort O(n1.3) O(n2) O(n) O(1) Unstable
Merge sort O(nlog2​n) O(nlog2​n) O(nlog2​n) O(1) Stable
Quick sort O(nlog2​n) O(n2) O(nlog2​n) O(nlog2​n) Unstable
Counting sort O(n+k) O(n+k) O(n+k) O(n+k) Stable
Bucket sort O(n+k) O(n2) O(n) O(n+k) Stable
Radix Sort O(n∗k) O(n∗k) O(n∗k) O(n+k) Stable

## Bubble Sort

The core of the algorithm is to swap the positions by pairwise comparison each time. It selects the largest (smallest) element in the remaining disordered sequence to put it at the end of the queue.

``````func BubbleSort(data []int) {
for i := 0; i < len(data); i++ {
for j := 1; j < len(data)-i; j++ {
if data[j] < data[j-1] {
data[j], data[j-1] = data[j-1], data[j]
}
}
}
}``````

## Selection Sort

The core of the algorithm is to search the sequence linearly and find the largest (smallest) value, and replace the largest (small) value with the number at the left end of the sequence and sort the elements then.

``````func SelectionSort(data []int) {
length := len(data)
for i := 0; i < length; i++ {
maxIndex := 0
for j := 1; j < length-i; j++ {
if data[j] > data[maxIndex] {
maxIndex = j
}
}
data[length-i-1], data[maxIndex] = data[maxIndex], data[length-i-1]
}
}``````

## Heap Sort

Heap sort is a sorting algorithm designed with the data structure of heap.

``````func HeapSort(data []int) []int {
heapify(data)
for i := len(data) - 1; i > 0; i-- {
data[0], data[i] = data[i], data[0]
siftDown(data, 0, i)
}
return data
}

func heapify(data []int) {
for i := (len(data) - 1) / 2; i >= 0; i-- {
siftDown(data, i, len(data))
}
}

func siftDown(heap []int, lo, hi int) {
root := lo
for {
child := root*2 + 1
if child >= hi {
break
}
if child+1 < hi && heap[child] < heap[child+1] {
child++
}
if heap[root] < heap[child] {
heap[root], heap[child] = heap[child], heap[root]
root = child
} else {
break
}

}
}``````

## Insertion Sort

It traverses from the second number to the right, and move the element to the left each time to place it in a correct position (which is larger than the left and smaller than the right).

``````func InsertionSort(data []int) {
for i := 1; i < len(data); i++ {
if data[i] < data[i-1] {
j := i - 1
temp := data[i]
for j >= 0 && data[j] > temp {
data[j+1] = data[j]
j--
}
data[j+1] = temp
}
}
}``````

## Shell Sort

It is invented by Shell in 1959. It is an improved sorting algorithm on the base of the simple insertion sort.

It differs from insertion sort in that it prioritizes the elements that are farther away. Shell sort is also called Diminishing Increment Sort.

``````func ShellSort(data []int) {
n := len(data)
h := 1
for h < n/3 {
h = 3*h + 1
}
for h >= 1 {
for i := h; i < n; i++ {
for j := i; j >= h && data[j] < data[j-h]; j -= h {
data[j], data[j-h] = data[j-h], data[j]
}
}
h /= 3
}
}``````

## Merge Sort

Merge sort is an effective sort algorithm based on merge operation. It is a very typical application of the Divide and Conquer method.

``````func MergeSort(data []int) []int {
if len(data) <= 1 {
return data
}
middle := len(data) / 2
left := MergeSort(data[:middle])
right := MergeSort(data[middle:])

return merge(left, right)
}
func merge(left, right []int) []int {
result := make([]int, len(left)+len(right))
for i := 0; len(left) > 0 || len(right) > 0; i++ {
if len(left) > 0 && len(right) > 0 {
if left[0] < right[0] {
result[i] = left[0]
left = left[1:]
} else {
result[i] = right[0]
right = right[1:]
}
} else if len(left) > 0 {
result[i] = left[0]
left = left[1:]
} else if len(right) > 0 {
result[i] = right[0]
right = right[1:]
}
}
return result
}``````

## Quick Sort

It separates the records waiting to be sorted into two independent parts through a sort, and the keywords of one part are smaller than the keywords of the other part. Then the two records can be sorted separately to achieve an orderly sequence.

``````func quickSort(nums []int) {
recursionSort(nums, 0, len(nums)-1)
}

func recursionSort(data []int, left int, right int) {
if left < right {
pivot := partition(data, left, right)
recursionSort(data, left, pivot-1)
recursionSort(data, pivot+1, right)
}
}

func partition(data []int, left int, right int) int {
for left < right {
for left < right && data[left] <= data[right] {
right--
}
if left < right {
data[left], data[right] = data[right], data[left]
left++
}

for left < right && data[left] <= data[right] {
left++
}
if left < right {
data[left], data[right] = data[right], data[left]
right--
}
}
return left
}``````

## Random Quick Sort

``````func RandomQuickSort(list []int, start, end int) {
if end-start > 1 {
mid := randomPartition(list, start, end)
RandomQuickSort(list, start, mid)
RandomQuickSort(list, mid+1, end)
}
}

func randomPartition(list []int, begin, end int) int {
rand.Seed(time.Now().UnixNano())
i := begin + rand.Intn(end-begin)
list[i], list[begin] = list[begin], list[i]
return partition(list, begin, end)
}

func partition(list []int, begin, end int) (i int) {
cValue := list[begin]
i = begin
for j := i + 1; j < end; j++ {
if list[j] < cValue {
i++
list[j], list[i] = list[i], list[j]
}
}
list[i], list[begin] = list[begin], list[i]
return i
}``````

## Counting Sort

``````func CountingSort(data []int, maxValue int) []int {
bucketLen := maxValue + 1
bucket := make([]int, bucketLen)

sortedIndex := 0
length := len(data)

for i := 0; i < length; i++ {
bucket[data[i]] += 1
}

for j := 0; j < bucketLen; j++ {
for bucket[j] > 0 {
data[sortedIndex] = j
sortedIndex += 1
bucket[j] -= 1
}
}
return data
}``````

## Bucket Sort

Bucket sort is an improved sort algorithm of counting sort.

``````func insertionSort(data []int) {
for i := 0; i < len(data); i++ {
temp := data[i]
j := i - 1
for ; j >= 0 && data[j] > temp; j-- {
data[j+1] = data[j]
}
data[j+1] = temp
}
}

func BucketSort(data []int, bucketSize int) []int {
var max, min int
for _, n := range data {
if n < min {
min = n
}
if n > max {
max = n
}
}
nBuckets := int(max-min)/bucketSize + 1
buckets := make([][]int, nBuckets)
for i := 0; i < nBuckets; i++ {
buckets[i] = make([]int, 0)
}

for _, n := range data {
idx := int(n-min) / bucketSize
buckets[idx] = append(buckets[idx], n)
}

sorted := make([]int, 0)
for _, bucket := range buckets {
if len(bucket) > 0 {
insertionSort(bucket)
sorted = append(sorted, bucket...)
}
}

return sorted
}``````

Radix Sort is a non-comparative integer sorting algorithm. It cuts the integers into single numbers according to different digits, and then compares the numbers separately.

``````func findLargestNum(data []int) int {
largestNum := 0

for i := 0; i < len(data); i++ {
if data[i] > largestNum {
largestNum = data[i]
}
}
return largestNum
}

func RadixSort(data []int) {

largestNum := findLargestNum(data)
size := len(data)
significantDigit := 1
semiSorted := make([]int, size, size)

for largestNum/significantDigit > 0 {
bucket := [10]int{0}

for i := 0; i < size; i++ {
bucket[(data[i]/significantDigit)%10]++
}

for i := 1; i < 10; i++ {
bucket[i] += bucket[i-1]
}

for i := size - 1; i >= 0; i-- {
bucket[(data[i]/significantDigit)%10]--
semiSorted[bucket[(data[i]/significantDigit)%10]] = data[i]
}

for i := 0; i < size; i++ {
data[i] = semiSorted[i]
}

significantDigit *= 10
}
}``````

temp