sort_it/algorithms/
selection_sort.rs

1use std::time::{ Instant, Duration };
2
3/// A trait providing the selection sort algorithm.
4pub trait SelectionSort<T: PartialEq + PartialOrd + Clone + Copy> {
5    /// The selection sort algorithm.
6    ///
7    /// Sorts the `Vec` it is called on.
8    fn selection_sort(&mut self);
9
10    /// The selection sort algorithm but timed.
11    ///
12    /// Sorts the `Vec` it is called on and returns the `Duration` of the process.
13    fn selection_sort_timed(&mut self) -> Duration;
14
15    /// The selection sort algorithm but stepped.
16    ///
17    /// Sorts the `Vec` it is called on and returns a `Vec` containing each step of the process.
18    fn selection_sort_stepped(&mut self) -> Vec<(Vec<T>, Vec<T>)>;
19
20    /// The selection sort algorithm but stepped _and_ timed.
21    ///
22    /// Sorts the `Vec` it is called on and returns a `Vec` containing each step of the process,
23    /// including the `Duration` of the entire process.
24    fn selection_sort_stepped_and_timed(&mut self) -> (Vec<(Vec<T>, Vec<T>)>, Duration);
25}
26
27/// The trait implementation of the selection sort algorithm.
28impl<T> SelectionSort<T> for Vec<T>
29    where T: PartialEq + PartialOrd + Clone + Copy,
30{
31    fn selection_sort(&mut self) {
32        if self.len() <= 1 {
33            return;
34        }
35
36        let mut sorted = vec![];
37
38        while self.len() > 0 {
39            let mut min_idx = 0;
40            for i in 0..self.len() {
41                if self[min_idx] > self[i] {
42                    min_idx = i;
43                }
44            }
45            sorted.push(self.remove(min_idx));
46        }
47
48        *self = sorted;
49    }
50
51    fn selection_sort_timed(&mut self) -> Duration {
52        let time = Instant::now();
53
54        if self.len() <= 1 {
55            return time.elapsed();
56        }
57
58        let mut sorted = vec![];
59
60        while self.len() > 0 {
61            let mut min_idx = 0;
62            for i in 0..self.len() {
63                if self[min_idx] > self[i] {
64                    min_idx = i;
65                }
66            }
67            sorted.push(self.remove(min_idx));
68        }
69
70        *self = sorted;
71
72        return time.elapsed();
73    }
74
75    fn selection_sort_stepped(&mut self) -> Vec<(Vec<T>, Vec<T>)> {
76        let mut steps = vec![(self.clone(), vec![])];
77
78        if self.len() <= 1 {
79            return steps;
80        }
81
82        let mut sorted = vec![];
83
84        while self.len() > 0 {
85            let mut min_idx = 0;
86            for i in 0..self.len() {
87                if self[min_idx] > self[i] {
88                    min_idx = i;
89                }
90            }
91            sorted.push(self.remove(min_idx));
92            steps.push((self.clone(), sorted.clone()));
93        }
94
95        *self = sorted;
96
97        return steps;
98    }
99
100    fn selection_sort_stepped_and_timed(&mut self) -> (Vec<(Vec<T>, Vec<T>)>, Duration) {
101        let time = Instant::now();
102
103        let mut steps = vec![(self.clone(), vec![])];
104
105        if self.len() <= 1 {
106            return (steps, time.elapsed());
107        }
108
109        let mut sorted = vec![];
110
111        while self.len() > 0 {
112            let mut min_idx = 0;
113            for i in 0..self.len() {
114                if self[min_idx] > self[i] {
115                    min_idx = i;
116                }
117            }
118            sorted.push(self.remove(min_idx));
119            steps.push((self.clone(), sorted.clone()));
120        }
121
122        *self = sorted;
123
124        (steps, time.elapsed())
125    }
126}
127
128/// The selection sort algorithm.
129///
130/// Sorts the given `Vec` and returns the result.
131pub fn selection_sort<T>(mut arr: Vec<T>) -> Vec<T>
132    where T: PartialEq + PartialOrd + Clone + Copy,
133{
134    if arr.len() <= 1 {
135        return arr;
136    }
137
138    let mut sorted = vec![];
139
140    while arr.len() > 0 {
141        let mut min_idx = 0;
142        for i in 0..arr.len() {
143            if arr[min_idx] > arr[i] {
144                min_idx = i;
145            }
146        }
147        sorted.push(arr.remove(min_idx));
148    }
149
150    return sorted;
151}
152
153/// The selection sort algorithm but timed.
154///
155/// Sorts the given `Vec` and returns the result and the `Duration` of the entire process.
156pub fn selection_sort_timed<T>(mut arr: Vec<T>) -> (Vec<T>, Duration)
157    where T: PartialEq + PartialOrd + Clone + Copy,
158{
159    let time = Instant::now();
160
161    if arr.len() <= 1 {
162        return (arr, time.elapsed());
163    }
164
165    let mut sorted = vec![];
166
167    while arr.len() > 0 {
168        let mut min_idx = 0;
169        for i in 0..arr.len() {
170            if arr[min_idx] > arr[i] {
171                min_idx = i;
172            }
173        }
174        sorted.push(arr.remove(min_idx));
175    }
176
177    (sorted, time.elapsed())
178}
179
180/// The selection sort algorithm but stepped.
181///
182/// Sorts the given `Vec` and returns the result and a `Vec` containing the steps of the 
183/// process as a tuple of the unsorted and sorted array.
184pub fn selection_sort_stepped<T>(mut arr: Vec<T>) -> (Vec<T>, Vec<(Vec<T>, Vec<T>)>)
185    where T: PartialEq + PartialOrd + Clone + Copy,
186{
187    let mut steps = vec![(arr.clone(), vec![])];
188
189    if arr.len() <= 1 {
190        return (arr, steps);
191    }
192
193    let mut sorted = vec![];
194
195    while arr.len() > 0 {
196        let mut min_idx = 0;
197        for i in 0..arr.len() {
198            if arr[min_idx] > arr[i] {
199                min_idx = i;
200            }
201        }
202
203        sorted.push(arr.remove(min_idx));
204        steps.push((arr.clone(), sorted.clone()));
205    }
206
207    (sorted, steps)
208}
209
210/// The selection sort algorithm but stepped _and_ timed.
211///
212/// Sorts the given `Vec` and returns the result and a `Vec` containing the steps of the 
213/// process as a tuple of the unsorted and sorted array, including the `Duration` of the 
214/// entire process.
215pub fn selection_sort_stepped_and_timed<T>(mut arr: Vec<T>) -> (Vec<T>, Vec<(Vec<T>, Vec<T>)>, Duration)
216    where T: PartialEq + PartialOrd + Clone + Copy,
217{
218    let time = Instant::now();
219
220    let mut steps = vec![(arr.clone(), vec![])];
221
222    if arr.len() <= 1 {
223        return (arr, steps, time.elapsed());
224    }
225
226    let mut sorted = vec![];
227
228    while arr.len() > 0 {
229        let mut min_idx = 0;
230        for i in 0..arr.len() {
231            if arr[min_idx] > arr[i] {
232                min_idx = i;
233            }
234        }
235
236        sorted.push(arr.remove(min_idx));
237        steps.push((arr.clone(), sorted.clone()));
238    }
239
240    (sorted, steps, time.elapsed())
241}
242
sort_it/algorithms/selection_sort.rs

sort_it/algorithms/
selection_sort.rs
