(values: &mut [T])
| 1 | use crate::sorting::traits::Sorter; |
| 2 | |
| 3 | pub fn shell_sort<T: Ord + Copy>(values: &mut [T]) { |
| 4 | // shell sort works by swiping the value at a given gap and decreasing the gap to 1 |
| 5 | fn insertion<T: Ord + Copy>(values: &mut [T], start: usize, gap: usize) { |
| 6 | for i in ((start + gap)..values.len()).step_by(gap) { |
| 7 | let val_current = values[i]; |
| 8 | let mut pos = i; |
| 9 | // make swaps |
| 10 | while pos >= gap && values[pos - gap] > val_current { |
| 11 | values[pos] = values[pos - gap]; |
| 12 | pos -= gap; |
| 13 | } |
| 14 | values[pos] = val_current; |
| 15 | } |
| 16 | } |
| 17 | |
| 18 | let mut count_sublist = values.len() / 2; // makes gap as long as half of the array |
| 19 | while count_sublist > 0 { |
| 20 | for pos_start in 0..count_sublist { |
| 21 | insertion(values, pos_start, count_sublist); |
| 22 | } |
| 23 | count_sublist /= 2; // makes gap as half of previous |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | pub struct ShellSort; |
| 28 |
no test coverage detected