↑Programmieren in Rust

Algorithmen: Sortierung

Inhaltsverzeichnis

1. Bubblesort
2. Quicksort

Bubblesort

fn bubble_sort<T: Ord>(a: &mut [T]) {
    let n = a.len();
    for _ in 0..n {
        for i in 0..n-1 {
            if a[i+1] < a[i] {a.swap(i, i+1);}
        }
    }
}

fn main() {
    let mut a = [3, 1, 4, 2];
    bubble_sort(&mut a);
    println!("{:?}", a);
}

Quicksort

Rekursiv

fn qsort<T: Ord + Clone>(a: &[T]) -> Vec<T> {
    if a.is_empty() {return vec![];}
    let l: Vec<T> = a[1..].iter().cloned().filter(|&x| x < a[0]).collect();
    let r: Vec<T> = a[1..].iter().cloned().filter(|&x| x >= a[0]).collect();
    [qsort(&l), qsort(&r)].join(&a[0])
}

fn qsort<T: Ord + Clone>(a: &[T]) -> Vec<T> {
    if a.is_empty() {return vec![];}
    let (l, r): (Vec<T>, Vec<T>)
        = a[1..].iter().cloned().partition(|&x| x < a[0]);
    [qsort(&l), qsort(&r)].join(&a[0])
}

Rekursiv, in-place

fn partition<T: Ord>(a: &mut [T], k: usize) -> usize {
    let pivot = a.len() - 1;
    a.swap(k, pivot);
    let mut i = 0;
    for j in 0..pivot {
        if a[j] <= a[pivot] {a.swap(i, j); i += 1;}
    }
    a.swap(i, pivot);
    i
}

fn qsort<T: Ord>(a: &mut [T]) {
    if a.len() < 2 {return;}
    let i = partition(a,0);
    qsort(&mut a[..i]);
    qsort(&mut a[i+1..]);
}