From 89e82439186c6dfa48a73bddc0908a494fbd4394 Mon Sep 17 00:00:00 2001
From: JSDurand <mmemmew@gmail.com>
Date: Sat, 11 Mar 2023 16:21:20 +0800
Subject: 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.
---
 src/main.rs | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

(limited to 'src/main.rs')

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}");
 }
-- 
cgit v1.2.3-18-g5258