v / examples
Raw file | 42 loc (38 sloc) | 973 bytes | Latest commit hash ef5be22f8
1import rand
2
3const (
4 gen_len = 1000 // how many random numbers to generate
5 gen_max = 10000 // max of the generated numbers
6)
7
8fn main() {
9 mut arr := []int{}
10 for _ in 0 .. gen_len {
11 arr << rand.intn(gen_max) or { 0 }
12 }
13 println('length of random array is ${arr.len}')
14 println('before quick sort whether array is sorted: ${is_sorted[int](arr)}')
15 quick_sort[int](mut arr, 0, arr.len - 1)
16 println('after quick sort whether array is sorted: ${is_sorted[int](arr)}')
17}
18
19fn quick_sort[T](mut arr []T, l int, r int) {
20 if l >= r {
21 return
22 }
23 mut sep := l // what is sep: [...all_value<arr[sep]...sep...all_value>=arr[sep]...]
24 for i in l + 1 .. r + 1 {
25 if arr[i] < arr[l] {
26 sep++
27 arr[i], arr[sep] = arr[sep], arr[i]
28 }
29 }
30 arr[l], arr[sep] = arr[sep], arr[l]
31 quick_sort[T](mut arr, l, sep - 1)
32 quick_sort[T](mut arr, sep + 1, r)
33}
34
35fn is_sorted[T](arr []T) bool {
36 for i in 0 .. arr.len - 1 {
37 if arr[i] > arr[i + 1] {
38 return false
39 }
40 }
41 return true
42}