Notebooks · lib/algo/legacy/cmp_quicksort

lib/algo/legacy/cmp_quicksort.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–27

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# The /compare page's quicksort: Lomuto's partition around the last element.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_lt

# from study/compare/recursion/quicksort.viv: partition quicksort

def partition(a, lo, hi) {
    pivot = a[hi]
    i = lo
    for j from lo to hi {
        if lg_lt(a[j], pivot) {
            a[i], a[j] = a[j], a[i]
            i += 1
        }
    }
    a[i], a[hi] = a[hi], a[i]
    return i
}

def quicksort(a, lo, hi) {
    if lo < hi {
        p = partition(a, lo, hi)
        quicksort(a, lo, p - 1)
        quicksort(a, p + 1, hi)
    }
}