Implementing Insertion sort in Rust (and it kinda sucked)


So I’m still learning Rust, and I decided to implement a naive version of the Insertion Sort algorithm as laid out in CLRS. I didn’t realise that it was going to be a bit of an exercise in frustration. Well, first let’s take a look at the code, and then do some analysis on it.

Here’s the C++ version:

#include <iostream>

using namespace std;

void insertion_sort(int arr[], int n)
{
	for (int i = 1; i < n; i++) {
		int key = arr[i];
		int j = i-1;

		while (j >= 0 && (arr[j] > key)) {
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = key;
	}
}

int main()
{
	int arr[] = { 10, -20, 1, 2, 6, 7, 99, 100, 0, 100 };

	insertion_sort(arr, 10);

	for (int& i : arr) {
		cout << i << " ";
	}

	cout << endl;

	return 0;
}

Take it for a spin:

Timmys-MacBook-Pro:my_sort z0ltan$ g++ -Wall -o insertion_sort insertion_sort.cpp -std=c++11
Timmys-MacBook-Pro:my_sort z0ltan$ time ./insertion_sort 
-20 0 1 2 6 7 10 99 100 100 

real	0m0.005s
user	0m0.001s
sys	0m0.003s

Nice! And here’s the Rust version:

pub fn insertion_sort(arr: &mut Vec<i32>) {
	for i in 1..arr.len() {
		
		let key = arr[i];
		let mut t:i32 = (i-1) as i32;
		let mut j = i-1;

		while arr[j] > key {
			arr[j+1] = arr[j];
			
			if t < 0 {
				break;
			}

			if j != 0 {
				j = j-1;
			}

			t = t-1;
		}

		j = (t+1) as usize;
		arr[j] = key;
	}
}


pub fn main() {
	let mut numbers = vec!(10, -20, 1, 2, 6, 7, 99, 100, 0, 100);

	insertion_sort(&mut numbers);

	for num in numbers {
		print!("{} ", num);
	}

	println!("");
}

And here’s the output from a test run:

Timmys-MacBook-Pro:src z0ltan$ rustc insertion_sort.rs
Timmys-MacBook-Pro:src z0ltan$ time ./insertion_sort
-20 0 1 2 6 7 10 99 100 100 

real	0m0.005s
user	0m0.002s
sys	0m0.002s

Great. Now compare the code in the sorting function in C++ and in Rust. The reason why the Rust version is so much more verbose (and filled with ugly casting and checks inside the while loop) is because of the type-safety that Rust provides.

Indexing in C++ and in Java is done using intS, even unsigned ones, and the compilers don’t really enforce any checks on that. So the same code (as in the C++ version) would work fine in Java as well.

In Rust, however, indexing is done using a “unsigned integer pointer size” type called usize. This means that we can’t do something like

   j -= 1;

inside the while loop in the Rust version. My issue is this – the compiler enforces nothing during compile time (aside from warning that a check like j >= 0 would be redundant), and it fails at runtime (as expected). Well, that explains the horrible hack of creating another mutable local variable, t to actually check when j goes 1 below 0 (as is required by this algorithm).

So far, I can’t say that I am overly impressed by Rust. I have seen the compiler miss a lot of clear checks that it could have done. For instance:

x == 1;

when I intended to do

x -= 1;

It shouldn’t be an error, but clearly there can be a warning since it’s basically doing nothing, being a statement than an expression. This may seem like picking at straws, but I wonder if Rust’s safety guarantees aren’t as valuable as the overheads of dealing with the Borrow Checker, and having to massively refactor the code, when business logic changes, to satisfy the Borrow Checker.

So far, what I’ve liked best about Rust is how easy it is to interact with C. C++ support is still far off since Rust does not really have the concept of a class (structS come close), and also name-mangling, but the basic use cases are extremely well-covered and well-designed.

I intend to so some small projects in Rust. Perhaps I will have a better idea of the actual ROI of Rust.

 

Advertisements
Implementing Insertion sort in Rust (and it kinda sucked)

Speak your mind!

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s