quick2gen_pointer_arithmetic_instead_of_array_indexing.v

import time
import rand

fn quicksort<T>(mut tab []T, left, right int) {
        pt := &T(tab.data)
        mut i := left
        mut j := right
        middle := (left + right) >> 1
        mut pivot := unsafe {*(pt + middle)}
        for {
                for unsafe {*(pt + i)} < pivot {
                        i++
                }
                for unsafe {*(pt + j)} > pivot {
                        j--
                }
                if i <= j {
                        unsafe {
                                tj := *(pt + j)
                                ti := *(pt + i)
                                mut pti := pt + i
                                mut ptj := pt + j
                                *pti = tj
                                *ptj = ti
                        }
                        i++
                        j--
                }
                if i > j {
                        break
                }
        }
        if left < j {
                quicksort<T>(mut tab, left, j)
        }
        if right > i {
                quicksort<T>(mut tab, i, right)
        }
}

mut total1 := i64(0)
mut total2 := i64(0)
for _ in 0 .. 100 {
        mut a := []int{}
        for _ in 0 .. 100000 {
                a << rand.intn(10000)
        }
        mut b := a.clone()
        //
        sw1 := time.new_stopwatch({})
        quicksort<int>(mut a, 0, a.len - 1)
        total1 += sw1.elapsed().microseconds()
        //
        sw2 := time.new_stopwatch({})
        b.sort()
        total2 += sw2.elapsed().microseconds()
        //
        assert a == b
}
println('vquicksort<T> took ${total1:8} microseconds')
println('b.sort        took ${total2:8} microseconds')
println('vquicksort/b.sort: ${f64(total1)/f64(total2)}')