Алгоритм сортировки однонаправленного связанного списка путём вставок. Дональд Э. Кнут. Rust

8 сентября 2026

//
// @author ESV Corp. (C) 08.09.2026
//
// "проба пера" на Rust
// алгоритм: "метод вставки в список"
// сортировка однонаправленного связанного списка
// Д. Кнут "Искусство программирования", т.3 "Сортировка и поиск",
// глава 5.2.1, раздел "Вставки в список"
//

const N: usize = 16;

// элемент списка
#[derive(Copy, Clone, Debug)]
struct Node {
    val:  i32,   // значение (оно же ключ)
    next: usize, // указатель на следующий элемент - индекс в массиве
}

fn main() {

    println!("Donald E. Knuth algorithms: sort linked list by inserts");

    // исходный список элементов
    let source: [i32; N] = [5, 3, 2, 7, 1, -5, 10, 4, -3, 0, 12, 6, 7, 9, 11, 8];

    // возможно
    // let mut list = [Node { val: 0, next: 0 }; N + 1];
    // но для наглядности так
    let _empty_node = Node { val: 0, next: 0 };
    // статический линейный список
    let mut list = [_empty_node; N + 1];

    // корень списка - нулевой элемент массива
    list[0].val  = -1000; // некое фиктивное значение или можно хранить дополнительную информацию
    list[0].next = 1;     // указывает на первый элемент списка

    // заполняем ноды в списке
    for i in 0..N {

        // в списке элементы расположены в массиве со смещением +1
        // корень расположен в 0-ом элементе массива
        let l_index = i + 1;

        list[l_index].val  = source[i];
        list[l_index].next = if l_index < N { l_index + 1 } else { 0 };

        #[cfg(debug_assertions)]
        println!("index={l_index} \tval={} \tnext = {:?}", list[l_index].val, list[l_index].next);

    }

    print_list(&list);

    // сортировка
    sort_linked_list_by_inserts(&mut list);

    // ---
    // динамический линейный список - динамический массив
    let mut list: Vec<Node> = vec![];

    // корень списка - нулевой элемент списка
    list.push(Node {val: -1000, next: 1});

    let a_count = 2;           // количество исходных массивов
    let i_last  = N * a_count; // индекс последнего элемента (для сравнения <, а не <=)

    // заполняем динамический список
    // для примера - 2 исходных массива
    for a in 0..a_count {
        for i in 0..N {

            // в списке элементы расположены в массиве со смещением +1
            // корень расположен в 0-ом элементе массива
            let l_index = a * N + i + 1;
            let a = a as i32;
            let val: i32 = source[i] * (a + 1) - a * 2;

            list.push(
                Node {
                    val:  val,
                    next: if l_index < i_last { l_index + 1 } else { 0 }
                }
            );

            #[cfg(debug_assertions)]
            println!("index={l_index} \tval={:4} \tnext = {:?}", list[l_index].val, list[l_index].next);

        }
    }

    print_list(&list);

    // сортировка
    sort_linked_list_by_inserts(&mut list);

}


// ===
// сортировка связанного списка методом вставок
// элементы не перемещаются, но меняются указатели на следующий элемент
fn sort_linked_list_by_inserts(r: &mut [Node]) {

    let n: usize = r.len();

    debug_assert!(n > 2, "sort_linked_list_by_inserts: nothing to sort");

    let n = n - 1;

    #[cfg(debug_assertions)]
    println!("Sort linked list by inserts source: {:?}", r);

    r[0].next = n; // устанавливаем указатель начала списка на последний элемент
    r[n].next = 0; // последний элемент - указывает на корень, что фактически означает,
                   // что он последний - это признак окончания списка, список замкнут, зациклен

    // от предпоследнего элемента списка до первого
    for j in (1..n).rev() {

        let mut q: usize = 0;         // q указывает на корень, а там хранится указатель на первый элемент
        let mut p: usize = r[q].next; // p указывает на первый элемент списка, указанный в корне (q)
                                      // q фактически всегда отстаёт от p на шаг

        let k: i32 = r[j].val; // ключ (значение) элемента для сравнения

        // пока не конец списка и текущий элемент списка r[p] меньше элемента для сравнения
        while p > 0 && r[p].val < k {
            q = p;         // позиция рассмотренного, q отстаёт на шаг
            p = r[p].next; // следующий элемент в списке
        }

        // элемент вставляется перед p, после q
        r[q].next = j;
        r[j].next = p;

    }

    println!("Sort linked list by inserts sorted:");
    print_list(&r);

    #[cfg(debug_assertions)]
    println!("Sort linked list by inserts sorted (debug): {:?}", r);

}


// печать связанного списка
fn print_list(list: &[Node]) {

    let mut i = list[0].next;

    while i > 0 {
        print!("{}{}", list[i].val, if list[i].next == 0 { "\n" } else { ", " });
        i = list[i].next;
    }
}