// 第 5 周 – 简单排序的比较
// 运行：go run ./w05/sortcompare
package main

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

var cmp, mov int // 比较次数和移动次数

func less(x, y int) bool { cmp++; return x < y }

func swap(a []int, i, j int) {
	a[i], a[j] = a[j], a[i]
	mov += 3
}

func bubble(a []int) {
	for i := len(a) - 1; i >= 1; i-- {
		swapped := false
		for j := 0; j < i; j++ {
			if less(a[j+1], a[j]) {
				swap(a, j, j+1)
				swapped = true
			}
		}
		if !swapped {
			break
		}
	}
}

func selection(a []int) {
	for i := 0; i < len(a)-1; i++ {
		min := i
		for j := i + 1; j < len(a); j++ {
			if less(a[j], a[min]) {
				min = j
			}
		}
		swap(a, i, min)
	}
}

func insertion(a []int) {
	for i := 1; i < len(a); i++ {
		x := a[i]
		mov++
		j := i - 1
		for j >= 0 && less(x, a[j]) {
			a[j+1] = a[j]
			mov++
			j--
		}
		a[j+1] = x
		mov++
	}
}

func makeData(kind string, n int, rnd *rand.Rand) []int {
	a := make([]int, n)
	for i := range a {
		switch kind {
		case "sorted":
			a[i] = i
		case "reversed":
			a[i] = n - i
		default:
			a[i] = rnd.Intn(n)
		}
	}
	return a
}

func main() {
	rnd := rand.New(rand.NewSource(42))
	names := []string{"bubble", "selection", "insertion"}
	sorters := []func([]int){bubble, selection, insertion}
	kinds := []string{"random", "sorted", "reversed"}

	n := 1000
	fmt.Println("n =", n, ": comparisons / moves")
	fmt.Printf("%-14s %22s %22s %22s\n", "", kinds[0], kinds[1], kinds[2])
	for s, sort := range sorters {
		fmt.Printf("%-14s", names[s])
		for _, k := range kinds {
			a := makeData(k, n, rnd)
			cmp, mov = 0, 0
			sort(a)
			fmt.Printf(" %10d / %9d", cmp, mov)
		}
		fmt.Println()
	}

	fmt.Println("\nTime on random data (ms) – roughly four times as much when n doubles:")
	fmt.Printf("%8s %12s %12s %12s\n", "n", "bubble", "selection", "insertion")
	for n := 2000; n <= 16000; n *= 2 {
		fmt.Printf("%8d", n)
		base := makeData("random", n, rnd)
		for _, sort := range sorters {
			a := slices.Clone(base)
			t0 := time.Now()
			sort(a)
			fmt.Printf(" %12.1f", float64(time.Since(t0).Microseconds())/1000)
		}
		fmt.Println()
	}
}