package goConcurrency

import (
	"math/rand"
	"sync"
	"time"
)

// QuickSortConcurrency 快速排序调用函数
func QuickSortConcurrency(arr []int) []int {
	// 一：校验arr是否满足排序需要，至少要有2个元素
	if arr == nil || len(arr) < 2 {
		return arr
	}

	// 四：同步的控制
	wg := &sync.WaitGroup{}
	// 二：执行排序
	// 初始排序整体[0, len(arr)-1]
	wg.Add(1)
	go quickSortConcurrency(arr, 0, len(arr)-1, wg)
	wg.Wait()

	// 三：返回结果
	return arr
}

// 实现递归快排的核心函数
// 接收arr，和排序区间的索引位置[l, r]
func quickSortConcurrency(arr []int, l, r int, wg *sync.WaitGroup) {
	// 一：-1wg的计数器
	defer wg.Done()

	// 二：判定是否需要排序， l < r
	if l < r {
		// 三：大小分区元素，并获取参考元素索引
		mid := partition(arr, l, r)

		// 四：并发对左部分排序
		wg.Add(1)
		go quickSortConcurrency(arr, l, mid-1, wg)

		// 五：并发的对右部分排序
		wg.Add(1)
		go quickSortConcurrency(arr, mid+1, r, wg)
	}
}

// 大小分区，返回参考元素索引
func partition(arr []int, l, r int) int {
	p := l - 1
	for i := l; i <= r; i++ {
		if arr[i] <= arr[r] {
			p++
			swap(arr, p, i)
		}
	}
	return p
}

// 交换arr中i和j元素
func swap(arr []int, i, j int) {
	t := arr[i]
	arr[i] = arr[j]
	arr[j] = t
}

// 生成大的随机数组
func GenerateRandArr(l int) []int {
	// 生产大量的随机数
	arr := make([]int, l)
	rand.Seed(time.Now().UnixMilli())
	for i := 0; i < l; i++ {
		arr[i] = int(rand.Int31n(int32(l * 5)))
	}

	return arr
}