Sorting Algorithms

Introduction

Sorting algorithms are fundamental in computer science for arranging data in a specific order. This lesson covers some of the most important sorting algorithms, including their properties, time complexities, and implementations in Rust.

Key Points

• Sorting Algorithms: Techniques for ordering elements in a list or array.
• Time Complexity: A measure of the amount of time an algorithm takes to complete based on the size of the input.

Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process is repeated until the list is sorted.

Bubble Sort Implementation

fn bubble_sort<T: Ord>(arr: &mut [T]) {
    let mut n = arr.len();
    let mut swapped = true;

    while swapped {
        swapped = false;
        for i in 1..n {
            if arr[i - 1] > arr[i] {
                arr.swap(i - 1, i);
                swapped = true;
            }
        }
        n -= 1;
    }
}

fn main() {
    let mut array = [64, 34, 25, 12, 22, 11, 90];
    bubble_sort(&mut array);
    println!("Sorted array: {:?}", array);
}

Code Explanation

• bubble_sort: Iterates through the array, swapping adjacent elements if they are out of order, until no more swaps are needed.
• Time Complexity: O(n²) in the worst and average cases; O(n) in the best case (when the array is already sorted).

Selection Sort

Selection Sort is a simple sorting algorithm that divides the list into a sorted and unsorted region. It repeatedly selects the smallest (or largest) element from the unsorted region and moves it to the end of the sorted region.

Selection Sort Implementation

fn selection_sort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    for i in 0..len {
        let mut min_index = i;
        for j in (i + 1)..len {
            if arr[j] < arr[min_index] {
                min_index = j;
            }
        }
        arr.swap(i, min_index);
    }
}

fn main() {
    let mut array = [64, 34, 25, 12, 22, 11, 90];
    selection_sort(&mut array);
    println!("Sorted array: {:?}", array);
}

Code Explanation

• selection_sort: Finds the minimum element from the unsorted part of the array and swaps it with the first unsorted element.
• Time Complexity: O(n²) for all cases (worst, average, and best).

Insertion Sort

Insertion Sort builds the final sorted array one item at a time by repeatedly picking the next item and inserting it into its correct position in the already sorted part of the array.

Insertion Sort Implementation

fn insertion_sort<T: Ord>(arr: &mut [T]) {
    let len = arr.len();
    for i in 1..len {
        let mut j = i;
        while j > 0 && arr[j - 1] > arr[j] {
            arr.swap(j - 1, j);
            j -= 1;
        }
    }
}

fn main() {
    let mut array = [64, 34, 25, 12, 22, 11, 90];
    insertion_sort(&mut array);
    println!("Sorted array: {:?}", array);
}

Code Explanation

• insertion_sort: Inserts each element into its correct position relative to the already sorted portion of the array.
• Time Complexity: O(n²) in the worst case; O(n) in the best case (when the array is already sorted).

Merge Sort

Merge Sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts each half, and then merges the sorted halves.

Merge Sort Implementation

fn merge_sort<T: Ord + Clone>(arr: &mut [T]) {
    let len = arr.len();
    if len <= 1 {
        return;
    }

    let mid = len / 2;
    let mut left = arr[0..mid].to_vec();
    let mut right = arr[mid..].to_vec();

    merge_sort(&mut left);
    merge_sort(&mut right);

    merge(arr, &left, &right);
}

fn merge<T: Ord + Clone>(arr: &mut [T], left: &[T], right: &[T]) {
    let mut i = 0;
    let mut j = 0;
    let mut k = 0;

    while i < left.len() && j < right.len() {
        if left[i] <= right[j] {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
        k += 1;
    }

    while i < left.len() {
        arr[k] = left[i].clone();
        i += 1;
        k += 1;
    }

    while j < right.len() {
        arr[k] = right[j].clone();
        j += 1;
        k += 1;
    }
}

fn main() {
    let mut array = [64, 34, 25, 12, 22, 11, 90];
    merge_sort(&mut array);
    println!("Sorted array: {:?}", array);
}

Code Explanation

• merge_sort: Recursively divides the array into halves, sorts each half, and then merges them.
• merge: Merges two sorted arrays into a single sorted array.
• Time Complexity: O(n log n) for all cases.

Quick Sort

Quick Sort is a divide-and-conquer algorithm that selects a pivot element, partitions the array into elements less than and greater than the pivot, and recursively sorts the partitions.

Quick Sort Implementation

fn quick_sort<T: Ord + Clone>(arr: &mut [T]) {
    if arr.len() <= 1 {
        return;
    }
    let pivot_index = partition(arr);
    let (left, right) = arr.split_at_mut(pivot_index);
    quick_sort(&mut left[0..pivot_index]);
    quick_sort(&mut right[1..]);
}

fn partition<T: Ord + Clone>(arr: &mut [T]) -> usize {
    let pivot_index = arr.len() / 2;
    let pivot = arr[pivot_index].clone();
    arr.swap(pivot_index, arr.len() - 1);

    let mut i = 0;
    for j in 0..arr.len() - 1 {
        if arr[j] < pivot {
            arr.swap(i, j);
            i += 1;
        }
    }
    arr.swap(i, arr.len() - 1);
    i
}

fn main() {
    let mut array = [64, 34, 25, 12, 22, 11, 90];
    quick_sort(&mut array);
    println!("Sorted array: {:?}", array);
}

Code Explanation

• quick_sort: Selects a pivot, partitions the array, and recursively sorts the partitions.
• partition: Rearranges elements around the pivot and returns the pivot index.
• Time Complexity: O(n log n) on average; O(n²) in the worst case.

Real World Examples

Bubble Sort

• Educational Purposes: Used for teaching basic sorting concepts due to its simplicity.

Selection Sort

• Simple Use Cases: Useful when memory is limited, and simplicity is preferred over performance.

Insertion Sort

• Small Arrays: Efficient for small or partially sorted arrays, like in certain hybrid sorting algorithms.

Merge Sort

• Large Data Sets: Used in external sorting algorithms where data cannot fit into memory, like sorting large files.

Quick Sort

• General Purpose: Efficient for most practical use cases due to its average-case performance, used in standard libraries and applications.

Conclusion

Sorting algorithms are essential tools in computer science, with each algorithm offering different trade-offs in terms of complexity and efficiency. Understanding and implementing these algorithms in Rust helps you solve various sorting problems and grasp fundamental computer science concepts.