// V1.go

package quicksort

type v1 struct{}

func QuickSortV1(list []int) []int {

	if len(list) <= 1 {

		return list

	}

	v1{}.quicksort(list, 0, len(list)-1)

	return list

}

func (v v1) quicksort(list []int, low, high int) {

	if low >= high {

		return

	}

	p := v.partion(list, low, high)

	v.quicksort(list, low, p-1)

	v.quicksort(list, p+1, high)

}

func (v1) partion(list []int, low, high int) int {

	p := list[low]

	// 移动左右指针

	for low < high {

		// 从高的地方，找到小于 p 的值，迁移

		for low < high && p <= list[high] {

			high--

		}

		list[low] = list[high]

		// fmt.Println(low, high, list)

		// 从低的地方，找到大于 p 的值，迁移

		for low < high && p >= list[low] {

			low++

		}

		list[high] = list[low]

		// fmt.Println(low, high, list)

	}

	// 插入 p

	list[low] = p

	// fmt.Println(low, high, list)

	// fmt.Println("====")

	return low

}

// v1_test.go

package quicksort

import (

	"fmt"

	"math/rand"

	"testing"

)

func TestQuickSortV1(t *testing.T) {

	list := []int{6, 5, 7, 9, 8, 3, 4}

	// list := []int{1, 6, 5, 7, 9, 8, 3, 4}

	list = QuickSortV1(list)

	fmt.Println(list)

}

func BenchmarkQuickSortV1(b *testing.B) {

	// list := []int{6, 5, 7, 9, 8, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4}

	list := make([]int, 0, 1000)

	for i := 0; i < 1000; i++ {

		list = append(list, rand.Intn(10000))

	}

	for i := 0; i < b.N; i++ {

		list = QuickSortV1(list)

	}

}

// v2.go

package quicksort

import "sync"

type v2 struct {

}

func QuickSortV2(list []int) []int {

	if len(list) <= 1 {

		return list

	}

	v := v2{}

	v.quicksort(list)

	return list

}

func (v v2) quicksort(list []int) {

	low := 0

	high := len(list) - 1

	if low >= high {

		return

	}

	p := v.partion(list)

	var wg sync.WaitGroup

	wg.Add(2)

	go func() {

		defer wg.Done()

		v.quicksort(list[:p])

	}()

	go func() {

		defer wg.Done()

		v.quicksort(list[p+1:])

	}()

	wg.Wait()

}

func (v v2) partion(list []int) int {

	low := 0

	high := len(list) - 1

	p := list[low]

	// fmt.Println(low, high, list)

	// 移动左右指针

	for low < high {

		// 从高的地方，找到小于 p 的值，迁移

		for low < high && p <= list[high] {

			high--

		}

		list[low] = list[high]

		// fmt.Println(low, high, list)

		// 从低的地方，找到大于 p 的值，迁移

		for low < high && p >= list[low] {

			low++

		}

		list[high] = list[low]

		// fmt.Println(low, high, list)

	}

	// 插入 p

	list[low] = p

	// fmt.Println(low, high, list)

	// fmt.Println("====")

	return low

}

// v2_test.go

package quicksort

import (

	"fmt"

	"math/rand"

	"testing"

)

func TestQuickSortV2(t *testing.T) {

	// list := []int{6, 5, 7, 9, 8, 3, 4}

	// list = QuickSortV2(list)

	// // time.Sleep(time.Second * 1)

	// fmt.Println(list)

	list := make([]int, 0, 1000)

	for i := 0; i < 1000; i++ {

		list = append(list, rand.Intn(10000))

	}

	list = QuickSortV2(list)

	fmt.Println(list)

}

func BenchmarkQuickSortV2(b *testing.B) {

	list := make([]int, 0, 1000)

	for i := 0; i < 1000; i++ {

		list = append(list, rand.Intn(10000))

	}

	for i := 0; i < b.N; i++ {

		list = QuickSortV2(list)

	}

}