Anonymous user
Sorting algorithms/Quicksort: Difference between revisions
→{{header|Rust}}
Line 4,407:
=={{header|Rust}}==
<lang rust>//
type OrderFunc<T> = Fn(&T, &T) -> bool;
// We use in place quick sort
// For details see http://en.wikipedia.org/wiki/Quicksort#In-place_version
fn quick_sort<T
let len = v.len();
if len < 2 {
Line 4,415 ⟶ 4,419:
}
let pivot_index = partition(v, f);
// Sort the left side
quick_sort(&mut v[0..pivot_index], f);
// Sort the right side
quick_sort(&mut v[pivot_index + 1..len], f);
}
Line 4,427 ⟶ 4,431:
// and values bigger than it at the right side.
// Also returns the store index.
fn partition<T
let len = v.len();
let pivot_index = len / 2;
Line 4,435 ⟶ 4,439:
let mut store_index = 0;
for i in 0..len - 1 {
if f(&v[i],
v.swap(i, store_index);
store_index += 1;
Line 4,443 ⟶ 4,447:
v.swap(store_index, len - 1);
store_index
}
// Example OrderFunc which is used to order items from least to greatest
#[inline]
fn f<T: Ord>(x: &T, y: &T) -> bool {
x < y
}
Line 4,450 ⟶ 4,460:
println!("Before: {:?}", numbers);
quick_sort(&mut numbers, &f);
println!("After: {:?}", numbers);
Line 4,457 ⟶ 4,467:
println!("Before: {:?}", strings);
quick_sort(&mut strings, &f);
println!("After: {:?}", strings);
}</lang>
| |||