Basic sort algorithms in Rust

April 29, 2021

Page content

Disclamer

The implementations in this post have a lot of room for improvement. As of Apr. 2021, they are more like code monkey’s code :(

Reverse a string

fn main() {
    let s1 = String::from("Please reverse me with spaces!日本語.한국어");
    println!("Original string: {}",s1);

    let mut s2 = String::from("");
    for c in s1.chars().rev() {
        s2.push(c);
    }

    println!("Reversed: {}",s2);
}

In Rust, both String and a string slice &str are UTF-8 encoded.
chars() returns an iterator over chars of a string slice..
- “Note that, s.chars().count() is an $O(N)$ operation (because UTF-8 is complex) while getting the number of bytes is an O(1) operation.”
rev() reverses an iterator’s direction.
s1.len() returns the length of s1 in bytes.
If you want to count the number of “human readable” charactors in a String s1, s1.chars().count().
My open question: How to allocate a String (heap) with the size?

Bubble sort

Imagine the bubble (the highest value) is floating.
Bubble sort needs two loops as design…

fn main() {
    let mut numbers: [i32; 10] = [4,3,9,5,0,8,6,1,7,2];
    println!("Original array: {:?}", numbers);

    let length = numbers.len()-1;
    for i in 0..length {
        for j in 0..length-i {
            if numbers[j] > numbers[j+1] {numbers.swap(j,j+1)};
        }
    }

    println!("Sorted array: {:?}", numbers);
}

Print an array: {:?}. Print an array with new lines: {:#?}
Swap elements in an array: numbers.swap(0, 2);
- Here is the source code in Rust core:
- And here is the std::ptr:
- If I couldn’t use the swap(i,j), I would prepare a tepmorary variable and cache the value in it, like:
```
...
let mut tmp: i32;
...
if numbers[j] > numbers[j+1] {
    tmp = numbers[j];
    numbers[j] = numbers[j+1];
    numbers[j+1] = tmp;
}
```

Selection sort

Bubble sort swap the highest number during floating, but selection sort just marks the current lowest value, and swap at the end of scanning.

fn main() {
    let mut numbers: [i32; 10] = [4,3,9,5,0,8,6,1,7,2];
    println!("Original array: {:?}", numbers);

    let mut cache: usize;
    let length = numbers.len()-1;
    for i in 0..length {
        cache = i;
        for j in i..length {
            if numbers[j+1] < numbers[cache] {cache = j+1};
        }
        numbers.swap(i, cache);
    }

    println!("Sorted array: {:?}", numbers);
}

I realized at this point that println! macro takes a reference to any arguments to be formatted
When I set the type of cache as i32, the compiler returns expected `i32`, found `usize` at cache = j+1.

Insertion sort

Two loops.
The first loop (index i) indicates that an array is ordered from 0 to i.
In the second loop, order by simple swapping from i to 0.
Insertions costs a lot because an insert needs a lot of swaps.

fn main() {
    let mut numbers: [i32; 10] = [4,3,9,5,0,8,6,1,7,2];
    println!("Original array: {:?}", numbers);

    let mut tmp: usize;
    let length = numbers.len();
    for i in 1..length {
        tmp = i;
        loop {
            if numbers[tmp] < numbers[tmp-1] {
                numbers.swap(tmp,tmp-1);
            }
            tmp -= 1;
            if tmp == 0 {break};
        }
    }

    println!("Sorted array: {:?}", numbers);
}

Note: Could be improved, like, “if a swap doesn’t happen, break the loop”.

Quick sort

fn main() {
    let mut numbers: [i32; 20] = [24, 35, 69, 20, 47, 65, 91, 39, 63, 53, 40, 50, 27, 42, 93, 60, 0, 96, 25, 55];

    println!("Original array: {:?}", numbers);
    let length = numbers.len()-1;
    quicksort(&mut numbers, 0, length);

    println!("Sorted array: {:?}", numbers);
}

fn quicksort (array: &mut[i32], low: usize, high: usize) {
    if high > low + 3  {
        let p = partition(array, low, high);
        quicksort(array, low, p-1);
        quicksort(array, p+1, high);
    }
    else {
        insertion_sort(array, low, high);
    }
}

fn partition (array: &mut[i32], low: usize, high: usize) -> usize{
    println!("Quicksort partition...");
    let pivot_pointer = median_of_three(array, low, high);
    let pivot = array[pivot_pointer];
    array.swap(pivot_pointer,high);
    let mut i = low;
    for j in low..high {
        if array[j] < pivot {
            println!("Swap {:?} and {:?}", array[i], array[j]);
            array.swap(i,j);
            i = i+1;
        }
    }
    array.swap(i, high);
    return i;
}


// I guess, I should write more Rusty...
fn median_of_three (array: &[i32], low: usize, high: usize) -> usize {
    let middle = (low+high)/2;
    if array[high] < array[low] {
        if      array[middle] < array[high] { return high;}
        else if array[low] < array[middle]  { return low;}
        else                                { return middle;}
    } else {
        if      array[middle] < array[low]  { return low;}
        else if array[high] < array[middle] { return high;}
        else                                { return middle;}
    }
}

fn insertion_sort (array: &mut[i32], low: usize, high: usize) {
    let mut tmp: usize;
    for i in low+1..high+1 {
        tmp = i;
        loop {
            if array[tmp] < array[tmp-1] {
                array.swap(tmp,tmp-1);
            }
            tmp -= 1;
            if tmp == low {break};
        }
    }
}

In partition function:

i: indicator where the pivot should be placed.
j: prober.

Room for improvement

While finding medium, wa can sort a[low]``a[middle], and a[high]. Then, at array.swap(pivot_pointer,high); we can swap the pivot with high-1 instead of high. (Because median is small than one of the others.)

https://www.youtube.com/watch?v=1Vl2TB7DoAM. The video is comprehensive explanation of middle-of-three quicksort, if you have already implemented random pivot quicksort.

Memo:

As a naming convention, the name of functions are written in snake_case.
As a naming convention, the name of local variables are written in snake_case.
If you want to force exit while the code (for debug purpose), use std::process::exit.
Don’t for get a type -> after function.
Casting type: as i32 or `i32::from(foo)

`i32` issue on array

Rust int devision round https://users.rust-lang.org/t/integer-division/28180/8

// why iterater index usize -> spec. I changed all uszie -> f64::from(right-left) error
// https://stackoverflow.com/a/35979485
//12 |    return array[(f32::from(right-left)/2.0).round() as usize];
//   |                  ^^^^^^^^^ the trait `From<usize>` is not implemented for `f32`

To be updated…

Note: full `println` debuggin quicksort

fn main() {
    //let mut numbers: [i32; 10] = [3,6,4,5,0,8,1,9,7,2];
    let mut numbers: [i32; 20] = [24, 35, 69, 20, 47, 65, 91, 39, 63, 53, 40, 50, 27, 42, 93, 60, 0, 96, 25, 55];

    println!("-----------------");
    println!("Original array: {:?}", numbers);
    println!("Start quick sort");
    println!("-----------------");
    let length = numbers.len()-1;
    quicksort(&mut numbers, 0, length);

    println!("Sorted array: {:?}", numbers);
}

fn quicksort (array: &mut[i32], low: usize, high: usize) {
    println!("Start sort in partition");
    println!("Partition: from {:?} to {:?}", low, high);
    if high > low + 3  {
        println!("Before partition: {:?}", array);
        let p = partition(array, low, high);
        println!("-----------------");
        quicksort(array, low, p-1);
        quicksort(array, p+1, high);
    }
    else {
        println!("This partition smaller than 4. Do insertion sort.");
        insertion_sort(array, low, high);
        println!("-----------------");
    }
}

fn partition (array: &mut[i32], low: usize, high: usize) -> usize{
    println!("Quicksort partition...");
    let pivot_pointer = median_of_three(array, low, high);
    let pivot = array[pivot_pointer];
    println!("The median-of-three is : a[{}]={}", pivot_pointer, pivot);
    println!("Put the median at the right end of the partition, {}", high);
    array.swap(pivot_pointer,high);
    let mut i = low;
    for j in low..high {
        if array[j] < pivot {
            println!("Swap {:?} and {:?}", array[i], array[j]);
            array.swap(i,j);
            i = i+1;
        }
    }
    println!("The location of pivot: {:?}", i);
    array.swap(i, high);
    println!("After partition quicksort: {:?}", array);
    return i;
}


// I guess, I should write more Rusty...
fn median_of_three (array: &[i32], low: usize, high: usize) -> usize {
    let middle = (low+high)/2;
    if array[high] < array[low] {
        if      array[middle] < array[high] { return high;}
        else if array[low] < array[middle]  { return low;}
        else                                { return middle;}
    } else {
        if      array[middle] < array[low]  { return low;}
        else if array[high] < array[middle] { return high;}
        else                                { return middle;}
    }
}

fn insertion_sort (array: &mut[i32], low: usize, high: usize) {
    let mut tmp: usize;
    for i in low+1..high+1 {
        tmp = i;
        loop {
            if array[tmp] < array[tmp-1] {
                array.swap(tmp,tmp-1);
            }
            tmp -= 1;
            if tmp == low {break};
        }
    }
    println!("After insertion sort: {:?}", array);
}