sorting_race/services/sorters/
shell.rs

1//! Shell Sort implementation
2
3use crate::models::traits::{Sorter, StepResult, Telemetry, Markers};
4use std::any::Any;
5
6/// Shell Sort algorithm implementation
7#[derive(Debug)]
8pub struct ShellSort {
9    data: Vec<i32>,
10    gap: usize,
11    current_pos: usize,
12    insertion_pos: usize,
13    comparisons: u64,
14    moves: u64,
15    complete: bool,
16    in_insertion: bool,
17}
18
19impl ShellSort {
20    /// Create a new ShellSort instance
21    pub fn new() -> Self {
22        Self {
23            data: Vec::new(),
24            gap: 0,
25            current_pos: 0,
26            insertion_pos: 0,
27            comparisons: 0,
28            moves: 0,
29            complete: false,
30            in_insertion: false,
31        }
32    }
33
34    /// Generate gap sequence using Knuth's sequence: 1, 4, 13, 40, 121, ...
35    fn generate_initial_gap(n: usize) -> usize {
36        let mut gap = 1;
37        while gap < n / 3 {
38            gap = gap * 3 + 1;
39        }
40        gap
41    }
42
43    fn next_gap(current_gap: usize) -> usize {
44        (current_gap - 1) / 3
45    }
46}
47
48impl Default for ShellSort {
49    fn default() -> Self {
50        Self::new()
51    }
52}
53
54impl Sorter for ShellSort {
55    fn step(&mut self, budget: usize) -> StepResult {
56        if self.complete || self.data.len() <= 1 {
57            return StepResult {
58                comparisons_used: 0,
59                moves_made: 0,
60                continued: false,
61            };
62        }
63
64        let initial_comparisons = self.comparisons;
65        let initial_moves = self.moves;
66        let mut remaining_budget = budget;
67
68        while remaining_budget > 0 && !self.complete {
69            if self.gap == 0 {
70                self.complete = true;
71                break;
72            }
73
74            if !self.in_insertion {
75                // Start new element insertion
76                if self.current_pos >= self.data.len() {
77                    // Move to next gap
78                    self.gap = Self::next_gap(self.gap);
79                    self.current_pos = self.gap;
80                    continue;
81                }
82
83                self.insertion_pos = self.current_pos;
84                self.in_insertion = true;
85            }
86
87            if self.in_insertion {
88                if self.insertion_pos >= self.gap {
89                    // Compare with element at gap distance
90                    remaining_budget -= 1;
91                    self.comparisons += 1;
92
93                    if self.data[self.insertion_pos] < self.data[self.insertion_pos - self.gap] {
94                        // Swap elements
95                        self.data.swap(self.insertion_pos, self.insertion_pos - self.gap);
96                        self.moves += 1;
97                        self.insertion_pos -= self.gap;
98                    } else {
99                        // Found correct position
100                        self.in_insertion = false;
101                        self.current_pos += 1;
102                    }
103                } else {
104                    // Reached the beginning for this gap
105                    self.in_insertion = false;
106                    self.current_pos += 1;
107                }
108            }
109        }
110
111        StepResult {
112            comparisons_used: (self.comparisons - initial_comparisons) as usize,
113            moves_made: (self.moves - initial_moves) as usize,
114            continued: !self.complete,
115        }
116    }
117
118    fn is_complete(&self) -> bool {
119        self.complete
120    }
121
122    fn get_telemetry(&self) -> Telemetry {
123        let mut markers = Markers::default();
124        
125        if !self.complete {
126            markers.gap = Some(self.gap);
127            
128            if self.in_insertion {
129                markers.cursors.push(self.insertion_pos);
130                if self.insertion_pos >= self.gap {
131                    markers.cursors.push(self.insertion_pos - self.gap);
132                }
133            } else if self.current_pos < self.data.len() {
134                markers.cursors.push(self.current_pos);
135            }
136        }
137
138        Telemetry {
139            total_comparisons: self.comparisons,
140            total_moves: self.moves,
141            memory_current: self.get_memory_usage(),
142            memory_peak: self.get_memory_usage(),
143            highlights: markers.cursors.clone(),
144            markers,
145            status_text: if self.complete {
146                "Completed".to_string()
147            } else if self.in_insertion {
148                format!("Gap {}, inserting at position {}", self.gap, self.insertion_pos)
149            } else {
150                format!("Gap {}, processing position {}", self.gap, self.current_pos)
151            },
152            progress_hint: if self.data.len() <= 1 {
153                1.0
154            } else {
155                // Estimate progress based on gap reduction
156                let initial_gap = Self::generate_initial_gap(self.data.len()) as f32;
157                let current_gap = self.gap as f32;
158                if initial_gap == 0.0 {
159                    1.0
160                } else {
161                    let progress = 1.0 - (current_gap / initial_gap);
162                    if progress.is_finite() { progress.min(1.0).max(0.0) } else { 0.0 }
163                }
164            },
165        }
166    }
167
168    fn reset(&mut self, data: Vec<i32>) {
169        self.data = data;
170        self.gap = Self::generate_initial_gap(self.data.len());
171        self.current_pos = self.gap;
172        self.insertion_pos = 0;
173        self.comparisons = 0;
174        self.moves = 0;
175        self.complete = self.data.len() <= 1;
176        self.in_insertion = false;
177    }
178
179    fn name(&self) -> &str {
180        "Shell Sort"
181    }
182
183    fn get_array(&self) -> &[i32] {
184        &self.data
185    }
186
187    fn get_memory_usage(&self) -> usize {
188        // Report size of the data array in bytes
189        self.data.len() * std::mem::size_of::<i32>()
190    }
191
192    fn as_any(&self) -> &dyn Any {
193        self
194    }
195
196    fn as_any_mut(&mut self) -> &mut dyn Any {
197        self
198    }
199}
sorting_race/services/sorters/shell.rs

sorting_race/services/sorters/
shell.rs
