1 | import rand |
2 | |
3 | const ( |
4 | gen_len = 1000 // how many random numbers to generate |
5 | gen_max = 10000 // max of the generated numbers |
6 | ) |
7 | |
8 | fn 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 | |
19 | fn 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 | |
35 | fn 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 | } |