5. Ordenado rápido
123456789101112131415161718192021222324252627282930313233343536373839404142434445
pub fn orden_rapido<T: Ord>(arr: &mut [T]) {
let len = arr.len();
orden_rapido1(arr, 0, (len - 1) as isize);
}
fn orden_rapido1<T: Ord>(arr: &mut [T], bajo: isize, alto: isize) {
if bajo < alto {
let p = partition(arr, bajo, alto);
orden_rapido1(arr, bajo, p - 1);
orden_rapido1(arr, p + 1, alto);
}
}
fn partition<T: Ord>(arr: &mut [T], bajo: isize, alto: isize) -> isize {
let pivot = alto as usize;
let mut almacen = bajo - 1;
let mut ultimo = alto;
loop {
almacen += 1;
while arr[almacen as usize] < arr[pivot] {
almacen += 1;
}
ultimo -= 1;
while ultimo >= 0 && arr[ultimo as usize] > arr[pivot] {
ultimo -= 1;
}
if almacen >= ultimo {
break;
} else {
arr.swap(almacen as usize, ultimo as usize);
}
}
arr.swap(almacen as usize, pivot as usize);
almacen
}
fn main() {
let mut array = [5, 7, 2, 1, 3, 4, 6];
println!("{:?}", array);
orden_rapido(&mut array);
println!("{:?}\n", array);
}
Rust
INFO