Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple Quicksort in go
// Direct translation from Baeldung's implementation: https://github.com/eugenp/tutorials/blob/master/algorithms-sorting
package main
import (
"fmt"
"math/rand"
"os"
"strconv"
)
func quickSort(arr []int32, begin, end int) {
if begin < end {
partitionIndex := partition(arr, begin, end)
// Recursively sort elements of the 2 sub-arrays
quickSort(arr, begin, partitionIndex-1)
quickSort(arr, partitionIndex+1, end)
}
}
func partition(arr []int32, begin, end int) int {
pivot := arr[end]
i := (begin - 1)
for j := begin; j < end; j++ {
if arr[j] <= pivot {
i++
arr[i], arr[j] = arr[j], arr[i]
}
}
arr[i+1], arr[end] = arr[end], arr[i+1]
return i + 1
}
func main() {
// Create random array
arrLen, err := strconv.Atoi(os.Args[1])
if err != nil {
panic(err)
}
array := make([]int32, 0, arrLen)
for i := 0; i < arrLen; i++ {
array = append(array, int32(rand.Int()))
}
// Sort array
quickSort(array, 0, arrLen-1)
// Check that the array is sorted
for i := 1; i < arrLen; i++ {
if array[i-1] > array[i] {
fmt.Printf("Array not ordered in position %d: %d > %d", i,
array[i-1], array[i])
os.Exit(-1)
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.