// Week 13 – Quicksort with Lomuto partitioning
// Run: go run ./w13/quicksort
package main

import (
	"fmt"
	"math"
	"math/rand"
	"slices"
)

var comparisons int
var rnd = rand.New(rand.NewSource(7))

func quickSort(a []int, lo, hi int, randomPivot bool) {
	if lo >= hi {
		return
	}
	if randomPivot {
		r := lo + rnd.Intn(hi-lo+1)
		a[r], a[hi] = a[hi], a[r]
	}
	p := partition(a, lo, hi)
	quickSort(a, lo, p-1, randomPivot)
	quickSort(a, p+1, hi, randomPivot)
}

// partition: pivot = a[hi]; smaller ones to the left, larger or equal ones to the right
func partition(a []int, lo, hi int) int {
	pivot := a[hi]
	i := lo - 1
	for j := lo; j < hi; j++ {
		comparisons++
		if a[j] < pivot {
			i++
			a[i], a[j] = a[j], a[i]
		}
	}
	a[i+1], a[hi] = a[hi], a[i+1]
	return i + 1
}

func main() {
	a := []int{7, 2, 9, 4, 3, 8, 6}
	b := slices.Clone(a)
	p := partition(b, 0, len(b)-1)
	fmt.Println("partition([7 2 9 4 3 8 6]) ->", b, ", pivot index:", p)
	quickSort(a, 0, len(a)-1, false)
	fmt.Println("quickSort ->", a)

	n := 5000
	sorted := make([]int, n)
	for i := range sorted {
		sorted[i] = i
	}
	comparisons = 0
	quickSort(slices.Clone(sorted), 0, n-1, false)
	fmt.Printf("\nsorted input, n = %d, fixed pivot:  %10d comparisons (≈ n²/2 = %d)\n", n, comparisons, n*n/2)
	comparisons = 0
	quickSort(slices.Clone(sorted), 0, n-1, true)
	fmt.Printf("sorted input, n = %d, random pivot: %10d comparisons (≈ 1.39·n·log₂n = %d)\n", n, comparisons,
		int(1.39*float64(n)*math.Log2(float64(n))))
}