quicksort exp

qsort.go

package main

import (
	"fmt"
	"math/rand"
	"sort"
	"time"
)

var myrand *rand.Rand

func init() {
	myrand = rand.New(rand.NewSource(time.Now().Unix()))
}

const cutoff = 25

func lomuto(nums []int) int {
	len := len(nums)
	pivot := nums[0]
	m := 0
	for i := 1; i < len; i++ {
		if nums[i] < pivot {
			m++
			nums[i], nums[m] = nums[m], nums[i]
		}
	}
	nums[0], nums[m] = nums[m], nums[0]
	return m
}

func qsort1Way(nums []int) {
	if len(nums) <= 1 {
		return
	}
	i := lomuto(nums)
	qsort1Way(nums[0:i])
	qsort1Way(nums[i+1:])
}

func partition2Way(nums []int) int {
	pivot := nums[0]
	i := 0
	len := len(nums)
	j := len
	for {
		i++
		j--
		for nums[i] < pivot && i < len-1 {
			i++
		}
		for pivot < nums[j] {
			j--
		}
		if i >= j {
			break
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[0], nums[j] = nums[j], nums[0]
	return j
}

func partition2WayWithSentinel(nums []int) int {
	pivot := nums[0]
	i := 0
	len := len(nums)
	j := len
	{
		max := pivot
		maxi := 0
		for i := 1; i < len; i++ {
			if max < nums[i] {
				max = nums[i]
				maxi = i
			}
		}
		nums[maxi], nums[len-1] = nums[len-1], nums[maxi]
	}
	for {
		i++
		j--
		for nums[i] < pivot {
			i++
		}
		for pivot < nums[j] {
			j--
		}
		if i >= j {
			break
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[0], nums[j] = nums[j], nums[0]
	return j
}

func partition2WayRandomPivot(nums []int) int {
	{
		i := randRange(0, len(nums)-1)
		nums[0], nums[i] = nums[i], nums[0]
	}
	pivot := nums[0]
	i := 0
	len := len(nums)
	j := len
	for {
		i++
		j--
		for nums[i] < pivot && i < len-1 {
			i++
		}
		for pivot < nums[j] {
			j--
		}
		if i >= j {
			break
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[0], nums[j] = nums[j], nums[0]
	return j
}

func partition2WayMedian3(nums []int, lo, hi int) int {
	//median of 3
	m := lo + (hi-lo)/2
	if nums[m] < nums[lo] {
		nums[m], nums[lo] = nums[lo], nums[m]
	}
	if nums[hi] < nums[lo] {
		nums[hi], nums[lo] = nums[lo], nums[hi]
	}
	if nums[hi] < nums[m] {
		nums[hi], nums[m] = nums[m], nums[hi]
	}
	nums[m], nums[lo] = nums[lo], nums[m]

	pivot := nums[lo]
	i := lo
	j := hi + 1
	for {
		i++
		j--
		for nums[i] < pivot {
			i++
		}
		for pivot < nums[j] {
			j--
		}
		if i >= j {
			break
		}
		nums[i], nums[j] = nums[j], nums[i]
	}
	nums[lo], nums[j] = nums[j], nums[lo]
	return j
}

func qsort2Way(nums []int) {
	if len(nums) <= 1 {
		return
	}
	j := partition2Way(nums)
	qsort2Way(nums[0:j])
	qsort2Way(nums[j+1:])
}

func qsort2WayRand(nums []int) {
	if len(nums) <= 1 {
		return
	}
	j := partition2WayRandomPivot(nums)
	qsort2Way(nums[0:j])
	qsort2Way(nums[j+1:])
}

func qsort2WayMedian3(nums []int) {
	size := len(nums)
	if size <= 1 {
		return
	}
	i := partition2WayMedian3(nums, 0, size-1)
	qsort2WayMedian3(nums[0:i])
	qsort2WayMedian3(nums[i+1:])
}

func qsort2WayMedian3CutOff(nums []int) {
	size := len(nums)
	if size <= cutoff {
		insertSort(nums)
		return
	}
	i := partition2WayMedian3(nums, 0, size-1)
	qsort2WayMedian3CutOff(nums[0:i])
	qsort2WayMedian3CutOff(nums[i+1:])
}

func partition3Way1(nums []int) (int, int) {
	lt := 0
	i := 1
	gt := len(nums) - 1
	pivot := nums[0]
	const (
		LESS = iota
		EQUAL
		GREAT
	)
	cmp := func(a, b int) int {
		if a == b {
			return EQUAL
		} else if a < b {
			return LESS
		} else {
			return GREAT
		}
	}
	for i <= gt {
		switch cmp(nums[i], pivot) {
		case LESS:
			nums[lt], nums[i] = nums[i], nums[lt]
			i++
			lt++
		case GREAT:
			nums[gt], nums[i] = nums[i], nums[gt]
			gt--
		case EQUAL:
			i++
		}
	}
	return lt - 1, gt + 1
}

func qsort3Way1(nums []int) {
	if len(nums) <= 1 {
		return
	}
	lt, gt := partition3Way1(nums)
	qsort3Way1(nums[0 : lt+1])
	qsort3Way1(nums[gt:])
}

func partition3Way2(nums []int) (int, int) {
	pivot := nums[0]
	len := len(nums)
	i := 0
	j := len
	p := 0
	q := len
	for {
		i++
		j--
		for nums[i] < pivot && i < len-1 {
			i++
		}
		for pivot < nums[j] {
			j--
		}
		if i >= j {
			break
		}
		nums[i], nums[j] = nums[j], nums[i]
		if nums[i] == pivot {
			p++
			nums[i], nums[p] = nums[p], nums[i]
		}
		if nums[j] == pivot {
			q--
			nums[q], nums[j] = nums[j], nums[q]
		}
	}
	nums[0], nums[j] = nums[j], nums[0]

	mlo := j - 1
	mhi := j + 1
	for k := 1; k <= p; k, mlo = k+1, mlo-1 {
		nums[k], nums[mlo] = nums[mlo], nums[k]
	}
	for k := len - 1; k >= q; k, mhi = k-1, mhi+1 {
		nums[k], nums[mhi] = nums[mhi], nums[k]
	}
	return mlo, mhi
}

func partition3Way2Median3(nums []int) (int, int) {
	//median of 3
	r := len(nums) - 1
	m := r / 2
	if nums[m] < nums[0] {
		nums[m], nums[0] = nums[0], nums[m]
	}
	if nums[r] < nums[0] {
		nums[r], nums[0] = nums[0], nums[r]
	}
	if nums[r] < nums[m] {
		nums[r], nums[m] = nums[m], nums[r]
	}
	nums[m], nums[0] = nums[0], nums[m]

	pivot := nums[0]
	len := len(nums)
	i := 0
	j := r + 1
	p := 0
	q := j
	for {
		i++
		j--
		for nums[i] < pivot {
			i++
		}
		for pivot < nums[j] {
			j--
		}
		if i >= j {
			break
		}
		nums[i], nums[j] = nums[j], nums[i]
		if nums[i] == pivot {
			p++
			nums[i], nums[p] = nums[p], nums[i]
		}
		if nums[j] == pivot {
			q--
			nums[q], nums[j] = nums[j], nums[q]
		}
	}
	nums[0], nums[j] = nums[j], nums[0]

	mlo := j - 1
	mhi := j + 1
	for k := 1; k <= p; k, mlo = k+1, mlo-1 {
		nums[k], nums[mlo] = nums[mlo], nums[k]
	}
	for k := len - 1; k >= q; k, mhi = k-1, mhi+1 {
		nums[k], nums[mhi] = nums[mhi], nums[k]
	}
	return mlo, mhi
}

func qsort3Way2(nums []int) {
	len := len(nums)
	if len <= 1 {
		return
	}
	mlo, mhi := partition3Way2(nums)
	if mlo > 0 {
		qsort3Way2(nums[0 : mlo+1])
	}
	if mhi < len-1 {
		qsort3Way2(nums[mhi:])
	}
}

func qsort3Way2Median3(nums []int) {
	len := len(nums)
	if len <= 1 {
		return
	}
	mlo, mhi := partition3Way2Median3(nums)
	if mlo > 0 {
		qsort3Way2Median3(nums[0 : mlo+1])
	}
	if mhi < len-1 {
		qsort3Way2Median3(nums[mhi:])
	}
}

func qsort3Way2Median3CutOff(nums []int) {
	len := len(nums)
	if len <= cutoff {
		insertSort(nums)
		return
	}
	mlo, mhi := partition3Way2Median3(nums)
	if mlo > 0 {
		qsort3Way2Median3CutOff(nums[0 : mlo+1])
	}
	if mhi < len-1 {
		qsort3Way2Median3CutOff(nums[mhi:])
	}
}

func qsort(nums []int) {
	size := len(nums)
	if size <= cutoff {
		insertSort(nums)
		return
	}
	var stack [128]int
	top := -1
	top++
	stack[top] = size - 1
	top++
	stack[top] = 0
	for top > 0 {
		lo := stack[top]
		top--
		hi := stack[top]
		top--

		if hi-lo+1 <= cutoff {
			insertSort(nums[lo : hi+1])
			continue
		}

		i := partition2WayMedian3(nums, lo, hi)
		lsize := i - lo
		rsize := hi - i

		if lsize > rsize {
			top++
			stack[top] = i - 1
			top++
			stack[top] = lo
			top++
			stack[top] = hi
			top++
			stack[top] = i + 1

		} else {
			top++
			stack[top] = hi
			top++
			stack[top] = i + 1
			top++
			stack[top] = i - 1
			top++
			stack[top] = lo
		}
	}
}

func makeRandInts(len, max int) []int {
	nums := make([]int, 0, len)
	for i := 0; i < len; i++ {
		nums = append(nums, myrand.Intn(max))
	}
	return nums
}

func makeAscInts(len, max int) []int {
	nums := makeRandInts(len, max)
	sort.Slice(nums, func(i, j int) bool {
		return nums[i] < nums[j]
	})
	return nums
}

func makeDup(len int) []int {
	max := 0
	if len <= 10 {
		max = len / 2
	} else {
		max = 10
	}
	return makeRandInts(len, max)
}

func makeDesInts(len, max int) []int {
	nums := makeRandInts(len, max)
	sort.Slice(nums, func(i, j int) bool {
		return nums[j] < nums[i]
	})
	return nums
}

func makeUnique(len int) []int {
	nums := make([]int, 0, len)
	for i := 0; i < len; i++ {
		nums = append(nums, i)
	}
	myrand.Shuffle(len, func(i, j int) {
		nums[i], nums[j] = nums[j], nums[i]
	})
	return nums
}

func randRange(min, max int) int {
	return min + myrand.Int()%(max-min+1)
}

func insertSort(nums []int) {
	last := len(nums) - 1
	for i := last; i > 0; i-- {
		if nums[i-1] > nums[i] {
			nums[i-1], nums[i] = nums[i], nums[i-1]
		}
	}
	//now nums[0] is minimum element
	for i := 2; i <= last; i++ {
		j := i
		v := nums[i]
		for ; v < nums[j-1]; j-- {
			nums[j] = nums[j-1]
		}
		nums[j] = v
	}
}

func main() {
	//data := makeRandInts(1e7, 1e7)
	//data := makeAscInts(1e7, 1e7)
	data := makeDesInts(1e7, 1e7)
	nums := make([]int, 1e7)

	copy(nums, data)
	b := time.Now()
	sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
	fmt.Printf("stdlib use: %+v\n", time.Since(b))

	copy(nums, data)
	b = time.Now()
	qsort2WayMedian3CutOff(nums)
	fmt.Printf("qsort2WayMedian3CutOff use: %+v\n", time.Since(b))
}

qsort_test.go

package main

import (
	"os"
	"sort"
	"strconv"
	"testing"
)

var size int

func init() {
	sizeStr := os.Getenv("SIZE")
	if sizeStr == "" {
		size = 1e4
	} else if f, err := strconv.ParseFloat(sizeStr, 64); err != nil {
		size = 1e4
	} else {
		size = int(f)
	}
	if size <= 0 {
		size = 1e1
	}
}

func bench(b *testing.B, size, max int, algo func([]int), name string) {
	benchs := []struct {
		inputType string
		input     []int
	}{
		{"randint", makeRandInts(size, max)},
		{"ascint", makeAscInts(size, max)},
		{"desint", makeDesInts(size, max)},
		{"unique", makeUnique(size)},
		{"duplicate", makeDup(size)},
	}
	for _, bm := range benchs {
		b.Run(bm.inputType, func(b *testing.B) {
			ns := make([]int, len(bm.input))
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				copy(ns, bm.input)
				//b.StartTimer()
				algo(ns)
				//b.StopTimer()
				if !sort.IntsAreSorted(ns) {
					b.Fatalf("sort error in algo %s\n", name)
				}
			}
		})
	}
}

func BenchmarkInsert(b *testing.B) {
	bench(b, size, size, insertSort, "insertSort")
}

func Benchmark1Way(b *testing.B) {
	bench(b, size, size, qsort1Way, "qsort1Way")
}

func Benchmark2Way(b *testing.B) {
	bench(b, size, size, qsort2Way, "qsort2Way")
}

func Benchmark2WayRand(b *testing.B) {
	bench(b, size, size, qsort2WayRand, "qsort2WayRand")
}

func Benchmark2WayMedian3(b *testing.B) {
	bench(b, size, size, qsort2WayMedian3, "qsort2WayMedian3")
}

func Benchmark2WayMedian3CutOff(b *testing.B) {
	bench(b, size, size, qsort2WayMedian3CutOff, "qsort2WayMedian3CutOff")
}

func Benchmark2WayMedian3CutOffNonRecur(b *testing.B) {
	bench(b, size, size, qsort, "qsort")
}

func Benchmark3Way1(b *testing.B) {
	bench(b, size, size, qsort3Way1, "qsort3Way1")
}

func Benchmark3Way2(b *testing.B) {
	bench(b, size, size, qsort3Way2, "qsort3Way2")
}

func Benchmark3Way2Median3(b *testing.B) {
	bench(b, size, size, qsort3Way2Median3, "qsort3Way2Median3")
}

func Benchmark3Way2Median3CutOff(b *testing.B) {
	bench(b, size, size, qsort3Way2Median3CutOff, "qsort3Way2Median3CutOff")
}

func BenchmarkStdLib(b *testing.B) {
	bench(b, size, size, func(nums []int) {
		sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] })
	}, "stdlib")
}