Алгоритмы сортировки путём вставок и методом Шелла. Дональд Э. Кнут. Rust
В целях практики и изучения языка программирования Rust, реализовал алгоритмы сортировки: путём вставок и методом Шелла.
//
// @author ESV Corp. (C) 05-07.09.2026
//
// "проба пера" на Rust
// алгоритмы: "сортировка путём вставок", методом Шелла (Shell)
// Д. Кнут "Искусство программирования", т.3 "Сортировка и поиск",
// глава 5.2.1. Сортировка путём вставок, Метод Шелла
//
use std::{fmt::Debug};
// тип для массива
// просто ради эксперимента
type SortArray = [i32; 16];
fn main() {
println!("Donald E. Knuth tests: sort by inserts, shellsort");
for test in 1..=4 {
// экспериментальный массив
// каждый раз новый для каждого теста
let mut r: SortArray = [5, 3, 2, 7, 1, -5, 10, 4, -3, 0, 12, 6, 7, 9, 11, 8];
match test {
// сортировка методом вставок
1 => {
// возвращается тот же массив, но он уже отсортирован
// но при этом уже не можем работать с r, т.к. произошло заимствование ссылки на изменяемые данные,
// если sorted_r будет освобождён, только тогда можно снова обратиться к r
let sorted_r = sort_by_inserts(&mut r);
// r[0] = 0; // ошибка: is assigned to here but it was already borrowed
println!("result sort by inserts: {:?}", sorted_r);
// освобождаем sorted_r
// или можно drop(sorted_r);
let sorted_r = 0;
println!("sorted_r = {:?}", sorted_r); // просто чтобы убрать предупреждение о неиспользуемой переменной
// или можно так вообще убрать из использования:
// let _ = sorted_r;
r[0] = 0; // сейчас можно снова работать с r, потому что ссылка заимствования освобождена
println!("r = {:?}", r);
// возможен ещё вот такой вариант с временным заимствованием внутри блока
{
let sorted_r2 = sort_by_inserts(&mut r);
// r[0] = 0; // ошибка: is assigned to here but it was already borrowed
println!("result sort by inserts after direct changes 1: {:?}", sorted_r2);
}
// но вот тут у нас уже sorted_r2 не существует, поэтому можем работать снова с r
r[0] = 0;
println!("result sort by inserts after direct changes 2: {:?}", r);
},
// сортировка методом Шелла, как я сам его понял
2 => {
// === Shellsort
// результат можем игнорировать, хоть и указано возвращаемое значение
shellsort(&mut r);
println!("shellsort: result itself: {:?}", r);
},
// реализация метода Шелла в соответствии с алгоритмом Кнута
3 => {
// в данном случае функция вообще ничего не возвращает
shellsort_knut(&mut r);
println!("shellsort_knut: result itself: {:?}", r);
},
// реализация метода Шелла в соответствии с алгоритмом Кнута,
// используя в параметре срез обобщённого типа
4 => {
// в данном случае функция вообще ничего не возвращает
shellsort_knut_gen(&mut r);
println!("shellsort_knut_gen: result itself: {:?}", r);
// массив произвольной длины
let mut r: Vec<i32> = vec![5, 3, 2, 7, 1, -5, 10, 4, -3, 0, 12, 6, 7, 9, 11, 8, 2, -3, 1, 0, 45, 7];
shellsort_knut_gen(&mut r);
println!("shellsort_knut_gen: result vec: {:?}", r);
},
// вариант на все остальные значения test
_ => {
println!("unknow test id={test}")
},
}
}
}
// ===
// сортировка методом вставок
// самый первый тест, первая реализация чего-то на Rust (05.09.2026)
fn sort_by_inserts(r: &mut [i32]) -> &mut [i32] {
let n: usize = r.len();
debug_assert!(n > 1, "sort_by_inserts: nothing to sort");
println!("Sort by inserts source: {:?}", r);
let mut j: usize = 1;
while j < n {
let t: i32 = r[j];
let mut i = j;
while i > 0 {
let check = r[i-1];
if check < t { break; }
r[i] = check;
i -= 1;
}
// в оригинальном агоритме Кнута значение может быть
// записано в ту же самую позицию
// видимо потому, что лишняя проверка индексов дополнительно занимает
// память программы, и ещё и для выполнения требует время
r[i] = t;
j += 1;
}
r
}
// ===
// сортировка методом Шелла (06.09.2026)
// сначала реализовал алгоритм, как понял его сам по текстовому описанию:
// проходим внутри каждого смещения (h):
// 1. находим полностью множество - элементы, отстоящие друг от друга на расстояние смещения
// 2. сортируем его методом вставки
// количество итераций ограничиваем только расстоянием смещения h, а не проходим по всем элементам
// но по сути это то же самое, что и оригинальный алгоритм Кнута, но у Кнута всё же
// элегантнее
// По описанию в книге достаточно сложно сразу понять, тем более по его описанию алгоритма,
// да ещё и одновременно эксперементируя с Rust, где индексы массивов 0..N-1, а у Кнута 1..N и индексы
// могут принимать отрицательные значения.
// Для понимания: наборы смещений h выбираются произвольно, но конечный h должен быть 1.
// У Кнута есть целое математическое обоснование, какие наборы смещений оптимальны.
fn shellsort(r: &mut [i32]) -> &mut [i32] {
let n: usize = r.len();
debug_assert!(n > 1, "shellsort: nothing to sort");
println!("Sort by shellsort source: {:?}", r);
for h in [8, 4, 2, 1].into_iter() {
let mut offset: usize = 0;
while offset < h {
let mut j: usize = h + offset;
while j < n {
let t: i32 = r[j];
let mut i: usize = j;
while i >= h {
let check = r[i-h];
if check < t { break; }
r[i] = check;
i -= h;
}
// моё дополнение - чтобы не перезаписывать одно и то же
// значение, если оно не подлежит перемещению
if i < j { r[i] = t; }
j += h; // вот тут как разница в величине шага при обходе множества
}
offset += 1; // проходим все множества внутри смещения
}
}
r
}
// ===
// сортировка методом Шелла с убывающим смещением строго по Кнуту (06.09.2026)
// и демонстрация, что наборы смещений (h) могут быть разными
fn shellsort_knut(r: &mut [i32]) {
let n: usize = r.len();
debug_assert!(n > 1, "shellsort_knut: nothing to sort");
println!("Sort by shellsort_knut source: {:?}", r);
for h in [7, 5, 3, 1].into_iter() {
let mut j: usize = h;
while j < n {
let t = r[j];
let mut i: usize = j;
while i >= h {
let check: i32 = r[i-h];
if check < t { break; }
r[i] = check;
i -= h;
}
// моё дополнение - чтобы не перезаписывать одно и то же
// значение, если оно не подлежит перемещению
if i < j { r[i] = t; }
j += 1;
}
}
}
// ===
// сортировка методом Шелла с убывающим смещением строго по Кнуту (07.09.2026)
// и демонстрация, что наборы смещений (h) могут быть разными
// реализация с помощью обобщённых типов Rust
fn shellsort_knut_gen<T>(r: &mut [T])
where T: Ord + Copy + Debug, {
let n: usize = r.len();
debug_assert!(n > 1, "shellsort_knut_gen<T>: nothing to sort");
println!("Sort by shellsort_knut_gen<T> source: {:?}", r);
for h in [7, 5, 3, 1].into_iter() {
let mut j: usize = h;
while j < n {
let t: T = r[j];
let mut i: usize = j;
while i >= h {
let check: T = r[i-h];
if check < t { break; }
r[i] = check;
i -= h;
}
// моё дополнение - чтобы не перезаписывать одно и то же
// значение, если оно не подлежит перемещению
if i < j { r[i] = t; }
j += 1;
}
}
}