2 sorting Problems of 99 to understand Rust

Previously we implemented Bubble sort and made our gimmick sort utility which supplements the original sort GNU Util. We noticed the short-come of the Original and gave our implementation context of numbers. If you skipped the Part 2, I highly recommend reading as we will build on it.

Thanks for reading Enigma Bits! Subscribe for free to receive new posts and support my work.

Here we will:

• learn Quick sort (advancing from bubble sort)
• add conditional flag to our CLI binary to switch between algorithms
• benchmark with bubble sort (technically we know the results, but let’s shoot it)

Quick Sort

Quick sort is different from Bubble sort — it is tree-based whereas Bubble sort is linear.

Inwords…

• Quick Sort starts by selecting a pivot element (arrow in the video).
• The array is then partitioned around this pivot, rearranging elements so that those less than the pivot are on the left, and those greater are on the right (tree like structure in fig. 1).
• The pivot element reaches its sorted position after partitioning (the 4 is swapped with 2003 in first scan in the video)
• This process is recursively applied to the subarrays formed on either side of the pivot (clear from the given fig. 1 above video).
• The recursion continues until the subarrays consist of a single element, at which point the array becomes fully sorted.

We also keep track of last swapped position in each scan so that if replace is needed. This is how we swap 4 with 2003 and then 104 with 140. If this is still unclear, please let me know in the comments.

How does this translate to rust code? Idiomatically (how we use i and j in loops) quick sort decomposes to 2 functions, each taking care of:

1. sorting the subarray (termed partition)
2. coordinating the partitions recursively

The meat is the function that does the partition.

fn partition<T: Ord>(arr: &mut [T], lo: usize, hi: usize) -> usize {
    let pivot = arr[hi];
    let mut idx = lo; // where we swapped last time
    
    for i in lo..hi {
        if arr[i] <= pivot {
            // swap because only smaller values are on left side
            arr.swap(idx, i);
            idx += 1;
        }
    }
    
    // now swap our pivot as well
    // because now greater values are at and beyond
    // out last swapped place
    // idx += 1;
    arr.swap(hi, idx);
    idx
}        

You should understand everything in here by now, we cleared them earlier. Should any errors to occur you will be able to fix them by yourself, probable except one.

…which does not implement the Copy trait

Before exploring what it is, let’s use the solution compiler gave us. Doing so gives us another error. Mismatched type? Where?

if arr[i] <= pivot {        

Makes sense right. pivotis now a reference, not usize. As compiler suggests we will dereference the pivot using * operator. Think of & and * as opposites of each other (just like how they are in QWERTY key layout).

Compiling now gives another error ?? BUT this time it is familiar. You know why this is, right? Right?

Notice compiler gave up suggestions, should we too? May be time to rethink that start-up idea! ?? Bit of StackOverflow analysis leads to another solution; the one we ignored to explore — Copy trait. What is a trait?

Trait. Equivalent to interfaces in other languages, rust answers OOP with this. But this is static polymorphism not the dynamic like python’s; I will go over this later, but now think of this as an “Abstract Class” which defines set of functions a type with this trait has implemented.

That leads us to next Enigma, Copy. The Copy trait in Rust signifies that a type can be duplicated by simply copying its bits. It’s used for straightforward types like primitives, facilitating easy and safe data replication without the complexities of deep cloning. This trait plays a key role in Rust’s approach to memory safety and efficient data management.

The problem here is that our T can be anything than can be ordered ( Ord trait). When T is some say JSON Struct then children and their children might have pointers to Heap, which by copying to pivot and later if mutated down the flow might cause unexpected behaviors.

Either we need to do a clone of entire array and mutate it (which is slow) or not do that and narrow our T towards something primitive. Since this is a tutorial I will also require T to implement Copy trait by itself.

Note ?: This is not how we might do in production; I stripped down the deep cloning for later use and for sake of grasping the basics!

After making necessary changes function signature looks like this…

pub fn partition<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize) -> usize {        

Now the code compiles and our partition looks like…

fn partition<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize) -> usize {{
    let pivot = arr[hi];
    let mut idx = lo; // where we swapped last time

    for i in lo..hi {
        if arr[i] <= pivot {
            // swap because only smaller values are on left side
            arr.swap(idx, i);
            idx += 1;
        }
    }
    
    // now swap our pivot as well
    // because now greater values are at and beyond
    // out last swapped place
    // idx += 1;
    arr.swap(hi, idx);
    idx
}        

The rest of Quick Sort

Partitioning out of the way, we now need to break the arr into partitions and recursively sort the subarrays as well. The pivot is determined by the designer, I pivot from the end; because why not?

pub fn quick_sort<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize) {
    if lo >= hi {
        return;
    }

    let pivot_idx = partition(arr, lo, hi);
    
    if pivot_idx > 0 {
        quick_sort(arr, lo, pivot_idx - 1); // branch left
    }
    quick_sort(arr, pivot_idx + 1, hi); // branch right
}        

Here lo being greater than or equal to hi — we are down to just 1 element in arr — is our base case. We terminate at that point. The second if statement is due to the rust’s usize being only positive (makes sense) but conventionally we start from -1 as last swapped point.

The commented branch left/right is in fig. 1 the left and right branches being split by the pivot point ( pivot_idx). And we are done!

O in SOLID

Infamous SOLID tells us a better code base is Open for extension and Closed for modification. Look at our quick_sort API.

fn quick_sort<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize)        

We are leaking internal implementation; quick_sort user does not need to worry about lo/hi, rather their only worry is whether arr is sorted. This is leaky abstraction. In team environment, this is headache as the team scales. You should learn to keep the team in mind during development of such utilities or whatsoever.

Solution: A wrapper. Let’s expose another function which would sort the arr and look after lo/hi making our users only worry about the arr of T to implement Copy and Ord trait.

/// sorts the given array and returns index to be partitioned again
fn partition<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize) -> usize {
    let pivot = arr[hi];
    let mut idx = lo;

    for i in lo..hi {
        if arr[i] <= pivot {
            arr.swap(idx, i);
            idx += 1;
        }
    }

    arr.swap(hi, idx);
    idx
}

/// partitions an array into left and right pivotted using partition
fn sort<T: Ord + Copy>(arr: &mut [T], lo: usize, hi: usize) {
    if lo >= hi {
        return;
    }

    let pivot_idx = partition(arr, lo, hi);

    if pivot_idx > 0 {
        sort(arr, lo, pivot_idx - 1);
    }
    sort(arr, pivot_idx + 1, hi);
}

/// public facing function as a wrapper
pub fn quick_sort<T: Ord + Copy>(arr: &mut [T]) {
    if arr.is_empty() {
        return;
    }

    sort(arr, 0, arr.len() - 1);
}        

Whew, done it.

If you are learning something and want more follow me on Medium so that you may never miss a beat. Next up…

• Strings and grep clone,
• Redis clone during hashing,
• bloom filters and cryptography,
• regex to enhance our grep clone,

…I have a great playlist planned on.

Enhancing Our Utility

Now that we have another better algorithm at our hand, let’s cooperate it into our sort utility. We already have a base implementation; all we need to do now is to build on top of it.

I intend to switch our algorithm using a common methodology in CLI world — Switches. The number of times we specify -s will switch the algorithm. We could simply say 1 time to bubble and 2 times to quick sort. But where is fun in that? Odd number will be Bubble sort and Even number will switch to Quick sort. By default, we will do Quick sort, since it is better (theoretically).

Continue Reading for free

Yay, you have made it this far. If you want to learn how to implement flags arguments using clap and benchmark this against the previous sort utility with different algorithm, I advise you to check out the full length post (which is free by the way)