use chrono::Duration;
// Time Complexity O(n^2)
// Space Complexity O(1)
// neighbours change places until a pass makes no swaps:
// the largest element "bubbles up" to the end on every pass
fn sort(items: &mut [i32])
{
for end in (2..=items.len()).rev() {
let mut swapped = false;
for j in 1..end {
if items[j] < items[j - 1] {
let tmp = items[j];
items[j] = items[j - 1];
items[j - 1] = tmp;
swapped = true;
}
}
if !swapped {
break;
}
}
}
let mut nums = [ 4, 1, 5, 3, 2 ];
sort(&mut nums);
// sortItems is {1, 2, 3, 4, 5}
println!("nums is {:?}", nums);
// *** simplified speed test ***
let mut items = [0i32; 200];
for i in 0..items.len() {
items[i] = (items.len() - 1 - i) as i32;
}
let count = 1000;
let start = chrono::offset::Utc::now();
for _ in 1..count {
let mut work = items;
sort(&mut work);
}
let now = chrono::offset::Utc::now();
let delta: Duration = now - start;
println!("milliseconds is {}",
delta.num_milliseconds());
println!("items is {:?}", items);
// about 115 milliseconds