From cd49e78df083c9bd3a2d5fa027037ca6ab3080c8 Mon Sep 17 00:00:00 2001 From: 魏曹先生 <1992414357@qq.com> Date: Thu, 8 Jan 2026 18:54:43 +0800 Subject: Fix typo in module name from "dada_sort" to "data_sort" The module was accidentally named "dada_sort" instead of "data_sort". :) --- crates/utils/data_struct/src/dada_sort.rs | 232 ------------------------------ crates/utils/data_struct/src/data_sort.rs | 232 ++++++++++++++++++++++++++++++ crates/utils/data_struct/src/lib.rs | 2 +- 3 files changed, 233 insertions(+), 233 deletions(-) delete mode 100644 crates/utils/data_struct/src/dada_sort.rs create mode 100644 crates/utils/data_struct/src/data_sort.rs (limited to 'crates/utils') diff --git a/crates/utils/data_struct/src/dada_sort.rs b/crates/utils/data_struct/src/dada_sort.rs deleted file mode 100644 index d891dc3..0000000 --- a/crates/utils/data_struct/src/dada_sort.rs +++ /dev/null @@ -1,232 +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(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(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(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(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::dada_sort::{quick_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"]); - } -} diff --git a/crates/utils/data_struct/src/data_sort.rs b/crates/utils/data_struct/src/data_sort.rs new file mode 100644 index 0000000..2c7a452 --- /dev/null +++ b/crates/utils/data_struct/src/data_sort.rs @@ -0,0 +1,232 @@ +/// 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(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(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(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(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::data_sort::{quick_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"]); + } +} diff --git a/crates/utils/data_struct/src/lib.rs b/crates/utils/data_struct/src/lib.rs index 749b746..47cc03c 100644 --- a/crates/utils/data_struct/src/lib.rs +++ b/crates/utils/data_struct/src/lib.rs @@ -1,2 +1,2 @@ pub mod bi_map; -pub mod dada_sort; +pub mod data_sort; -- cgit