// Week 5 – Bubble sort, selection sort and insertion sort, step by step
// Run: go run ./w05/simplesorts
package main

import (
	"fmt"
	"slices"
)

// bubbleSort: swapping neighbouring pairs; if a pass has no swap, we are done.
func bubbleSort(a []int, trace bool) {
	for i := len(a) - 1; i >= 1; i-- {
		swapped := false
		for j := 0; j < i; j++ {
			if a[j] > a[j+1] {
				a[j], a[j+1] = a[j+1], a[j]
				swapped = true
			}
		}
		if trace {
			fmt.Println("  after pass:", a)
		}
		if !swapped {
			break
		}
	}
}

// selectionSort: the minimum of the unsorted part is swapped to its front.
func selectionSort(a []int, trace bool) {
	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]
		if trace {
			fmt.Printf("  step %d:     %v\n", i+1, a)
		}
	}
}

// insertionSort: the next element is inserted into the sorted beginning.
func insertionSort(a []int, trace bool) {
	for i := 1; i < len(a); i++ {
		x := a[i]
		j := i - 1
		for j >= 0 && a[j] > x {
			a[j+1] = a[j]
			j--
		}
		a[j+1] = x
		if trace {
			fmt.Printf("  step %d:     %v\n", i, a)
		}
	}
}

func main() {
	data := []int{5, 2, 8, 1, 9, 3}
	fmt.Println("Bubble sort", data)
	bubbleSort(slices.Clone(data), true)
	fmt.Println("Selection sort", data)
	selectionSort(slices.Clone(data), true)
	fmt.Println("Insertion sort", data)
	insertionSort(slices.Clone(data), true)
}