sort_it/algorithms/
gnome_sort.rs

1use std::time::{ Instant, Duration };
2
3/// A trait providing the gnome sort method.
4pub trait GnomeSort<T: PartialEq + PartialOrd + Clone + Copy> {
5    /// The gnome sort algorithm.
6    ///
7    /// Sorts the `Vec` it is called on.
8    fn gnome_sort(&mut self);
9
10    /// The gnome sort algorithm but timed.
11    ///
12    /// Sorts the `Vec` it is called on and returns the `Duration` of the process.
13    fn gnome_sort_timed(&mut self) -> Duration;
14
15    /// The gnome 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 gnome_sort_stepped(&mut self) -> Vec<Vec<T>>;
19
20    /// The gnome 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 a `Duration` of the entire process.
24    fn gnome_sort_stepped_and_timed(&mut self) -> (Vec<Vec<T>>, Duration);
25}
26
27/// The trait implementation of the bogosort algorithm.
28impl<T> GnomeSort<T> for Vec<T>
29    where T: PartialEq + PartialOrd + Clone + Copy,
30{
31    fn gnome_sort(&mut self) {
32        if self.len() <= 1 {
33            return;
34        }
35
36        let mut i = 1;
37
38        while i < self.len() {
39            if self[i] < self[i-1] {
40                let tmp = self[i];
41                self[i] = self[i-1];
42                self[i-1] = tmp;
43
44                if i > 1 {
45                    i -= 1;
46                }
47            } else {
48                i += 1;
49            }
50        }
51    }
52
53    fn gnome_sort_timed(&mut self) -> Duration {
54        let time = Instant::now();
55
56        if self.len() <= 1 {
57            return time.elapsed();
58        }
59
60        let mut i = 1;
61
62        while i < self.len() {
63            if self[i] < self[i-1] {
64                let tmp = self[i];
65                self[i] = self[i-1];
66                self[i-1] = tmp;
67
68                if i > 1 {
69                    i -= 1;
70                }
71            } else {
72                i += 1;
73            }
74        }
75
76        return time.elapsed();
77    }
78
79    fn gnome_sort_stepped(&mut self) -> Vec<Vec<T>> {
80        let mut steps = vec![self.clone()];
81
82        if self.len() <= 1 {
83            return steps;
84        }
85
86        let mut i = 1;
87
88        while i < self.len() {
89            if self[i] < self[i-1] {
90                let tmp = self[i];
91                self[i] = self[i-1];
92                self[i-1] = tmp;
93
94                steps.push(self.clone());
95
96                if i > 1 {
97                    i -= 1;
98                }
99            } else {
100                i += 1;
101            }
102        }
103
104        return steps;
105    }
106
107    fn gnome_sort_stepped_and_timed(&mut self) -> (Vec<Vec<T>>, Duration){
108        let time = Instant::now();
109
110        let mut steps = vec![self.clone()];
111
112        if self.len() <= 1 {
113            return (steps, time.elapsed());
114        }
115
116        let mut i = 1;
117
118        while i < self.len() {
119            if self[i] < self[i-1] {
120                let tmp = self[i];
121                self[i] = self[i-1];
122                self[i-1] = tmp;
123
124                steps.push(self.clone());
125
126                if i > 1 {
127                    i -= 1;
128                }
129            } else {
130                i += 1;
131            }
132        }
133
134        return (steps, time.elapsed());
135    }
136}
137
138/// The gnome sort algorithm.
139///
140/// Sorts a given `Vec` and returns the result.
141pub fn gnome_sort<T>(mut arr: Vec<T>) -> Vec<T> 
142    where T: PartialEq + PartialOrd + Clone + Copy,
143{
144    // If the array only contains one element, it's sorted by default.
145    if arr.len() <= 1 {
146        return arr;
147    }
148
149    // We start at one since the gnome can only 
150    // compare the current pot with the previous one.
151    let mut i = 1;
152
153    while i < arr.len() {
154        if arr[i] < arr[i-1] {
155            let tmp = arr[i];
156            arr[i] = arr[i-1];
157            arr[i-1] = tmp;
158
159            if i > 1 {
160                i -= 1;
161            }
162        } else {
163            i += 1;
164        }
165    }
166
167    return arr;
168}
169
170/// The gnome sort algorithm but timed.
171///
172/// Sorts a given `Vec` and returns the result and the `Duration` of the process.
173pub fn gnome_sort_timed<T>(mut arr: Vec<T>) -> (Vec<T>, Duration) 
174    where T: PartialEq + PartialOrd + Clone + Copy,
175{
176    let time = Instant::now();
177
178    // If the array only contains one element, it's sorted by default.
179    if arr.len() <= 1 {
180        return (arr, time.elapsed());
181    }
182
183    // We start at one since the gnome can only 
184    // compare the current pot with the previous one.
185    let mut i = 1;
186
187    while i < arr.len() {
188        if arr[i] < arr[i-1] {
189            let tmp = arr[i];
190            arr[i] = arr[i-1];
191            arr[i-1] = tmp;
192
193            if i > 1 {
194                i -= 1;
195            }
196        } else {
197            i += 1;
198        }
199    }
200
201    (arr, time.elapsed())
202}
203
204/// The gnome sort algorithm but stepped.
205///
206/// Sorts a given `Vec` and returns the result and a `Vec` containing each step of the process.
207pub fn gnome_sort_stepped<T>(mut arr: Vec<T>) -> (Vec<T>, Vec<Vec<T>>) 
208    where T: PartialEq + PartialOrd + Clone + Copy,
209{
210    let mut steps = vec![arr.clone()];
211
212    // If the array only contains one element, it's sorted by default.
213    if arr.len() <= 1 {
214        return (arr, steps);
215    }
216
217    // We start at one since the gnome can only 
218    // compare the current pot with the previous one.
219    let mut i = 1;
220
221    while i < arr.len() {
222        if arr[i] < arr[i-1] {
223            let tmp = arr[i];
224            arr[i] = arr[i-1];
225            arr[i-1] = tmp;
226
227            // Push the current state to the list of steps.
228            steps.push(arr.clone());
229
230            if i > 1 {
231                i -= 1;
232            }
233        } else {
234            i += 1;
235        }
236    }
237
238    (arr, steps)
239}
240
241/// The gnome sort algorithm but stepped _and_ timed.
242///
243/// Sorts a given `Vec` and returns the result and a `Vec` containing each step of the 
244/// process, including the `Duration` of the process.
245pub fn gnome_sort_stepped_and_timed<T>(mut arr: Vec<T>) -> (Vec<T>, Vec<Vec<T>>, Duration) 
246    where T: PartialEq + PartialOrd + Clone + Copy,
247{
248    let time = Instant::now();
249
250    let mut steps = vec![arr.clone()];
251
252    // If the array only contains one element, it's sorted by default.
253    if arr.len() <= 1 {
254        return (arr, steps, time.elapsed());
255    }
256
257    // We start at one since the gnome can only 
258    // compare the current pot with the previous one.
259    let mut i = 1;
260
261    while i < arr.len() {
262        if arr[i] < arr[i-1] {
263            let tmp = arr[i];
264            arr[i] = arr[i-1];
265            arr[i-1] = tmp;
266
267            // Push the current state to the list of steps.
268            steps.push(arr.clone());
269
270            if i > 1 {
271                i -= 1;
272            }
273        } else {
274            i += 1;
275        }
276    }
277
278    (arr, steps, time.elapsed())
279}
sort_it/algorithms/gnome_sort.rs

sort_it/algorithms/
gnome_sort.rs
