Function partition

pub fn partition<T>(slice: &mut [T], pivot_index: usize) -> usize
where
    T: Ord,

Partitions the slice around the element at pivot_index.

Returns the pivot’s new index.

Panics

Panics if pivot_index is out of bounds.

Example

use rust_dsa::partition;

let mut nums = [4, 10, 3, 0, 2, 6, 7, 1, 5, 8, 9];

let pivot_index = partition(&mut nums, 0);

assert_eq!(pivot_index, 4);

for &num in &nums[..pivot_index] {
    assert!(num < nums[pivot_index]);
}

for &num in &nums[(pivot_index + 1)..] {
    assert!(nums[pivot_index] <= num);
}


let mut nums: Vec<i32> = (0..10_000).map(|_| rand::random()).collect();

let pivot_index = partition(&mut nums, 0);
let pivot = nums[pivot_index];

for &num in &nums[0..pivot_index] {
    assert!(num < pivot);
}

for &num in &nums[(pivot_index + 1)..] {
    assert!(num >= pivot);
}

let mut single = [1];
assert_eq!(partition(&mut single, 0), 0);