sort_it/algorithms/
slowsort.rs

1use std::time::{ Instant, Duration };
2
3/// A trait providing the slowsort algorithm.
4pub trait Slowsort<T: PartialEq + PartialOrd + Clone + Copy> {
5    /// The slowsort algorithm.
6    ///
7    /// Sorts the `Vec` it is called on.
8    fn slowsort(&mut self);
9
10    /// The slowsort algorithm but timed.
11    ///
12    /// Sorts the `Vec` it is called on and returns the `Duration` of the process.
13    fn slowsort_timed(&mut self) -> Duration;
14
15    /// The slowsort algorithm but stepped.
16    ///
17    /// Sorts the `Vec` it is called on and returns a `Vec` containing each step of the process.
18    fn slowsort_stepped(&mut self) -> Vec<Vec<T>>;
19
20    /// The slowsort 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 slowsort_stepped_and_timed(&mut self) -> (Vec<Vec<T>>, Duration);
25}
26
27/// The trait implementation of the slowsort algorithm.
28impl<T> Slowsort<T> for Vec<T> 
29    where T: PartialEq + PartialOrd + Clone + Copy,
30{
31    fn slowsort(&mut self) {
32        // NOTE: this may be too serious of an optimization 
33        //       for the kind of algorithm this is (and might 
34        //       even defeat the purpose).
35        if self.len() <= 1 {
36            return;
37        }
38
39        let length = self.len();
40        slowsort_rec(self, 0, length - 1);
41    }
42
43    fn slowsort_timed(&mut self) -> Duration {
44        let time = Instant::now();
45
46        // NOTE: this may be too serious of an optimization 
47        //       for the kind of algorithm this is (and might 
48        //       even defeat the purpose).
49        if self.len() <= 1 {
50            return time.elapsed();
51        }
52
53        let length = self.len();
54        slowsort_rec(self, 0, length - 1);
55
56        return time.elapsed();
57    }
58
59    fn slowsort_stepped(&mut self) -> Vec<Vec<T>> {
60        let mut steps = vec![self.clone()];
61
62        // NOTE: this may be too serious of an optimization 
63        //       for the kind of algorithm this is (and might 
64        //       even defeat the purpose).
65        if self.len() <= 1 {
66            return steps;
67        }
68
69        let length = self.len();
70        slowsort_rec_stepped(self, 0, length - 1, &mut steps);
71
72        return steps;
73    }
74
75    fn slowsort_stepped_and_timed(&mut self) -> (Vec<Vec<T>>, Duration) {
76        let time = Instant::now();
77
78        let mut steps = vec![self.clone()];
79
80        // NOTE: this may be too serious of an optimization 
81        //       for the kind of algorithm this is (and might 
82        //       even defeat the purpose).
83        if self.len() <= 1 {
84            return (steps, time.elapsed());
85        }
86
87        let length = self.len();
88        slowsort_rec_stepped(self, 0, length - 1, &mut steps);
89
90        (steps, time.elapsed())
91    }
92}
93
94/// The slowsort algorithm.
95///
96/// Sorts the given `Vec` and returns the result.
97pub fn slowsort<T>(mut arr: Vec<T>) -> Vec<T>
98    where T: PartialEq + PartialOrd + Clone + Copy,
99{
100    // NOTE: this may be too serious of an optimization 
101    //       for the kind of algorithm this is (and might 
102    //       even defeat the purpose).
103    if arr.len() <= 1 {
104        return arr;
105    }
106
107    let length = arr.len();
108    slowsort_rec(&mut arr, 0, length - 1);
109
110    return arr;
111}
112
113/// The slowsort algorithm but timed.
114///
115/// Sorts the given `Vec` and returns the result and the `Duration` of the process.
116pub fn slowsort_timed<T>(mut arr: Vec<T>) -> (Vec<T>, Duration)
117    where T: PartialEq + PartialOrd + Clone + Copy,
118{
119    let time = Instant::now();
120
121    // NOTE: this may be too serious of an optimization 
122    //       for the kind of algorithm this is (and might 
123    //       even defeat the purpose).
124    if arr.len() <= 1 {
125        return (arr, time.elapsed());
126    }
127
128    let length = arr.len();
129    slowsort_rec(&mut arr, 0, length - 1);
130
131    (arr, time.elapsed())
132}
133
134/// The slowsort algorithm but stepped.
135///
136/// Sorts the given `Vec` and returns the result and a `Vec` containing each step of the process.
137pub fn slowsort_stepped<T>(mut arr: Vec<T>) -> (Vec<T>, Vec<Vec<T>>)
138    where T: PartialEq + PartialOrd + Clone + Copy,
139{
140    let mut steps = vec![arr.clone()];
141
142    // NOTE: this may be too serious of an optimization 
143    //       for the kind of algorithm this is (and might 
144    //       even defeat the purpose).
145    if arr.len() <= 1 {
146        return (arr, steps);
147    }
148
149    let length = arr.len();
150    slowsort_rec_stepped(&mut arr, 0, length - 1, &mut steps);
151
152    (arr, steps)
153}
154
155/// The slowsort algorithm but stepped _and_ timed.
156///
157/// Sorts the given `Vec` and returns the result and a `Vec` containing each step of the process,
158/// including the `Duration` of the entire process.
159pub fn slowsort_stepped_and_timed<T>(mut arr: Vec<T>) -> (Vec<T>, Vec<Vec<T>>, Duration) 
160    where T: PartialEq + PartialOrd + Clone + Copy,
161{
162    let time = Instant::now();
163
164    let mut steps = vec![arr.clone()];
165
166    // NOTE: this may be too serious of an optimization 
167    //       for the kind of algorithm this is (and might 
168    //       even defeat the purpose).
169    if arr.len() <= 1 {
170        return (arr, steps, time.elapsed());
171    }
172
173    let length = arr.len();
174    slowsort_rec_stepped(&mut arr, 0, length - 1, &mut steps);
175
176    (arr, steps, time.elapsed())
177}
178
179/// Auxiliary function.
180fn slowsort_rec<T>(arr: &mut Vec<T>, i: usize, j: usize) 
181    where T: PartialEq + PartialOrd + Clone + Copy,
182{
183    if i >= j {
184        return;
185    }
186
187    let m = (i + j) / 2;
188
189    slowsort_rec(arr, i, m);
190    slowsort_rec(arr, m+1, j);
191
192    if arr[m] > arr[j] {
193        arr.swap(m, j);
194    }
195
196    slowsort_rec(arr, i, j-1);
197}
198
199/// Auxiliary function (with stepped support).
200fn slowsort_rec_stepped<T>(arr: &mut Vec<T>, i: usize, j: usize, steps: &mut Vec<Vec<T>>)
201    where T: PartialEq + PartialOrd + Clone + Copy,
202{
203    if i >= j {
204        return;
205    }
206
207    let m = (i + j) / 2;
208
209    slowsort_rec(arr, i, m);
210    slowsort_rec(arr, m+1, j);
211
212    if arr[m] > arr[j] {
213        arr.swap(m, j);
214        steps.push(arr.clone());
215    }
216
217    slowsort_rec(arr, i, j-1);
218}
sort_it/algorithms/slowsort.rs

sort_it/algorithms/
slowsort.rs
