quicksort_marray.fz

quicksort_marray =>

  # NYI this is broken currently

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

  partition(T type : property.orderable, arr Mutable_Array 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 type : property.orderable, arr Mutable_Array 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

  mi : mutate is
  mi.go ()->

    a := (mutate.array f64).type.new mi 10 0.0
    for i in a.indices do
      a[i] := random.next_f64


    say "unsorted"
    print a

    quick_sort a 0 (a.count - 1)

    say "sorted"
    print a