2 sorting Problems of 99 to understand Rust — Part 2 - 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/99-problems-to-understand-rust-by-js-part-2-40852cf9652d

2 sorting Problems of 99 to understand Rust — Part 2

[ Enigma Bits

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

](https://blog.stackademic.com/?source=post_page-----40852cf9652d--------------------------------)

Enigma Bits

Published in[

Stackademic

](https://blog.stackademic.com/?source=post_page-----40852cf9652d--------------------------------)·8 min read·Jan 27, 2024

—

Listen

from unsplash.com

In the previous section, we explored fundamental aspects of Rust programming, covering its structural anatomy, declarative style, and JSON deserialization. Building on this foundation, Part 2 will introduce more advanced topics and practical applications.

[

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-----40852cf9652d--------------------------------)

Topics to be Covered:

2 Sort Algorithms
Implementing a sort Gimmick
Mutation in Rust
Benchmarking

Sorting Algorithms

I know, the word Algorithms might be a turn off to you, but it will help us grasp a better knowledge in the language as did to me during my Pythonista times. I have chosen very basic easy to implement sorting algorithms so language will be the only barrier.

Bubble sort
Quick sort

These are essentially not the best, but they come in handy now and then.

Bubble Sort

Bubble sort visualized — Enigma Bits

Instead of paragraphs, I have embedded a visualization. The essence is as follows:

for each k in collection, we check next one is greater than; if so, we swap the two in-place — else we move on
then after we re-iterate but this time we ignore the last element — as it is already the maximum resultant of previous pass/iteration.
we ignore an element at a time from end of the list for each pass/iteration; finish when there is only one left.

In the video, one can observe the movement of 4 being swapped in each iteration & the iteration ignores elements from last position on successive terms.

One key point about Bubble sort is that the collection becomes sorted upon each pass from the end towards the beginning. Second is that the first pass produces maximum element in the collection towards the end (here 2003).

Bubble Sort in Rust

The plan of attack is to iterate over an array, if arr[k] > arr[k+1] then we swap the couple; do passes until the array is sorted. This translates to this…

pub fn bubble\_sort<T: Ord>(arr: \[T\]) {  
    if arr.is\_empty() {  
        return;  
    }  
    let mut sorted = false;  
    let mut n = arr.len();  
    while !sorted {  
        sorted = true;  
        for i in 0..n - 1 {  
            if arr\[i\] > arr\[i + 1\] {  
                arr.swap(i, i + 1);  
                sorted = false;  
            }  
        }  
        n -= 1;  
    }  
}

Trying to compile this, we will meet an error which will be new for developers from dynamically typed languages (DTL).

first error we encounter

Alas, compiler tells us a solution too. But why do we need to know the size of the array beforehand?

Stack. I recon you might have heard this term, but it really is a point of concern in systems programming. OS allocated memory slot for our program which is divided into Stack & Heap.

The Stack is used for static memory allocation, which includes local variables and function parameters. Its size is determined at compile time, meaning the compiler must know how much memory to allocate for these variables before the program runs.

When a function is called, its parameters and local variables are pushed onto the Stack. Once the function completes, they are popped off, freeing up space efficiently.

If the size of function parameters were not known at compile time, the Stack couldn’t be used effectively. The system would struggle, leading to inefficiencies or even errors like stack overflows, where the Stack’s limit is exceeded; Knowing the size of function parameters at compile time allows the system to allocate memory effectively, maintain execution speed, and ensure the stability of the program.

So, listening to the rustc,let’s modify our code. Compiling…

Second error we encounter

…produces an error, but 🙌 we have different error. We are making some progress it seems.

A reference cannot be borrowed as mutable?!

whaaaaaaaaaaaaaaaat?

Mutations in Rust

The plethora of rust propaganda is due to rust’s ability to juggle mutable data safely and performantly as much as possible. For the last error we have to figure out 3 things:

What is Reference?
What Borrowing means?
Mutations not in borrowed reference, why?

References. Remember how & fixed the first issue? Since we don’t know the size of the array at compile time, we passed in a reference to array instead of the array itself to the function. A reference (memory address) is always known at compile time as it the memory bus width (64 bits or 32 mostly); thus, compiler was able to layout Stack correctly.

Borrow. In rust’s lingo, we say the bubble_sort function borrowed a reference to some array of type T. Instead of borrowing the value we borrowed a reference by appending the & to the type definition of the parameter arr.

And by default, all the borrows are immutable unless explicitly annotated as mut which is the solution compiler is providing us in the Second error message. I think Prime said it better in terms of DTL, I will let him cook.

So…

Every “rust-object” has notion of owner & value (which is immutable as well).
By default, functions borrow values,
Unless explicitly indicated by & keyword.
Borrowed references are immutable by nature,
Unless references are annotated with mut, they are immutable.
Moving “object” around moves scope which would automatically manage the memory for us during function clean up phase (the end curly brace)

Back to Bubble Sort

Since we borrowed a reference to an array of T and later swaps the conflicting couples in-place, we need to notify compiler that we need a mutable reference. Thus, annotating the type definition with mut keyword.

pub fn bubble\_sort<T: Ord>(arr: &mut \[T\]) {  
    if arr.is\_empty() {  
        // merely a rain check  
        return;  
    }  
      
    let mut sorted = false;  
    let mut n = arr.len();  
     
     while !sorted {  
  
        sorted = true;  
  
        // iterate over each element and compare the neighbor  
        for i in 0..n - 1 {  
            if arr\[i\] > arr\[i + 1\] {  
                // v-- this line is the reason we have to put mut  
                arr.swap(i, i + 1);  
                sorted = false;  
            }  
        }  
          
        // we then ignore last elements from each iteration as  
        // indicated in the visualization video  
        n -= 1;  
    }  
}

This snippet compiles and thus run as expected indeed. At this point I expect you to understand the bare basics of what and why we need &mut for arr.

As one is exposed to more rust code snippets, the vague ideas will be solidified or loopholes in knowledge will become apparent, which signals the one needs a revision — Birnadin E.

it is free by the way!

GNU Utils sort gimmick

Now that we know 2 sorting algorithms, I think we can put it to test by mimicking the sort utility. At the end of the day, if we can’t utilize the skill we learned, then why waste time learning?

The CLI

The sort utility works on strings, merely mimicking it is waste. Let’s make our program work on integers (numbers to be precise). Because this weird behavior is by default is of sort.

sort utility interpreting 2003 as string

Since check is by strings, 2003 did not have any context and shoveled towards 2 and proceeded. Our sort will have context of numbers. We will take our input from stdin and save the File IO to later part of the series.

Our input parsing is simple as converting the strings to i32. Before that, ignore the first argument from the OS as it is always the path of the binary command shell invoked. In case you don’t know any of this, please refer to Enigma Bits Part 1 in 99 Problems to Understand Rust.

[

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-----40852cf9652d--------------------------------)``` let args: Vec = std::env::args().skip(1).collect();

if args.is\_empty() {  
    panic!("Usage: sort \[space seperated numbers to sort\]");  
}


Then I decided to simplify the program to restrict the input to be only signed 32 bits integers. So, we then convert the `args` we collected.

let mut args: Vec = args
.iter()
.map(|x| i32::from_str(x).expect(“Input Parse failed. Only i32 values.”))
.collect();


Then after we just call out `bubble_sort` on `arr`. **Note** the `mut` keyword in-front of second `args`. After sorting, we will print the `arr` to the standard output. Hence the entire code for the CLI should read like 👇

use std::str::FromStr;

fn bubble_sort<T: Ord>(arr: &mut [T]) {
if arr.is_empty() {
return;
}

let mut sorted = false;  
let mut n = arr.len();  
  
while !sorted {  
    sorted = true;  
      
    for i in 0..n - 1 {  
        if arr\[i\] > arr\[i + 1\] {  
            arr.swap(i, i + 1);  
            sorted = false;  
        }  
    }  
    n -= 1;  
}

}

fn main() {
let args: Vec = std::env::args().skip(1).collect();

if args.is\_empty() {  
  eprintln!("Usage: sort <space seperated numbers to sort>");  
  std::process::exit(1);  
}  

let mut args: Vec<i32> = args  
    .iter()  
    .map(|x| i32::from\_str(x).expect("Input Parse failed. Only i32 values."))  
    .collect();  

bubble\_sort(&mut args); // the magic  
println!("{:?}", args);

}


Benchmark
=========

So I have benchmarked this bubble sort with Quick sort implementation I will be doing in [Part 3](https://medium.com/@birnadin/2-sorting-problems-of-99-to-understand-rust-part-2-2f4a5b1aa2e9). And results are (not) surprising! Here is the average time to execute graph plotted in log-scale.

Yh, we have impurities as well

If you want to learn about the implementation that beats our current, then don’t miss the Part 3.

What’s next?
------------

I promised 2 sorting algorithms, but I have only included 1 here; can’t I count? Of course I can (depends on how much hunger I am). I wanted to implement Quick Sort as well and have a CLI flag to alter the sorting algorithm.

But the way I came up with it, I need to introduce you to _traits_ (rust’s polymorphic solution to scalable code base with no runtime cost). Adding it up here breaks the joy and might bore the readers. So I split this into 2 portions and third(3) part of the series will cover the rest:

*   Quick sort
*   Flags to CLI the manual way and _clap_ way
*   O in SOLID
*   Benchmark in details

[

2 sorting Problems of 99 to understand Rust — Part 3
----------------------------------------------------

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

medium.com

](https://medium.com/@birnadin/2-sorting-problems-of-99-to-understand-rust-part-2-2f4a5b1aa2e9?source=post_page-----40852cf9652d--------------------------------)

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