Notebooks · lib/algo/legacy/bench_qsort

lib/algo/legacy/bench_qsort.viv

Look inside this program

Atlas
The program’s map: every function and which calls which.
There’s no recorded run of this program yet.

Shift+Enter in a cell runs it and moves to the next. Running a cell runs every cell above it too, as one program.

[1]lines 1–42

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The Julia microbenchmark's quicksort (Hoare-style, middle pivot) and issorted.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_gt, lg_lt

# from study/benchmarks/viv/micro/quicksort.viv: qsort issorted

def qsort(a: Arr, lo, hi) {
    i = lo
    j = hi
    while i < hi {
        pivot = a[(lo + hi) // 2]
        while i <= j {
            while lg_lt(a[i], pivot) {
                i = i + 1
            }
            while lg_gt(a[j], pivot) {
                j = j - 1
            }
            if i <= j {
                a[i], a[j] = a[j], a[i]
                i = i + 1
                j = j - 1
            }
        }
        if lo < j {
            qsort(a, lo, j)
        }
        lo = i
        j = hi
    }
    return a
}

def issorted(a: Arr) {
    for k from 1 to len(a) {
        if lg_gt(a[k - 1], a[k]) {
            return false
        }
    }
    return true
}

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The Julia microbenchmark's quicksort (Hoare-style, middle pivot) and issorted.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_gt, lg_lt

# from study/benchmarks/viv/micro/quicksort.viv: qsort issorted

def qsort(a: Arr, lo, hi) {
    i = lo
    j = hi
    while i < hi {
        pivot = a[(lo + hi) // 2]
        while i <= j {
            while lg_lt(a[i], pivot) {
                i = i + 1
            }
            while lg_gt(a[j], pivot) {
                j = j - 1
            }
            if i <= j {
                a[i], a[j] = a[j], a[i]
                i = i + 1
                j = j - 1
            }
        }
        if lo < j {
            qsort(a, lo, j)
        }
        lo = i
        j = hi
    }
    return a
}

def issorted(a: Arr) {
    for k from 1 to len(a) {
        if lg_gt(a[k - 1], a[k]) {
            return false
        }
    }
    return true
}