1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
use super::{SortingAlgorithm, SortingStatsTrait}; #[derive(Debug, Default)] pub struct BubbleSort; impl SortingAlgorithm for BubbleSort { fn sort_with_stats<T, S>(&self, slice: &mut [T], mut stats: S) -> S where T: Ord, S: SortingStatsTrait, { let mut something_got_swapped = true; while something_got_swapped { something_got_swapped = false; for i in 1..slice.len() { stats.comparison(); if slice[i - 1] > slice[i] { slice.swap(i - 1, i); stats.swap(); something_got_swapped = true; } } } stats } } #[cfg(test)] mod tests { use super::*; use crate::SortingStats; #[test] fn bubblesort() { let mut v = [3, 2, 1, 7, 6]; assert_eq!( BubbleSort.sort_with_stats(&mut v[..], SortingStats::default()), SortingStats { comparisons: 12, swaps: 4 } ); assert_eq!(v, [1, 2, 3, 6, 7]); } }