Golang React JS Technology Blog

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 Bubble Sort Golang program for implementation of Huffman Coding Algorithm Golang program for implementation of Rabin-Karp Golang program for implementation of Pancake Sort Golang program for implementation of Median of Medians Golang program for implementation of Radix Sort