sort_it/algorithms/
insertion_sort.rs

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

sort_it/algorithms/
insertion_sort.rs
