Putting It Together

Let's combine everything we've learned into a complete program: Quicksort.

The Algorithm

Quicksort is a classic divide-and-conquer sorting algorithm:

1. Pick a "pivot" element
2. Partition the array so elements less than the pivot come before it
3. Recursively sort the left and right partitions

The Implementation

fn partition(arr: MutRef([i32; 5]), lo: usize, hi: usize) -> usize {
    let pivot = arr[hi];
    let mut i = lo;
    let mut j = lo;

    while j < hi {
        if arr[j] <= pivot {
            // Swap arr[i] and arr[j]
            let tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i = i + 1;
        }
        j = j + 1;
    }

    // Move pivot to its final position
    let tmp = arr[i];
    arr[i] = arr[hi];
    arr[hi] = tmp;
    i
}

fn quicksort(arr: MutRef([i32; 5]), lo: usize, hi: usize) {
    if lo < hi {
        let p = partition(arr, lo, hi);
        if p > lo {
            quicksort(arr, lo, p - 1);
        }
        quicksort(arr, p + 1, hi);
    }
}

fn main() -> i32 {
    let mut nums = [64, 25, 12, 22, 11];

    // Print before sorting
    @dbg(nums[0]);
    @dbg(nums[1]);
    @dbg(nums[2]);
    @dbg(nums[3]);
    @dbg(nums[4]);

    quicksort(&mut nums, 0, 4);

    // Print after sorting
    @dbg(0);  // separator
    @dbg(nums[0]);
    @dbg(nums[1]);
    @dbg(nums[2]);
    @dbg(nums[3]);
    @dbg(nums[4]);

    nums[0]  // Returns 11 (smallest)
}

What This Demonstrates

This example uses almost everything from the tutorial:

• Functions: partition and quicksort with parameters and return values
• Variables: Both mutable (let mut) and immutable (let)
• Control flow: if conditions and while loops
• Arrays: Fixed-size arrays with indexing
• Mutable references: MutRef(...) to modify the array in place
• Recursion: quicksort calls itself

Running It

cargo run -p gruel -- quicksort.gruel quicksort
./quicksort

Output:

64
25
12
22
11
0
11
12
22
25
64

The array is sorted!

More Examples

The GitHub repository has more examples in the examples/ directory:

• fibonacci.gruel - Iterative and recursive Fibonacci
• primes.gruel - Prime number sieve with trial division
• binary_search.gruel - Binary search on a sorted array
• quicksort.gruel - Full quicksort with 10-element arrays
• shapes.gruel - Interfaces with static and dynamic dispatch

Next Steps

You've learned the fundamentals of Gruel! The next chapters cover more features:

• Methods — dot-syntax operations defined inside struct and enum bodies
• Strings — the String type with heap allocation and automatic cleanup
• Input and Parsing — reading user input and converting strings to numbers
• Comptime and Generics — compile-time evaluation and generic functions
• Modules — splitting code across multiple files with @import
• Linear Types — must-consume types and explicit duplication via the Handle interface
• Unchecked Code and Raw Pointers — checked blocks, raw pointers, and syscalls
• Tuples — fixed-size groupings of heterogeneous values
• Slices — borrowed views over contiguous elements with runtime length
• Interfaces — structural conformance, derives, and Copy/Drop
• Destructors — automatic cleanup, drop order, and custom fn __drop

For the complete language reference, read the Language Specification.

Gruel is still in early development. If you find bugs or have ideas, please file an issue!