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

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

[

](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--------------------------------)

·

Published in[

Stackademic

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

—

Listen

Share

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. `pivot`

is 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

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/)
```