Sorting Problems

sort.go

package main

import (
	"fmt"
)

func main() {
	l := []int{1, -20, 7, 6, 0, 9}
	quicksort(l, 0, 6)
	fmt.Println(l)
}

func partition2(data []int, l, r int) int {
	m := (r - l) / 2
	x := data[m]
	i := l
	j := r - 1
	for i <= j {
		for ; data[i] <= x; i++ {
		}
		for ; data[j] > x; j-- {
		}
		if i > j {
			break
		}
		data[i], data[j] = data[j], data[i]
		i++
		j--
	}
	fmt.Println("@", l, r, m, data, i)
	return i
}

func partition(data []int, l, r int) int {
	x := data[l] // pivot
	j := l
	for i := l + 1; i < r; i++ {
		if data[i] <= x {
			j++
			data[j], data[i] = data[i], data[j]
		}
	}
	data[j], data[l] = data[l], data[j]
	fmt.Println("@", l, r, data, j)
	return j
}

func quicksort(data []int, l, r int) {
	if l >= r {
		return
	}
	m := partition2(data, l, r)
	if m-1 > l {
	quicksort(data, l, m)
	}
	quicksort(data, m+1, r)
}

func insertionSort(data []int, l, r int) {
	for i := l + 1; i < r; i++ {
		for j := i; j > l && data[j-1] > data[j]; j-- {
			data[j], data[j-1] = data[j-1], data[j]
		}
	}
}