package main
import "fmt"
import "math/rand"
import "time"


func bubleSort(nums []int) {
    for i := len(nums)-1; i >= 0; i-- {
        for j := 0; j < i; j++ {
            if nums[j] > nums[j+1] {
                nums[j], nums[j+1] = nums[j+1], nums[j]
            }
        }
    }
    return 
}


func quickSort(nums [] int, start int, end int) {
    if start >= end {
        return
    }
    middle := findMiddle(nums, start, end)
    quickSort(nums, start, middle-1)
    quickSort(nums, middle+1, end)
}


func findMiddle(nums [] int, start int, end int) int {
    pivot := nums[start]
    for ;start < end; {
        
        for ; start < end && pivot <= nums[end]; {
            end -- 
        }
        
        if start < end {
            nums[start] = nums[end]
        }
        
        for ; start < end && pivot > nums[start]; {
            start ++
        }
        
        if start < end {
            nums[end] = nums[start]
        }
    }
    nums[end] = pivot
    
    return end
}


func main() {
    nums := make([] int, 0)
    rand.Seed(time.Now().UnixNano())
    for i:=0; i < 10; i++ {
        nums = append(nums, rand.Intn(100))
    }
    fmt.Println(nums)
    quickSort(nums, 0, len(nums)-1)
    fmt.Println(nums)
    
}