2 sorting Problems of 99 to understand Rust — Part 3 - 27/01/2024

What could learn by mimicking the sort GNU Utility? A Lot actually.

Site under construction! Migrated content might be displayed ugly!

medium-to-markdown@0.0.3 convert node index.js https://medium.com/stackademic/2-sorting-problems-of-99-to-understand-rust-part-2-2f4a5b1aa2e9

2 sorting Problems of 99 to understand Rust — Part 3

[ Enigma Bits

](https://medium.com/@birnadin?source=post_page-----2f4a5b1aa2e9--------------------------------)[![Stackademic](https://miro.medium.com/v2/resize:fill:48:48/1*U-kjsW7IZUobnoy1gAp1UQ.png)

](https://blog.stackademic.com/?source=post_page-----2f4a5b1aa2e9--------------------------------)

Enigma Bits

Published in[

Stackademic

](https://blog.stackademic.com/?source=post_page-----2f4a5b1aa2e9--------------------------------)·10 min read·Jan 27, 2024

—

Listen

from unsplash.com

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.

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.

a brief quick sort recursively calling to sort children — fig. 1

Following video demonstrates the traits of quick sort (you may want to slow the speed down, sorry bitrate conflicts)

Quick sort visualized

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:

sorting the subarray (termed partition)
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.

Third error or later (who’s counting?)

…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).

it won’t cost you anything by the way

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.

API of sort

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).

Another thing is position of command line. We could require user to specify at either beginning or end, but implementing that would be a headache (however, at the end I would show you how), thus we will utilize a library I introduced you in the Part 1.

[

99 problems to understand Rust — Part 1

what could you learn by building a CLI tool to find GCD of integers?

blog.stackademic.com

](https://medium.com/99-problems-to-understand-rust-part-1-53c6899b460e?source=post_page-----2f4a5b1aa2e9--------------------------------)

Going through the documentation of clap, we can equip the Flags feature. Though Flags act as boolean values, by overriding the action with Count we could replicate the -vvvv functionality of conventional binaries. So let’s define our command-line argument parser.

#\[derive(Parser)\]  
#\[command(version)\]  
struct CLIAPI {  
    #\[arg(short, long, action=clap::ArgAction::Count)\]  
    switch: u8,  
    nums: Vec<i32>,  
}

Our CLI API will act as declarative way to parse our command line arguments. All we have to do is CLIAPI::parse() to have a variable with defined fields populated with decorated types. 🥰.

Now all we have to do is test the switch and invoke functions accordingly. When all is done, our main.rs should be…

use clap::Parser;  
use sort::{bubble\_sort, quick\_sort};  
  
#\[derive(Parser)\]  
#\[command(version)\]  
struct CLIAPI {  
    #\[arg(short, long, action=clap::ArgAction::Count)\]  
    switch: u8,  
    nums: Vec<i32>,  
}  
  
fn main() {  
    let args = CLIAPI::parse();  
  
    let mut nums = args.nums;  
  
    if args.switch % 2 == 0 {  
        quick\_sort(&mut nums);  
    } else {  
        bubble\_sort(&mut nums);  
    }  
  
    println!("{:?}", nums);  
}
```And our binary works

Give it a go and try the binary. You could see it is fast. But how fast when alternating between methods?

Benchmarking Bubble and Quick sort
----------------------------------

I know, we all know Bubble sort is O(N²) and Quick sort is around O(N log N). But how does it translate into real world performance? Let’s use another crate — criterion. It is a micro-benchmarking tool i.e. we can benchmark at functional level as well.

I will just reuse the benchmark script I already had. For futher clarrification please refer 👇 tutorial. But to have just joy, you dont need to!

[

Micro-benchmarking in Rust 101
------------------------------

### Not a professional at benchmarking, but a wannabe!

medium.com

](https://medium.com/@birnadin/micro-benchmarking-in-rust-101-2682235a5a08?source=post_page-----2f4a5b1aa2e9--------------------------------)```
fn benchmark\_sort(c: &mut Criterion) {  
    let file\_sizes = vec!\[10, 100, 1000, 10000, 100000\];  
  
    match std::env::current\_dir() {  
        Ok(cwd) => println!("{}", cwd.display()),  
        Err(\_) => panic!("err getting CWD"),  
    };  
  
    for &size in &file\_sizes {  
        let data = read\_data\_from\_file(format!("./benches/data\_{}.txt", size))  
            .expect("Failed to read data");  
  
        let mut group = c.benchmark\_group(format!("Sort - {} items", size));  
  
        group.bench\_function("bubble\_sort", |b| {  
            b.iter(|| {  
                let mut data\_clone = data.clone();  
                bubble\_sort(black\_box(&mut data\_clone));  
            })  
        });  
  
        group.bench\_function("quick sort", |b| {  
            b.iter(|| {  
                let mut data\_clone = data.clone();  
                quick\_sort(black\_box(&mut data\_clone));  
            })  
        });  
  
        group.finish();  
    }  
}
```I don’t know why with 100K bubble sort is fast

Too much information eh? I only care about runtime, especially mean time to sort juxtaposed. Plotting it looks like…

Average time each function took to execute

Not that our 10, 100 and such did not run, they are relatively negligible when compared to Bubble Sort of 10K items. Hard to visualize, though I am not a statistician I took some physics classes. And I know that decibels is in log-scale due to varying scale and logarithmic scale makes spreads like these easy to understand. Doing so…

logarithmic scale to understand the runtime

I am confused. 100K is still bothering me. May be it is due to the fact that 100K will be recursed (comes cost of stack manipulation and memory requirements) whereas Bubble sort is raw memory manipulation. If you know why, please feel free to comment, most welcome 🙏

time ranges for execution

> To me it seems like 1000 (1K) is a sweet spot for Quick sort and Bubble sort is better suited for smaller samples.

**Note** that above benchmark was run on a development machine, hence results are not pure; though I’d pass as it is only for fun and theoretically there are white papers to prove my point 😜

What is Next?
-------------

I hope I made some difference with this article and made my best to express my learning journey. If you are also learning Rust right now, then follow me for more of my perspective; love to connect with you as well 🤟

Part 4 will be on Strings, and as of my knowing rust has quite a variety & each its perks and cons. I will test my understanding with a search algorithm (not fuzzy, it for later when I am able to implement a tree) and mimic the _grep_ utility.

If you are into these kind of stuff make sure to subscribe [Enigma Bits Newsletter](https://enigmabits.substack.com)! A Clap to the story wouldn’t hurt you as well.

Till next time, it’s _meTheBE_ signing off 👋

Stackademic
===========

Thank you for reading until the end. Before you go:

*   Please consider **clapping** and **following** the writer! 👏
*   Follow us [**X**](https://twitter.com/stackademichq) **|** [**LinkedIn**](https://www.linkedin.com/company/stackademic) **|** [**YouTube**](https://www.youtube.com/c/stackademic) **|** [**Discord**](https://discord.gg/in-plain-english-709094664682340443)
*   Visit our other platforms: [**In Plain English**](https://plainenglish.io/) **|** [**CoFeed**](https://cofeed.app/) **|** [**Venture**](https://venturemagazine.net/)