package main

import (
	"fmt"
)

func insert_sort(array []int) int {
	l := len(array)
	for i := 1; i < l; i++ {
		for j := i; j > 0; j-- {
			if array[j] < array[j-1] {
				array[j], array[j-1] = array[j-1], array[j]
			}
		}
	}
	return 0
}

func bubbling_sort(array []int) int {

	l := len(array)
	for i := l; i > 0; i-- {
		for j := 1; j < i; j++ {
			if array[j] < array[j-1] {
				array[j], array[j-1] = array[j-1], array[j]
			}
		}
	}
	return 0
}

func create_heap(array []int) {
	i := len(array) - 1
	for i > 0 {
		j := i
		i = (i+1)/2 - 1
		if array[i] < array[j] {
			array[i], array[j] = array[j], array[i]
		} else {
			break
		}
	}
	return
}

func pop_heap(array []int) int {
	l := len(array) - 1
	array[0], array[l] = array[l], array[0]
	i := 0
	for i < l {
		if ((i+1)*2 >= l) && ((2*(i+1) - 1) < l) {
			if array[i] < array[2*(i+1)-1] {
				array[i], array[2*(i+1)-1] = array[2*(i+1)-1], array[i]
				i = 2*(i+1) - 1
			}
			break
		} else if ((i+1)*2 - 1) >= l {
			break
		} else if array[2*(i+1)-1] > array[i] || array[2*(i+1)] > array[i] {
			if array[2*(i+1)-1] < array[2*(i+1)] {
				array[i], array[2*(i+1)] = array[2*(i+1)], array[i]
				i = 2 * (i + 1)
			} else {
				array[i], array[2*(i+1)-1] = array[2*(i+1)-1], array[i]
				i = 2*(i+1) - 1
			}
		} else {
			break
		}
	}

	return array[l]
}

func heap_sort(array []int) {
	l := len(array)
	for i := 2; i <= l; i++ {
		create_heap(array[:i])
	}
	for j := 0; j < l; j++ {
		pop_heap(array[:l-j])
	}
}

func qprocess(array []int) {

}

func quick_sort(array []int) {

	l := len(array)
	if l <= 1 {
		return
	}
	p := 0
	h := 0
	t := l - 1
	v := array[p]
	for h < t {
		for h < t && v < array[t] {
			t--
		}
		if h < t {
			array[p] = array[t]
			p = t
			h++
		}

		for h < t && v > array[h] {
			h++
		}
		if h < t {
			array[p] = array[h]
			p = h
			t--
		}

	}
	array[p] = v
	fmt.Println(array)
	quick_sort(array[:p])
	quick_sort(array[p+1:])

}

func main() {
	array := []int{5, 4, 8, 6, 1, 7, 3, 2, 0}
	fmt.Println("[begin]", array)
	quick_sort(array)
	fmt.Println("[end  ]", array)
}