// 第 5 周 – 冒泡排序、选择排序和插入排序，逐步演示
// 运行：go run ./w05/simplesorts
package main

import (
	"fmt"
	"slices"
)

// bubbleSort：交换相邻的元素对；如果某一趟没有交换，就完成了。
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：把未排序部分的最小值交换到它的最前面。
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：把下一个元素插入到前面的有序部分。
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)
}