Алгоритм quicksort "быстрая сортировка". Роберт Седживик, Дональд Э. Кнут. Rust

17 сентября 2026

//
// @author ESV Corp. (C) 17.09.2026
//
// "проба пера" на Rust
// алгоритм: "быстрая сортировка", quicksort
// Р. Седжвик "Алгоритмы",
// Д. Кнут "Искусство программирования", т.3 "Сортировка и поиск",
// глава 5.2.2, раздел "Обменная сортировка"
//
// сначала происходит разделение массива на подмассивы, размер которых
// подходит для быстрой сортировки методом вставок, далее каждый подмассив
// сортируется методом вcтавки
// сортировка всего массива производится "по месту", т.е. без создания дополнительных
// массивов
//

// реализация стека в отдельном модуле (файл stack.rs или stack/mod.rs)
mod stack;
// используем структуру QsStack
use stack::QsStack;


const N: usize = 20; // размер списка (массива) для сортировки
const M: usize = 5;  // размер подмассива для сортировки методом вставок

fn main() {


    println!("Robert Sedgewick, Donald E. Knuth algorithms: quicksort");


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

    println!("source: {:?}", list);

    quicksort(0, N-1, &mut list);

    println!("sorted: {:?}", list);


    // исходный список элементов произвольной длины
    // let mut list: Vec<i32> = vec![5, 14, 2, 7, -1, -2, -5, 10, 4, -3, 7, 0, 12, 6, 15, 7, 11, 8, 3, 12, 1, 22, 33, 0x2F, -10];
    let mut list: Vec<i32> = vec![5, 14, 2, 7, -1, -2, -5, 10, 4, -3, 7, 0, 12, 6, 15, 7, 11, 8, 3, 12, 1, 22, 33, 0x2F, -10, 2, 1, -10, 3, 50];

    println!("\n\n{}\n\n", "*".repeat(30));

    println!("vec source: {:?}", list);

    quicksort(0, list.len()-1, &mut list);

    println!("vec sorted: {:?}", list);


    // исходный список элементов произвольной длины
    let mut list: Vec<i32> = vec![5, 14, 2, 7, -1, -2, -5, 10, 4, -3, 7, 0, 1, 9, 12, 6, 15, 7, 11, 8, 3, 12, 1, 22, 33, 0x2F, -7, 2, 1, -10, 3, 50];

    println!("\n\n{}\n\n", "*".repeat(30));

    println!("vec stack source: {:?}", list);

    quicksort_stack(0, list.len()-1, &mut list);

    println!("vec stack sorted: {:?}", list);


}


/// сортировка массива методом quicksort ("быстрая сортировка")
///
/// # Parameters
/// `l`    - левый индекс
/// `r`    - правый индекс
/// `list` - массив (срез) для сортировки
fn quicksort(l: usize, r: usize, list: &mut [i32]) {

    if l >= r { return; }

    #[cfg(debug_assertions)]
    {
        let qs_slice = &list[l..=r];
        println!("\n+++\nquicksort slice ({l}-{r}): {:?}", qs_slice);
    }

    // разделяем на подмассивы
    let s = split(l, r, list);

    #[cfg(debug_assertions)]
    {
        let center_elem = list[s];
        let left_slice  = &list[l..s];
        let right_slice = &list[s+1..=r];

        println!("---");
        println!("splited:");
        println!("index = {s}, list[s] = {center_elem}");
        println!("left  = {:?}", left_slice);
        println!("right = {:?}", right_slice);
        println!("{:?} {} {:?}", left_slice, center_elem, right_slice);
        println!("===");
    }

    let left_size  = s - l;
    let right_size = r - s;

    // сортировка левой части
    if left_size > 1 {

        let right_index = s - 1;
        let slice = &mut list[l..s];

        if left_size > M {

            #[cfg(debug_assertions)]
            println!("quicksort left side ({}-{}):\n{:?}", l, right_index, slice);

            quicksort(l, right_index, list);

        } else {

            #[cfg(debug_assertions)]
            println!("sort_by_inserts left size ({}-{}): {:?}", l, right_index, slice);

            sort_by_inserts(slice);

        }
    }

    // сортировка правой части
    if right_size > 1 {

        let left_index = s + 1;
        let slice = &mut list[left_index..=r];

        if right_size > M {

            #[cfg(debug_assertions)]
            println!("quicksort right side ({}-{}):\n{:?}", left_index, r, slice);

            quicksort(left_index, r, list);

        }  else {

            #[cfg(debug_assertions)]
            println!("sort_by_inserts right size ({}-{}): {:?}", left_index, r, slice);

            sort_by_inserts(slice);

        }
    }
}


/// сортировка массива методом quicksort ("быстрая сортировка")
/// вместо рекурсивного вызова используем стек
///
/// # Parameters
/// `l`    - левый индекс
/// `r`    - правый индекс
/// `list` - массив (срез) для сортировки
fn quicksort_stack(l: usize, r: usize, list: &mut [i32]) {

    if l >= r { return; }

    #[cfg(debug_assertions)]
    {
        let qs_slice = &list[l..=r];
        println!("quicksort with stack ({l}-{r}): {:?}", qs_slice);
    }

    let mut stack = QsStack::new((l, r));

    while stack.qs_exists() {

        let (l, r) = stack.qs_pop().unwrap();

        // делим список
        let s = split(l, r, list);

        #[cfg(debug_assertions)]
        {
            let center_elem = list[s];
            let left_slice  = &list[l..s];
            let right_slice = &list[s+1..=r];

            println!("---");
            println!("splited:");
            println!("index = {s}, list[s] = {center_elem}");
            println!("left  = {:?}", left_slice);
            println!("right = {:?}", right_slice);
            println!("{:?} {} {:?}", left_slice, center_elem, right_slice);
            println!("===");
        }

        let left_size  = s - l;
        let right_size = r - s;

        if left_size > 1 {
            if left_size > M {
                stack.qs_push((l, s - 1));
            } else {
                stack.ins_push((l, s - 1));
            }
        }

        if right_size > 1 {
            if right_size > M {
                stack.qs_push((s + 1, r));
            } else {
                stack.ins_push((s + 1, r));
            }
        }
    }

    // сортировка кооротких подмассивов методом вставки
    while stack.ins_exists() {
        let (l, r) = stack.ins_pop().unwrap();
        let slice = &mut list[l..=r];
        sort_by_inserts(slice);
    }
}


/// "разделение" массива на подмассивы:
/// в результате возвращается индекс (index) в массиве, такой, что
/// элементы list[l..index] <= list[index] <= list[index+1..=r]
///
/// # Parameters
///
/// * `l` — левая (меньшая) граница исходного массива
/// * `r` — правая (большая) граница исходного массива
/// * `list` — изменяемый массив, который разделяется
///
/// # Returns
///
/// Индекс элемент в массиве, который делит массив на левую и правую части
///
fn split(l: usize, r: usize, list: &mut [i32]) -> usize {

    #[cfg(debug_assertions)]
    {
        let n: usize = list.len();

        debug_assert!(n > 1, "split: nothing to split");

        debug_assert!(r > l, "split: right must be greater than left");

    }

    let mut i = l;
    let mut j = r + 1;

    let k = list[l];

    while i < j {

        // гарантированный сдвиг индексов
        // !!! важно: этот код выполняется и после обмена соседних элементов [i] и [j]
        // при этом более важен j -= 1 , т.к. после этого он будет указывать
        // на элемент, который подлежит обмену с "центральным" элементом после
        // выхода из цикла while i < j
        i += 1;
        j -= 1;

        while i < r && k > list[i] { i += 1; }

        while j > l && k < list[j] { j -= 1; }

        // обмен элементов из левой и правой частей
        if i < j {

            // обмен элементов
            if list[i] != list[j] {
                (list[i], list[j]) = (list[j], list[i]);
            }
        }
    }

    // обмен левого элемента и "центрального", который должен находится между разделёнными массивами
    if l != j {
        // установим "центральный" элемент между массивами "меньше" и "больше"
        (list[l], list[j]) = (list[j], list[l]);
    }

    j
}


// ===
// сортировка методом вставок
// пример из ппердыдущей реализации
fn sort_by_inserts(list: &mut [i32]) {

    let n: usize = list.len();

    debug_assert!(n > 1, "sort_by_inserts: nothing to sort");

    #[cfg(debug_assertions)]
    println!("sort_by_inserts source: {:?}", list);

    let mut j: usize = 1;

    while j < n {

        let t: i32 = list[j];
        let mut i = j;

        while i > 0 {

            let check = list[i-1];

            if check < t { break; }
            list[i] = check;
            i -= 1;

        }

        // в оригинальном агоритме Кнута значение может быть
        // записано в ту же самую позицию
        // видимо потому, что лишняя проверка индексов дополнительно занимает
        // память программы, и ещё и для выполнения требует время
        // но использую своё дополнение - с проверкой индексов, чтобы не перезаписывать
        // одно и то же значение
        if i < j { list[i] = t; }

        j += 1;
    }

    #[cfg(debug_assertions)]
    println!("sort_by_inserts sorted: {:?}", list);

}


// ===
// модуль тестов
//
#[cfg(test)]
mod split_tests {
    use super::*;

    #[test]
    fn split_tests() {

        let mut list = [5, 30, 20, 1, 2];
        let j = split(0, list.len() - 1, &mut list);
            assert_eq!(j, 2);
            assert_eq!(list[j], 5);
            assert_eq!(list[0..j], [1, 2]);
            assert_eq!(list[j+1..list.len()], [20, 30]);

        let mut list = [5, 30, 20, 1, 2, 50];
        let j = split(0, list.len() - 1, &mut list);
            assert_eq!(j, 2);
            assert_eq!(list[j], 5);
            assert_eq!(list[0..j], [1, 2]);
            assert_eq!(list[j+1..list.len()], [20, 30, 50]);

        let mut list = [5, 30, 50, 20, 3, 2, 1];
        let j = split(0, list.len() - 1, &mut list);
            assert_eq!(j, 3);
            assert_eq!(list[j], 5);
            assert_eq!(list[0..j], [3, 1, 2]);
            assert_eq!(list[j+1..list.len()], [20, 50, 30]);

        let mut list = [100, 30, 50, 20, 3, 2, -1, 0, 10];
        let j = split(0, list.len() - 1, &mut list);
            assert_eq!(j, 8);
            assert_eq!(list[j], 100);
            assert_eq!(list[0..j], [10, 30, 50, 20, 3, 2, -1, 0]);
            assert_eq!(list[j+1..list.len()], []);

        let mut list = [-100, 30, 50, 20, 3, 2, -1, 0, 10];
        let j = split(0, list.len() - 1, &mut list);
            assert_eq!(j, 0);
            assert_eq!(list[j], -100);
            assert_eq!(list[0..j], []);
            assert_eq!(list[j+1..list.len()], [30, 50, 20, 3, 2, -1, 0, 10]);

    }
}

#[cfg(test)]
mod quicksort_tests {
    use super::*;

    #[test]
    fn quicksort_small_tests() {

        let mut list = [1];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1]);

        let mut list = [1, 2];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2]);

        let mut list = [2, 1];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2]);

    }

    #[test]
    fn quicksort_tests() {

        let mut list = [-100, 1, 2, 3, 4];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, 1, 2, 3, 4]);

        let mut list = [-100, 1, 2, 3, 4];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, 1, 2, 3, 4]);

        let mut list = [5, 30, 20, 1, 2];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 5, 20, 30]);

        let mut list = [5, 30, 20, 1, 2, 6];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 5, 6, 20, 30]);

        let mut list = [0, 4, 3, 2, 1, -1, -100];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, -1, 0, 1, 2, 3, 4]);

        let mut list = [0, 1, 3, 2, 4, -1, 100];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 3, 4, 100]);

        let mut list = [100, 1, 2, 3, 4, 0, -1];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 3, 4, 100]);

        let mut list = [0, 1, 2, 100, 3, -1, 4];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 3, 4, 100]);

        let mut list = [5, 1, 2, 100, -1, 4, 0];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 4, 5, 100]);

    }

    #[test]
    fn quicksort_test_several_eq() {

        let mut list = [5, 1, 2, 100, 2, 2, 0];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [0, 1, 2, 2, 2, 5, 100]);

        let mut list = [5, 1, 2, 100, 2, 2, 0, -100];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, 0, 1, 2, 2, 2, 5, 100]);

    }

    #[test]
    fn quicksort_test_all_eq() {

        let mut list = [1, 1, 1, 1, 1, 1, 1];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 1, 1, 1, 1, 1, 1]);

        let mut list = [3, 3, 3, 3, 3, 3, 3, 3];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [3, 3, 3, 3, 3, 3, 3, 3]);

    }

    #[test]
    fn quicksort_test_sorted() {

        let mut list = [1, 2, 3, 4, 5, 6];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6]);

        let mut list = [6, 5, 4, 3, 2, 1];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6]);

        let mut list = [1, 2, 3, 4, 5, 6, 7];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6, 7]);

        let mut list = [7, 6, 5, 4, 3, 2, 1];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6, 7]);

    }

    #[test]
    fn quicksort_stack_small_tests() {

        let mut list = [1];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1]);

        let mut list = [1, 2];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2]);

        let mut list = [2, 1];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2]);

    }

    #[test]
    fn quicksort_stack_tests() {

        let mut list = [-100, 1, 2, 3, 4];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, 1, 2, 3, 4]);

        let mut list = [5, 30, 20, 1, 2];
            quicksort(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 5, 20, 30]);

        let mut list = [-100, 1, 2, 3, 4, 100];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, 1, 2, 3, 4, 100]);

        let mut list = [0, 4, 3, 2, 1, -1, -100];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-100, -1, 0, 1, 2, 3, 4]);

        let mut list = [0, 1, 3, 2, 4, -1, 100];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 3, 4, 100]);

        let mut list = [100, 1, 2, 3, 4, 0, -1];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 3, 4, 100]);

        let mut list = [0, 1, 2, 100, 3, -1, 4];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 3, 4, 100]);

        let mut list = [5, 1, 2, 100, -1, 4, 0];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [-1, 0, 1, 2, 4, 5, 100]);

    }

    #[test]
    fn quicksort_stack_test_several_eq() {

        let mut list = [5, 1, 2, 100, 2, 2, 0];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [0, 1, 2, 2, 2, 5, 100]);
    }

    #[test]
    fn quicksort_stack_test_all_eq() {

        let mut list = [1, 1, 1, 1, 1, 1, 1];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 1, 1, 1, 1, 1, 1]);

        let mut list = [3, 3, 3, 3, 3, 3];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [3, 3, 3, 3, 3, 3]);

    }

    #[test]
    fn quicksort_stack_test_sorted() {

        let mut list = [1, 2, 3, 4, 5, 6];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6]);

        let mut list = [6, 5, 4, 3, 2, 1];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6]);

        let mut list = [1, 2, 3, 4, 5, 6, 7];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6, 7]);

        let mut list = [7, 6, 5, 4, 3, 2, 1];
            quicksort_stack(0, list.len()-1, &mut list);
            assert_eq!(list, [1, 2, 3, 4, 5, 6, 7]);

    }
}

Для пробы реализовал стек в отдельной структуре и в отдельном модуле:

//
// @author ESV Corp. (C) 17.09.2026
//
// модуль реализации стека
//

pub struct QsStack {

    qs_size: usize,
    qs_stack: Vec<(usize, usize)>,

    ins_size: usize,
    ins_stack: Vec<(usize, usize)>,

}


impl QsStack {

    pub fn new(init: (usize, usize)) -> Self {
        Self {
            qs_size: 1,
            ins_size: 0,
            qs_stack: vec![init],
            ins_stack: Vec::new(),
        }
    }

    pub fn qs_push(&mut self, el: (usize, usize)) {
        self.qs_stack.push(el);
        self.qs_size += 1;
    }

    pub fn qs_pop(&mut self) -> Option<(usize, usize)> {
        if self.qs_exists() {
            self.qs_size -= 1;
            self.qs_stack.pop()
        } else {
            None
        }
    }

    pub fn qs_exists(&self) -> bool { self.qs_size > 0 }


    // блоки для сортировки методом вставок
    pub fn ins_push(&mut self, el: (usize, usize)) {
        self.ins_stack.push(el);
        self.ins_size += 1;
    }

    pub fn ins_pop(&mut self) -> Option<(usize, usize)> {
        if self.ins_exists() {
            self.ins_size -= 1;
            self.ins_stack.pop()
        } else {
            None
        }
    }

    pub fn ins_exists(&self) -> bool { self.ins_size > 0 }

}