sorting_race/services/sorters/
selection.rs

1//! Selection Sort implementation
2
3use crate::models::traits::{Sorter, StepResult, Telemetry, Markers};
4use std::any::Any;
5
6/// Selection Sort algorithm implementation
7#[derive(Debug)]
8pub struct SelectionSort {
9    data: Vec<i32>,
10    current_position: usize,
11    search_index: usize,
12    min_index: usize,
13    comparisons: u64,
14    moves: u64,
15    complete: bool,
16}
17
18impl SelectionSort {
19    /// Create a new SelectionSort instance
20    pub fn new() -> Self {
21        Self {
22            data: Vec::new(),
23            current_position: 0,
24            search_index: 1,
25            min_index: 0,
26            comparisons: 0,
27            moves: 0,
28            complete: false,
29        }
30    }
31}
32
33impl Default for SelectionSort {
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl Sorter for SelectionSort {
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.current_position >= self.data.len() - 1 {
54                self.complete = true;
55                break;
56            }
57
58            if self.search_index < self.data.len() {
59                // Compare current element with minimum found so far
60                comparisons_used += 1;
61                self.comparisons += 1;
62
63                if self.data[self.search_index] < self.data[self.min_index] {
64                    self.min_index = self.search_index;
65                }
66
67                self.search_index += 1;
68            } else {
69                // Found minimum for this pass, swap if necessary
70                if self.min_index != self.current_position {
71                    self.data.swap(self.current_position, self.min_index);
72                    moves_made += 1;
73                    self.moves += 1;
74                }
75
76                // Move to next position
77                self.current_position += 1;
78                if self.current_position < self.data.len() {
79                    self.search_index = self.current_position + 1;
80                    self.min_index = self.current_position;
81                }
82            }
83        }
84
85        StepResult {
86            comparisons_used,
87            moves_made,
88            continued: !self.complete,
89        }
90    }
91
92    fn is_complete(&self) -> bool {
93        self.complete
94    }
95
96    fn get_telemetry(&self) -> Telemetry {
97        let mut markers = Markers::default();
98        
99        if !self.complete {
100            if self.search_index < self.data.len() {
101                markers.cursors = vec![self.current_position, self.search_index, self.min_index];
102            } else if self.current_position < self.data.len() {
103                markers.cursors = vec![self.current_position, self.min_index];
104            }
105        }
106
107        // Remove duplicates and sort
108        markers.cursors.sort_unstable();
109        markers.cursors.dedup();
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.search_index < self.data.len() {
121                format!("Position {}, searching at {}, min at {}", 
122                       self.current_position, self.search_index, self.min_index)
123            } else {
124                format!("Position {}, found min at {}", self.current_position, self.min_index)
125            },
126            progress_hint: if self.data.len() <= 1 {
127                1.0
128            } else {
129                let progress = (self.current_position as f32) / ((self.data.len() - 1) as f32);
130                progress.min(1.0).max(0.0) // Clamp to [0.0, 1.0]
131            },
132        }
133    }
134
135    fn reset(&mut self, data: Vec<i32>) {
136        self.data = data;
137        self.current_position = 0;
138        self.search_index = 1;
139        self.min_index = 0;
140        self.comparisons = 0;
141        self.moves = 0;
142        self.complete = self.data.len() <= 1;
143    }
144
145    fn name(&self) -> &str {
146        "Selection Sort"
147    }
148
149    fn get_array(&self) -> &[i32] {
150        &self.data
151    }
152
153    fn get_memory_usage(&self) -> usize {
154        // Report size of the data array in bytes
155        self.data.len() * std::mem::size_of::<i32>()
156    }
157
158    fn as_any(&self) -> &dyn Any {
159        self
160    }
161
162    fn as_any_mut(&mut self) -> &mut dyn Any {
163        self
164    }
165}
sorting_race/services/sorters/selection.rs

sorting_race/services/sorters/
selection.rs
