package sort

type Comparable interface {
	CompareTo(other Comparable) bool
}

func Sort(arr []Comparable) {
	quickSort(arr, 0, len(arr)-1)
}

func quickSort(arr []Comparable, start, end int) {
	if start < end {
		i := partition(arr, start, end)
		quickSort(arr, start, i-1)
		quickSort(arr, i+1, end)
	}
}

func partition(arr []Comparable, start, end int) int {
	var key = arr[end]
	var i = start
	for j := start; j < end; j++ {
		if arr[j].CompareTo(key) {
			arr[j], arr[i] = arr[i], arr[j]
			i++
		}
	}
	arr[i], arr[end] = arr[end], arr[i]
	return i
}

//type Comparator interface {
//	Compare(o1 interface{}, o2 interface{}) bool
//}

type Comparator func(o1 interface{}, o2 interface{}) bool

func SortBy(arr []interface{}, comparator Comparator) {
	quickSortBy(arr, 0, len(arr)-1, comparator)
}

func quickSortBy(arr []interface{}, start, end int, comparator Comparator) {
	if start < end {
		i := partitionBy(arr, start, end, comparator)
		quickSortBy(arr, start, i-1, comparator)
		quickSortBy(arr, i+1, end, comparator)
	}
}

func partitionBy(arr []interface{}, start, end int, comparator Comparator) int {
	var key = arr[end]
	var i = start
	for j := start; j < end; j++ {
		if comparator(arr[j], key) {
			arr[j], arr[i] = arr[i], arr[j]
			i++
		}
	}
	arr[i], arr[end] = arr[end], arr[i]
	return i
}