Basic sort algorithms in Rust

Page content

Disclamer

The implementations in this post has a lot of room to 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);
}

Bubble sort

  • 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);
    ...
    let mut tmp: i32;
    ...
    if numbers[j] > numbers[j+1] {
        tmp = numbers[j];
        numbers[j] = numbers[j+1];
        numbers[j+1] = tmp;
    }
    

Selection sort

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

  • 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);
}