Golang program for implementation of Quick Sort
The quick sort algorithm falls under the divide and conquer class of algorithms, where we break (divide) a problem into smaller chunks that are much simpler to solve (conquer). In this case, an unsorted array is broken into sub-arrays that are partially sorted, until all elements in the list are in the right position, by which time our unsorted list will have become sorted.
Example
package main
import (
"fmt"
"math/rand"
"time"
)
func main() {
slice := generateSlice(20)
fmt.Println("\n--- Unsorted --- \n\n", slice)
quicksort(slice)
fmt.Println("\n--- Sorted ---\n\n", slice, "\n")
}
// Generates a slice of size, size filled with random numbers
func generateSlice(size int) []int {
slice := make([]int, size, size)
rand.Seed(time.Now().UnixNano())
for i := 0; i < size; i++ {
slice[i] = rand.Intn(999) - rand.Intn(999)
}
return slice
}
func quicksort(a []int) []int {
if len(a) < 2 {
return a
}
left, right := 0, len(a)-1
pivot := rand.Int() % len(a)
a[pivot], a[right] = a[right], a[pivot]
for i, _ := range a {
if a[i] < a[right] {
a[left], a[i] = a[i], a[left]
left++
}
}
a[left], a[right] = a[right], a[left]
quicksort(a[:left])
quicksort(a[left+1:])
return a
}
Output
--- Unsorted ---
[-317 -381 -14 -215 -590 -243 -412 380 -312 925 158 -46 177 22 -482 273 217 514 -392 424]
--- Sorted ---
[-590 -482 -412 -392 -381 -317 -312 -243 -215 -46 -14 22 158 177 217 273 380 424 514 925]
Most Helpful This Week
Golang program for implementation of Floyd–Warshall Algorithm
Golang program for implementation of Comb Sort
Golang program for implementation of Insertion Sort
Golang program for implementation of AVL Trees
Golang program to implement Binary Tree
Golang program for implementation of Linked List
Golang program to print a matrix in Spiral Format
Golang program for implementation of Median of Medians
Golang program to generate number of slices permutations of number entered by user
Golang program for implementation of Bubble Sort