diff options
Diffstat (limited to 'src/utils')
| -rw-r--r-- | src/utils/sort.rs | 233 |
1 files changed, 0 insertions, 233 deletions
diff --git a/src/utils/sort.rs b/src/utils/sort.rs deleted file mode 100644 index 26cbf57..0000000 --- a/src/utils/sort.rs +++ /dev/null @@ -1,233 +0,0 @@ -/// Quick sort a slice with a custom comparison function -/// -/// # Arguments -/// * `arr` - The mutable slice to be sorted -/// * `inverse` - Sort direction: true for descending, false for ascending -/// * `compare` - Comparison function that returns -1, 0, or 1 indicating the relative order of two elements -pub fn quick_sort_with_cmp<T, F>(arr: &mut [T], inverse: bool, compare: F) -where - F: Fn(&T, &T) -> i32, -{ - quick_sort_with_cmp_helper(arr, inverse, &compare); -} - -/// Quick sort for types that implement the PartialOrd trait -/// -/// # Arguments -/// * `arr` - The mutable slice to be sorted -/// * `inverse` - Sort direction: true for descending, false for ascending -pub fn quick_sort<T: PartialOrd>(arr: &mut [T], inverse: bool) { - quick_sort_with_cmp(arr, inverse, |a, b| { - if a < b { - -1 - } else if a > b { - 1 - } else { - 0 - } - }); -} - -fn quick_sort_with_cmp_helper<T, F>(arr: &mut [T], inverse: bool, compare: &F) -where - F: Fn(&T, &T) -> i32, -{ - if arr.len() <= 1 { - return; - } - - let pivot_index = partition_with_cmp(arr, inverse, compare); - let (left, right) = arr.split_at_mut(pivot_index); - - quick_sort_with_cmp_helper(left, inverse, compare); - quick_sort_with_cmp_helper(&mut right[1..], inverse, compare); -} - -fn partition_with_cmp<T, F>(arr: &mut [T], inverse: bool, compare: &F) -> usize -where - F: Fn(&T, &T) -> i32, -{ - let len = arr.len(); - let pivot_index = len / 2; - - arr.swap(pivot_index, len - 1); - - let mut i = 0; - for j in 0..len - 1 { - let cmp_result = compare(&arr[j], &arr[len - 1]); - let should_swap = if inverse { - cmp_result > 0 - } else { - cmp_result < 0 - }; - - if should_swap { - arr.swap(i, j); - i += 1; - } - } - - arr.swap(i, len - 1); - i -} - -#[cfg(test)] -pub mod sort_test { - use crate::utils::sort::quick_sort; - use crate::utils::sort::quick_sort_with_cmp; - - #[test] - fn test_quick_sort_ascending() { - let mut arr = [3, 1, 4, 1, 5, 9, 2, 6]; - quick_sort(&mut arr, false); - assert_eq!(arr, [1, 1, 2, 3, 4, 5, 6, 9]); - } - - #[test] - fn test_quick_sort_descending() { - let mut arr = [3, 1, 4, 1, 5, 9, 2, 6]; - quick_sort(&mut arr, true); - assert_eq!(arr, [9, 6, 5, 4, 3, 2, 1, 1]); - } - - #[test] - fn test_quick_sort_single() { - let mut arr = [42]; - quick_sort(&mut arr, false); - assert_eq!(arr, [42]); - } - - #[test] - fn test_quick_sort_already_sorted() { - let mut arr = [1, 2, 3, 4, 5]; - quick_sort(&mut arr, false); - assert_eq!(arr, [1, 2, 3, 4, 5]); - } - - #[test] - fn test_quick_sort_with_cmp_by_count() { - #[derive(Debug, PartialEq)] - struct WordCount { - word: String, - count: usize, - } - - let mut words = vec![ - WordCount { - word: "apple".to_string(), - count: 3, - }, - WordCount { - word: "banana".to_string(), - count: 1, - }, - WordCount { - word: "cherry".to_string(), - count: 5, - }, - WordCount { - word: "date".to_string(), - count: 2, - }, - ]; - - quick_sort_with_cmp(&mut words, false, |a, b| { - if a.count < b.count { - -1 - } else if a.count > b.count { - 1 - } else { - 0 - } - }); - - assert_eq!( - words, - vec![ - WordCount { - word: "banana".to_string(), - count: 1 - }, - WordCount { - word: "date".to_string(), - count: 2 - }, - WordCount { - word: "apple".to_string(), - count: 3 - }, - WordCount { - word: "cherry".to_string(), - count: 5 - }, - ] - ); - - quick_sort_with_cmp(&mut words, true, |a, b| { - if a.count < b.count { - -1 - } else if a.count > b.count { - 1 - } else { - 0 - } - }); - - assert_eq!( - words, - vec![ - WordCount { - word: "cherry".to_string(), - count: 5 - }, - WordCount { - word: "apple".to_string(), - count: 3 - }, - WordCount { - word: "date".to_string(), - count: 2 - }, - WordCount { - word: "banana".to_string(), - count: 1 - }, - ] - ); - } - - #[test] - fn test_quick_sort_with_cmp_by_first_letter() { - let mut words = vec!["zebra", "apple", "banana", "cherry", "date"]; - - quick_sort_with_cmp(&mut words, false, |a, b| { - let a_first = a.chars().next().unwrap(); - let b_first = b.chars().next().unwrap(); - - if a_first < b_first { - -1 - } else if a_first > b_first { - 1 - } else { - 0 - } - }); - - assert_eq!(words, vec!["apple", "banana", "cherry", "date", "zebra"]); - - quick_sort_with_cmp(&mut words, true, |a, b| { - let a_first = a.chars().next().unwrap(); - let b_first = b.chars().next().unwrap(); - - if a_first < b_first { - -1 - } else if a_first > b_first { - 1 - } else { - 0 - } - }); - - assert_eq!(words, vec!["zebra", "date", "cherry", "banana", "apple"]); - } -} |