# 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.
```// Quick Sort in Golang
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
}
```
C:\golang\time>go run s2.go

--- 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]

C:\golang\time>