sort

In-place sorting of Vec<i64> (from the vec package). Uses introsort (quicksort with insertion sort for small partitions). Pure integer comparisons. Depends on vec.jda.

Usage

import vec
import sort

fn main() {
    let v = vec_new(16)
    vec_push(v, 50)
    vec_push(v, 10)
    vec_push(v, 40)
    vec_push(v, 20)
    vec_push(v, 30)

    sort_vec(v)
    // v is now [10, 20, 30, 40, 50]

    print(sort_binary_search(v, 30))   // 2
    print(sort_min(v))                 // 10
    print(sort_max(v))                 // 50
}

Function Reference

Detailed API

sort_vec

fn sort_vec(v: &i64)

Sort a vec in ascending order, in-place. Uses quicksort with a Lomuto partition scheme, falling back to insertion sort for partitions of 16 elements or fewer.

let v = vec_new(16)
vec_push(v, 3)
vec_push(v, 1)
vec_push(v, 2)
sort_vec(v)
print(vec_get(v, 0))   // 1
print(vec_get(v, 1))   // 2
print(vec_get(v, 2))   // 3

sort_vec_desc

fn sort_vec_desc(v: &i64)

Sort a vec in descending order. Internally sorts ascending then reverses.

let v = vec_new(16)
vec_push(v, 1)
vec_push(v, 3)
vec_push(v, 2)
sort_vec_desc(v)
print(vec_get(v, 0))   // 3
print(vec_get(v, 1))   // 2
print(vec_get(v, 2))   // 1

sort_is_sorted

fn sort_is_sorted(v: &i64) -> i64

Check whether a vec is sorted in ascending order.

let v = vec_new(16)
vec_push(v, 1)
vec_push(v, 2)
vec_push(v, 3)
print(sort_is_sorted(v))   // 1

vec_push(v, 0)
print(sort_is_sorted(v))   // 0

Returns: 1 if sorted ascending, 0 otherwise.

sort_reverse

fn sort_reverse(v: &i64)

Reverse a vec in-place by swapping elements from both ends toward the center.

let v = vec_new(16)
vec_push(v, 1)
vec_push(v, 2)
vec_push(v, 3)
sort_reverse(v)
print(vec_get(v, 0))   // 3
print(vec_get(v, 1))   // 2
print(vec_get(v, 2))   // 1

sort_min

fn sort_min(v: &i64) -> i64

Find the minimum element by linear scan. Returns -1 if the vec is empty.

let v = vec_new(16)
vec_push(v, 50)
vec_push(v, 10)
vec_push(v, 30)
print(sort_min(v))   // 10

sort_max

fn sort_max(v: &i64) -> i64

Find the maximum element by linear scan. Returns -1 if the vec is empty.

let v = vec_new(16)
vec_push(v, 50)
vec_push(v, 10)
vec_push(v, 30)
print(sort_max(v))   // 50

sort_binary_search

fn sort_binary_search(v: &i64, val: i64) -> i64

Perform binary search on a sorted vec. The vec must be sorted in ascending order before calling this function.

let v = vec_new(16)
vec_push(v, 10)
vec_push(v, 20)
vec_push(v, 30)
vec_push(v, 40)
vec_push(v, 50)

print(sort_binary_search(v, 30))   // 2
print(sort_binary_search(v, 25))   // -1 (not found)

Returns: Index of the value, or -1 if not found.

sort_unique

fn sort_unique(v: &i64) -> &i64

Create a new vec with duplicate values removed. The input vec must be sorted – consecutive equal elements are collapsed to one.

let v = vec_new(16)
vec_push(v, 1)
vec_push(v, 1)
vec_push(v, 2)
vec_push(v, 3)
vec_push(v, 3)

let u = sort_unique(v)
print(vec_len(u))       // 3
// u contains [1, 2, 3]

Returns: A new vec with unique values.

sort_merge

fn sort_merge(a: &i64, b: &i64) -> &i64

Merge two sorted vecs into one sorted vec. Both inputs must be sorted in ascending order.

let a = vec_new(16)
vec_push(a, 1)
vec_push(a, 3)
vec_push(a, 5)

let b = vec_new(16)
vec_push(b, 2)
vec_push(b, 4)
vec_push(b, 6)

let merged = sort_merge(a, b)
// merged contains [1, 2, 3, 4, 5, 6]
print(vec_len(merged))   // 6

Returns: A new sorted vec containing all elements from both inputs.

sort_swap

fn sort_swap(data: &i64, i: i64, j: i64)

Internal: Swap two elements at indices i and j in the raw data array.

sort_insertion

fn sort_insertion(data: &i64, lo: i64, hi: i64)

Internal: Sort the partition [lo, hi] using insertion sort. Used for small partitions (<= 16 elements) to reduce recursion overhead.

sort_partition

fn sort_partition(data: &i64, lo: i64, hi: i64) -> i64

Internal: Partition the array [lo, hi] using the Lomuto partition scheme. Returns the index of the pivot element.

sort_qs

fn sort_qs(data: &i64, lo: i64, hi: i64)

Internal: Recursive quicksort driver. Partitions the array and recursively sorts the left and right sub-arrays.

Internal Functions