Basic Sorting in Rust

This is an article about sorting algorithms using Rust programming language.

Bubble Sort

In bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, continuously making sweeps of the array until it is sorted. This algorithm is called “bubble” because the smaller item items slowly “bubble” up to the beginning of the list😊

Time complexity: O(n2)
Memory complexity: O(1)
Sort in place: yes
Stable sort: yes

fn bubble_sort(mut arr: Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    if n <= 1 {
        return arr;
    }
    for i in 0..n {
        let mut has_swap = false;
        for j in 0..(n - i - 1) {
            if arr[j] > arr[j + 1] {
                let temp = arr[j + 1];
                arr[j + 1] = arr[j];
                arr[j] = temp;
                has_swap = true;
            }
        }
        if has_swap == false {
            break;
        }
    }
    arr
}

Insertion Sort

Insertion sort is similar to bubble sort, I found a lot of articles are mixing them together. There is an insert operation in insertion sort at least. The core idea of insertion sort is iterating the array, finding out the index where an element should be put and inserting it at the right position.

Time Complexity: O(n2)
Space Complexity: O(1)
Sort in place: yes
Stable sort: yes

fn insertion_sort(arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }

    for i in 0..arr.len() {
        let value = arr[i];
        let mut j = (i - 1) as i32;
        while j >= 0 {
            if arr[j as usize] > value {
                arr[(j + 1) as usize] = arr[j as usize]
            } else {
                break;
            }
            j -= 1;
        }
        arr[(j + 1) as usize] = arr[i]
    }

    arr
}

Selection Sort

The selection sort is simple but inefficient. Find the smallest element using a linear iterate and move it to the front. Then, apply this logic to the second smallest element, until all the elements are in place.

Time Complexity: O(n2)
Space Complexity: O(1)
Sort in place: yes
Stable sort: no

fn selection_sort(mut arr: Vec<i32>) -> Vec<i32> {
    if arr.len() <= 1 {
        return arr;
    }

    for i in 0..arr.len() {
        let mut mini_idx = i;
        for j in (i + 1)..arr.len() {
            if arr[j] < arr[mini_idx] {
                mini_idx = j;
            }
        }
        let temp = arr[i];
        arr[i] = arr[mini_idx];
        arr[mini_idx] = temp;
    }
    arr
}

Merge Sort

The time complexity of all the sorting algorithms upper is O(n2). It’s not efficient as merge sort and quick sort. Merge sort divides the array in half, sorts each part and merges them back together. Each part could divide into two parts and sort them with the same logic, do you familiar with this idea?

Yes, it’s recursive.

Time Complexity: O(nlogn)
Space Complexity: O(n). It is very complex to analyse the space complexity.
Sort in place: no
Stable sort: yes

pub fn merge_sort(mut arr: Vec<i32>) -> Vec<i32> {
    let n = arr.len() as usize;
    merge_sort_recusive(&mut arr, 0, n);
    arr
}

fn merge_sort_recusive(arr: &mut Vec<i32>, start: usize, end: usize) {
    if start >= end {
        return;
    }
    let middle = start + (end - start) / 2;
    merge_sort_recusive(arr, start, middle);
    merge_sort_recusive(arr, middle + 1, end);

    merge(arr, start, middle, end);
}

fn merge(arr: &mut Vec<i32>, start: usize, middle: usize, end: usize) {
    let mut i = start;
    let mut j = middle + 1;
    let mut temp: Vec<i32> = vec![];

    // using two-pointer generate a sorted array
    while i <= middle {
        if j <= end {
            if arr[i] <= arr[j] {
                temp.push(arr[i]);
                i += 1;
            } else {
                temp.push(arr[j]);
                j += 1;
            }
        } else {
            break;
        }
    }

    // checkout which part has un-used elements
    let mut low = i;
    let mut high = middle;

    if j <= end {
        low = j;
        high = end;
    }

    while low <= high {
        temp.push(arr[low]);
        low += 1;
    }

    // replace origin array with sorted temp array
    for i in 0..(end - start) {
        arr[start + i] = temp[i]
    }
}

Quick Sort

In quick sort, we pick a random element and divide the array into two parts. The numbers less than the pivot will be put in the front part, and the numbers bigger than the pivot put in the rear array. Repeating this procedure until the whole array is sorted.

fn quick_sort(mut arr: Vec<i32>) -> Vec<i32> {
    let n = arr.len();
    quick_sort_recusive(&mut arr, 0, n);
    arr
}

fn quick_sort_recusive(arr: &mut Vec<i32>, start: usize, end: usize) {
    if start >= end {
        return;
    }
    let partition = partition(arr, start, end);
    quick_sort_recusive(arr, start, partition - 1);
    quick_sort_recusive(arr, partition + 1, end);
}

fn partition(arr: &mut Vec<i32>, start: usize, end: usize) -> usize {
    let pivot = arr[end];

    let mut i = start;
    for j in start..end {
        if arr[j] > pivot {
            let temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i += 1;
        }
    }

    arr[end] = arr[i];
    arr[i] = pivot;

    i
}

Last modified on 2022-03-21