quick_sort.go

package main

import (
	"fmt"
	"math/rand"
)

func main() {
	// Get the number of items and maximum item value.
	var numItems, max int
	fmt.Printf("# Items: ")
	fmt.Scanln(&numItems)
	fmt.Printf("Max: ")
	fmt.Scanln(&max)

	// Make and display the unsorted slice.
	slice := makeRandomSlice(numItems, max)
	printSlice(slice, 40)
	fmt.Println()

	// Sort and display the result.
	quicksort(slice)
	printSlice(slice, 40)

	// Verify that it's sorted.
	checkSorted(slice)
}

func partition(nums []int, low, high int) int {
	pivot := nums[high]
	i := low - 1

	for j := low; j < high; j++ {
		if nums[j] < pivot {
			i++
			nums[i], nums[j] = nums[j], nums[i]
		}
	}

	nums[i+1], nums[high] = nums[high], nums[i+1]
	return i + 1
}

func quicksort(nums []int) {
	if len(nums) < 2 {
		return
	}
	pi := partition(nums, 0, len(nums)-1)

	quicksort(nums[:pi])
	quicksort(nums[pi+1:])
}

func makeRandomSlice(numItems, max int) []int {
	newSlice := make([]int, numItems)
	for i := 0; i < numItems; i++ {
		newSlice[i] = rand.Intn(max)
	}
	return newSlice
}

func printSlice(slice []int, numItems int) {
	if numItems > len(slice) {
		numItems = len(slice)
	}
	for i := 0; i < numItems; i++ {
		fmt.Printf("Index: %d, Value: %d\n", i, slice[i])
	}
}

func checkSorted(slice []int) {
	for i := 0; i < len(slice)-1; i++ {
		if slice[i] > slice[i+1] {
			fmt.Println("Not sorted")
			return
		}
	}
	fmt.Println("Sorted")
}