// 5. hét – A gyakorlati feladatok megoldásai
// Futtatás: go run ./h05/exercises
package main

import (
	"fmt"
	"slices"
)

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

// F2. Csökkenő beszúrásos rendezés
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
	}
}

// F3. Stringek kiválasztásos rendezése (Go-ban a < stringekre is működik)
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]
	}
}

// F4. Rekordok stabil rendezése pontszám szerint
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 { // > és nem >= : stabil
			a[j+1] = a[j]
			j--
		}
		a[j+1] = x
	}
}

// F5. A k legkisebb elem: a kiválasztásos rendezés első k lépése
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]
}

// F6. Számláló rendezés 0..maxValue értékekre – 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++
		}
	}
}

// F7. Inverziók száma (= a buborékrendezés cseréinek száma)
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("F1. 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("F2. csökkenő:", d)
	cities := []string{"Wuhan", "Beijing", "Shanghai", "Chengdu", "Eger"}
	selectionSortStrings(cities)
	fmt.Println("F3. városok:", cities)
	st := []Student{{"Li", 85}, {"Wang", 90}, {"Zhang", 85}, {"Chen", 70}}
	sortByScore(st)
	fmt.Println("F4. pontszám szerint (stabil):", st)
	fmt.Println("F5. 3 legkisebb:", 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("F6. számláló rendezés (jegyek):", grades)
	fmt.Println("F7. inverziók [5 2 8 1 9 3]:", inversions([]int{5, 2, 8, 1, 9, 3}))
}