package main

import (
	"fmt"
	"math/rand"
)

func Qsort(arr []int, left, right int) {
	if left + 1 == right {
		if arr[left] > arr[right] {
			arr[left], arr[right] = arr[right], arr[left]
		}
		return
	}
	if right < left + 1 {
		return
	}

	pivot_index := left + rand.Intn(right - left + 1)
	arr[left], arr[pivot_index] = arr[pivot_index], arr[left]
	pivot := arr[left]
	index := left + 1

	for i := left + 1; i <= right; i++ {
		if arr[i] < pivot {
			arr[i], arr[index] = arr[index], arr[i]
			index++
		}
	}
	fmt.Printf("%d\n", index)
	arr[left], arr[index - 1] = arr[index - 1], arr[left]
	Qsort(arr, left, index - 1)
	Qsort(arr, index, right)
}

func main() {
	arr := []int{2, 1, 1, 5, 3, 11, 1, 1}

	Qsort(arr, 0, len(arr) - 1)

	fmt.Println(arr)
}