quicksort_marray.fz

quicksort_marray =>

  print(T type, arr marray T) =>
    for x in arr do
      yak "$x, "
    say

  partition(T (ordered T).type, arr marray T, low i32, high i32) =>

    swap(x i32, y i32)
      =>
      tmp := arr[x]
      arr[x] := arr[y]
      arr[y] := tmp

    pivot := arr[high]
    i := mut (low - 1)
    for j in low..(high- 1) do
      if (arr[j] < pivot)
        i <- (i.get + 1)
        if i.get != j
          swap i.get j
    swap (i.get + 1) high
    (i.get + 1)

  quick_sort(T (ordered T).type, arr marray T, low i32, high i32) =>
    if (low < high)
      pi := partition T arr low high
      quick_sort arr low (pi - 1)
      quick_sort arr (pi + 1) high


  ia := (array 10 (x -> random.next_f64)).internalArray

  a := marray f64 ia.length ia

  say "unsorted"
  print a

  quick_sort a 0 (a.length - 1)

  say "sorted"
  print a