// Week 5 – Solutions of the practice exercises
// Run: go run ./w05/exercises
package main

import (
	"fmt"
	"slices"
)

// E1. Is it sorted?
func isSorted(a []int) bool {
	for i := 1; i < len(a); i++ {
		if a[i-1] > a[i] {
			return false
		}
	}
	return true
}

// E2. Descending insertion sort
func insertionSortDesc(a []int) {
	for i := 1; i < len(a); i++ {
		x, j := a[i], i-1
		for j >= 0 && a[j] < x {
			a[j+1] = a[j]
			j--
		}
		a[j+1] = x
	}
}

// E3. Selection sort of strings (in Go < works for strings too)
func selectionSortStrings(a []string) {
	for i := 0; i < len(a)-1; i++ {
		min := i
		for j := i + 1; j < len(a); j++ {
			if a[j] < a[min] {
				min = j
			}
		}
		a[i], a[min] = a[min], a[i]
	}
}

// E4. Stable sort of records by score
type Student struct {
	Name  string
	Score int
}

func sortByScore(a []Student) {
	for i := 1; i < len(a); i++ {
		x, j := a[i], i-1
		for j >= 0 && a[j].Score > x.Score { // > and not >= : stable
			a[j+1] = a[j]
			j--
		}
		a[j+1] = x
	}
}

// E5. The k smallest elements: the first k steps of selection sort
func kSmallest(a []int, k int) []int {
	b := slices.Clone(a)
	for i := 0; i < k; i++ {
		min := i
		for j := i + 1; j < len(b); j++ {
			if b[j] < b[min] {
				min = j
			}
		}
		b[i], b[min] = b[min], b[i]
	}
	return b[:k]
}

// E6. Counting sort for values 0..maxValue – O(n + k)
func countingSort(a []int, maxValue int) {
	count := make([]int, maxValue+1)
	for _, v := range a {
		count[v]++
	}
	k := 0
	for v := 0; v <= maxValue; v++ {
		for ; count[v] > 0; count[v]-- {
			a[k] = v
			k++
		}
	}
}

// E7. Number of inversions (= the number of swaps of bubble sort)
func inversions(a []int) int {
	c := 0
	for i := range a {
		for j := i + 1; j < len(a); j++ {
			if a[i] > a[j] {
				c++
			}
		}
	}
	return c
}

func main() {
	fmt.Println("E1. isSorted([1 2 2 5]) =", isSorted([]int{1, 2, 2, 5}), ", isSorted([3 1]) =", isSorted([]int{3, 1}))
	d := []int{5, 2, 8, 1, 9, 3}
	insertionSortDesc(d)
	fmt.Println("E2. descending:", d)
	cities := []string{"Wuhan", "Beijing", "Shanghai", "Chengdu", "Eger"}
	selectionSortStrings(cities)
	fmt.Println("E3. cities:", cities)
	st := []Student{{"Li", 85}, {"Wang", 90}, {"Zhang", 85}, {"Chen", 70}}
	sortByScore(st)
	fmt.Println("E4. by score (stable):", st)
	fmt.Println("E5. 3 smallest:", kSmallest([]int{7, 2, 9, 4, 1, 8}, 3))
	grades := []int{3, 5, 1, 4, 5, 2, 3, 5, 4, 1}
	countingSort(grades, 5)
	fmt.Println("E6. counting sort (grades):", grades)
	fmt.Println("E7. inversions [5 2 8 1 9 3]:", inversions([]int{5, 2, 8, 1, 9, 3}))
}