sorting_race/services/sorters/
insertion.rs

1//! Insertion Sort implementation
2
3use crate::models::traits::{Sorter, StepResult, Telemetry, Markers};
4use std::any::Any;
5
6/// Insertion Sort algorithm implementation
7#[derive(Debug)]
8pub struct InsertionSort {
9    data: Vec<i32>,
10    current_index: usize,
11    insert_pos: usize,
12    comparisons: u64,
13    moves: u64,
14    complete: bool,
15    in_insertion: bool,
16}
17
18impl InsertionSort {
19    /// Create a new InsertionSort instance
20    pub fn new() -> Self {
21        Self {
22            data: Vec::new(),
23            current_index: 1,
24            insert_pos: 0,
25            comparisons: 0,
26            moves: 0,
27            complete: false,
28            in_insertion: false,
29        }
30    }
31}
32
33impl Default for InsertionSort {
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl Sorter for InsertionSort {
40    fn step(&mut self, budget: usize) -> StepResult {
41        if self.complete || self.data.len() <= 1 {
42            return StepResult {
43                comparisons_used: 0,
44                moves_made: 0,
45                continued: false,
46            };
47        }
48
49        let mut comparisons_used = 0;
50        let mut moves_made = 0;
51
52        while comparisons_used < budget && !self.complete {
53            if !self.in_insertion {
54                if self.current_index >= self.data.len() {
55                    self.complete = true;
56                    break;
57                }
58                
59                self.insert_pos = self.current_index;
60                self.in_insertion = true;
61            }
62
63            if self.in_insertion && self.insert_pos > 0 {
64                // Compare with previous element
65                comparisons_used += 1;
66                self.comparisons += 1;
67
68                if self.data[self.insert_pos] < self.data[self.insert_pos - 1] {
69                    // Swap elements
70                    self.data.swap(self.insert_pos, self.insert_pos - 1);
71                    moves_made += 1;
72                    self.moves += 1;
73                    self.insert_pos -= 1;
74                } else {
75                    // Found correct position
76                    self.in_insertion = false;
77                    self.current_index += 1;
78                }
79            } else {
80                // Reached beginning of array or not in insertion
81                self.in_insertion = false;
82                self.current_index += 1;
83            }
84        }
85
86        StepResult {
87            comparisons_used,
88            moves_made,
89            continued: !self.complete,
90        }
91    }
92
93    fn is_complete(&self) -> bool {
94        self.complete
95    }
96
97    fn get_telemetry(&self) -> Telemetry {
98        let mut markers = Markers::default();
99        
100        if !self.complete {
101            if self.in_insertion {
102                markers.cursors = vec![self.insert_pos];
103                if self.insert_pos > 0 {
104                    markers.cursors.push(self.insert_pos - 1);
105                }
106            } else if self.current_index < self.data.len() {
107                markers.cursors = vec![self.current_index];
108            }
109        }
110
111        Telemetry {
112            total_comparisons: self.comparisons,
113            total_moves: self.moves,
114            memory_current: self.get_memory_usage(),
115            memory_peak: self.get_memory_usage(),
116            highlights: markers.cursors.clone(),
117            markers,
118            status_text: if self.complete {
119                "Completed".to_string()
120            } else if self.in_insertion {
121                format!("Inserting element at index {}", self.insert_pos)
122            } else {
123                format!("Processing index {}", self.current_index)
124            },
125            progress_hint: if self.data.len() <= 1 {
126                1.0
127            } else {
128                let progress = (self.current_index as f32) / (self.data.len() as f32);
129                progress.min(1.0).max(0.0) // Clamp to [0.0, 1.0]
130            },
131        }
132    }
133
134    fn reset(&mut self, data: Vec<i32>) {
135        self.data = data;
136        self.current_index = 1;
137        self.insert_pos = 0;
138        self.comparisons = 0;
139        self.moves = 0;
140        self.complete = self.data.len() <= 1;
141        self.in_insertion = false;
142    }
143
144    fn name(&self) -> &str {
145        "Insertion Sort"
146    }
147
148    fn get_array(&self) -> &[i32] {
149        &self.data
150    }
151
152    fn get_memory_usage(&self) -> usize {
153        // Report size of the data array in bytes
154        self.data.len() * std::mem::size_of::<i32>()
155    }
156
157    fn as_any(&self) -> &dyn Any {
158        self
159    }
160
161    fn as_any_mut(&mut self) -> &mut dyn Any {
162        self
163    }
164}
sorting_race/services/sorters/insertion.rs

sorting_race/services/sorters/
insertion.rs
