lib/algo/legacy/ta_sorting.viv

# Generated by tools/algo/legacy.py from the corpus: do not edit.
# TheAlgorithms/Python's sorts and binary searches, as ported in the study corpus.
# Element comparisons are routed through lib/algo/legacy/order.viv; nothing else changes.
from algo.legacy.order import lg_eq, lg_lt

# from study/idioms/thealgorithms-python/sorting.viv: merge merge_sort partition sign quick_sort heapify heap_sort insertion_sort binary_search bisect_left search_between binary_search_by_recursion

#| sorts/merge_sort.py: split at the middle, sort each half, merge.
def merge(left: Arr, right: Arr) -> Arr {
    result = zeros(len(left) + len(right))
    i = 0.0
    j = 0.0
    for k to len(result) {
        if j < len(right) and (i == len(left) or lg_lt(right[j], left[i])) {
            result[k] = right[j]
            j += 1.0
        }
        else {
            result[k] = left[i]
            i += 1.0
        }
    }
    return result
}

def merge_sort(collection: Arr) -> Arr {
    n = len(collection)
    if n <= 1.0 {
        return collection
    }
    mid = floor(n / 2.0)
    return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:]))
}

#| The entries of `a` that compare to `pivot` as `side` says: -1 less, 0 equal, 1 greater.
#| Python writes this as three list comprehensions over a closure on `pivot`.
def partition(a: Arr, pivot, side) -> Arr {
    out = []
    for i to len(a) {
        if sign(a[i] - pivot) == side {
            out = append(out, a[i])
        }
    }
    return out
}

def sign(x) {
    if x < 0.0 {
        return -1.0
    }
    if x > 0.0 {
        return 1.0
    }
    return 0.0
}

#| sorts/quick_sort.py: a random pivot, then [*lesser, *equal, *greater].
def quick_sort(collection: Arr) -> Arr {
    if len(collection) < 2.0 {
        return collection
    }
    pivot = collection[floor(rand() * len(collection))]
    lesser = quick_sort(partition(collection, pivot, -1.0))
    greater = quick_sort(partition(collection, pivot, 1.0))
    return concat(lesser, partition(collection, pivot, 0.0), greater)
}

#| sorts/heap_sort.py: sift a[index] down a max-heap of the first heap_size entries.
def heapify(a: Arr, index, heap_size) {
    largest = index
    left = 2.0 * index + 1.0
    right = 2.0 * index + 2.0
    if left < heap_size and lg_lt(a[largest], a[left]) {
        largest = left
    }
    if right < heap_size and lg_lt(a[largest], a[right]) {
        largest = right
    }
    if largest != index {
        t = a[largest]
        a[largest] = a[index]
        a[index] = t
        heapify(a, largest, heap_size)
    }
}

def heap_sort(a: Arr) -> Arr {
    n = len(a)
    for i to floor(n / 2.0) reversed {
        heapify(a, i, n)
    }
    for i from 1.0 to n reversed {
        t = a[0]
        a[0] = a[i]
        a[i] = t
        heapify(a, 0.0, i)
    }
    return a
}

#| sorts/insertion_sort.py: shift each item left past the larger ones before it.
def insertion_sort(a: Arr) -> Arr {
    for insert_index to len(a) {
        insert_value = a[insert_index]
        j = insert_index
        while j > 0.0 and lg_lt(insert_value, a[j - 1.0]) {
            a[j] = a[j - 1.0]
            j -= 1.0
        }
        a[j] = insert_value
    }
    return a
}

#| searches/binary_search.py binary_search: the leftmost index of item, or -1.
def binary_search(sorted: Arr, item) {
    left = 0.0
    right = len(sorted) - 1.0
    result = -1.0
    while left <= right {
        mid = left + floor((right - left) / 2.0)
        if lg_eq(sorted[mid], item) {
            result = mid
            right = mid - 1.0
        }
        else if lg_lt(item, sorted[mid]) {
            right = mid - 1.0
        }
        else {
            left = mid + 1.0
        }
    }
    return result
}

#| searches/binary_search.py bisect_left: the first index whose entry is >= item.
def bisect_left(sorted: Arr, item) {
    lo = 0.0
    hi = len(sorted)
    while lo < hi {
        mid = lo + floor((hi - lo) / 2.0)
        if lg_lt(sorted[mid], item) {
            lo = mid + 1.0
        }
        else {
            hi = mid
        }
    }
    return lo
}

#| searches/binary_search.py binary_search_by_recursion.
def search_between(sorted: Arr, item, left, right) {
    if right < left {
        return -1.0
    }
    mid = left + floor((right - left) / 2.0)
    if lg_eq(sorted[mid], item) {
        leftmost = search_between(sorted, item, left, mid - 1.0)
        if leftmost != -1.0 {
            return leftmost
        }
        return mid
    }
    if lg_lt(item, sorted[mid]) {
        return search_between(sorted, item, left, mid - 1.0)
    }
    return search_between(sorted, item, mid + 1.0, right)
}

def binary_search_by_recursion(sorted: Arr, item) {
    return search_between(sorted, item, 0.0, len(sorted) - 1.0)
}