optimize the implementation

Now the double for loop is eliminated and the time complexity is
indeed O(n log(n)).

Also added (micro)-benchmarks to roughly confirm the time complexity
is as predicted.

1 files changed, 16 insertions, 0 deletions

diff --git a/src/main.rs b/src/main.rs
index 64709b1..f223aeb 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -55,6 +55,8 @@ fn sm1<T: PartialOrd>(a: Vec<T>, count: &mut usize) -> (usize, Graph) {
                     *indices.get_mut(i).unwrap() = y;
                 }
                 None => {
+                    *count += 1;
+
                     if a.get(x).unwrap().partial_cmp(a.get(x).unwrap()).is_some() {
                         *indices.get_mut(i).unwrap() = x;
                     } else {
@@ -181,4 +183,18 @@ fn main() {
         .collect();
 
     println!("sort indices = {sort:?}\nsort result: {sort_result:?}\ncount = {count}");
+
+    // Now use the optimized version
+
+    count = 0;
+
+    let sort = sort::sm(inputs.as_slice(), &mut count);
+
+    let sort_result: Vec<f32> = sort
+        .iter()
+        .copied()
+        .map(|n| inputs.get(n).copied().unwrap())
+        .collect();
+
+    println!("sort indices = {sort:?}\nsort result: {sort_result:?}\ncount = {count}");
 }