Quicksort – алгоритм сортировки по методу «разделяй и влавствуй». Рекурсивно, по частям разбираем массив чисел, выставляя числа в меньшем и большем порядке от выбранного опорного элемента, сам опорный элемент вставляем в отсечку между ними. После нескольких рекурсивных итераций получится отсортированный список. Временная сложность O(n2).
Схема:
- Начинаем с того что получаем снаружи список элементов, границы сортировки. На первом шаге границы сортировки будут от начала до конца.
- Проверяем что границы начала и конца не пересекаются, если это произошло, значит пора заканчивать
- Выбираем какой-то элемент из списка, называем его опорным
- Сдвигаем вправо в конец на последний индекс, чтобы не мешался
- Создаем счетчик *меньших чисел* пока равный нулю
- Проходим циклом по списку слева направо, до последнего индекса, где находится опорный элемент, не включительно
- Каждый элемент сравниваем с опорным
- Если он меньше опорного, то меняем его местами по индексу счетчика меньших чисел. Инкрементируем счетчик меньших чисел.
- Когда цикл дойдет до опорного элемента, останавливаемся, меняем местами опорный элемент с элементом по счетчику меньших чисел.
- Запускаем отдельно алгоритм для левой меньшей части списка, и отдельно для правой большей части списка.
- В итоге все рекурсивные итерации начнут останавливаться из-за проверки в пункте 2
- Получим отсортированный список
Quicksort был придуман ученым Чарльзом Энтони Ричардом Хоаром в МГУ, выучив русский язык, он занимался изучением компьютерного перевода, а также теории вероятностей в школе Колмогорова. В 1960 г. из-за политического кризиса, он покинул Советский Союз.
Пример реализации на Rust:
extern crate rand;
use rand::Rng;
fn swap(numbers: &mut [i64], from: usize, to: usize) {
let temp = numbers[from];
numbers[from] = numbers[to];
numbers[to] = temp;
}
fn quicksort(numbers: &mut [i64], left: usize, right: usize) {
if left >= right {
return
}
let length = right - left;
if length <= 1 {
return
}
let pivot_index = left + (length / 2);
let pivot = numbers[pivot_index];
let last_index = right - 1;
swap(numbers, pivot_index, last_index);
let mut less_insert_index = left;
for i in left..last_index {
if numbers[i] < pivot {
swap(numbers, i, less_insert_index);
less_insert_index += 1;
}
}
swap(numbers, last_index, less_insert_index);
quicksort(numbers, left, less_insert_index);
quicksort(numbers, less_insert_index + 1, right);
}
fn main() {
let mut numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let mut reference_numbers = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0];
let mut rng = rand::thread_rng();
for i in 0..numbers.len() {
numbers[i] = rng.gen_range(-10..10);
reference_numbers[i] = numbers[i];
}
reference_numbers.sort();
println!("Numbers {:?}", numbers);
let length = numbers.len();
quicksort(&mut numbers, 0, length);
println!("Numbers {:?}", numbers);
println!("Reference numbers {:?}", reference_numbers);
if numbers != reference_numbers {
println!("Validation failed");
std::process::exit(1);
}
else {
println!("Validation success!");
std::process::exit(0);
}
}
Если ничего непонятно, то предлагаю посмотреть видео Роба Эдвардса из университета Сан-Диего https://www.youtube.com/watch?v=ZHVk2blR45Q в нем наиболее просто, по шагам, показывается суть и реализация алгоритма.
Ссылки
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/quickSort
Источники
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=ywWBy6J5gz8
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://ru.wikipedia.org/wiki/Быстрая_сортировка
https://www.youtube.com/watch?v=Hoixgm4-P4M
https://www.youtube.com/watch?v=XE4VP_8Y0BU
https://www.youtube.com/watch?v=MZaf_9IZCrc
https://www.youtube.com/watch?v=ZHVk2blR45Q
http://rosettacode.org/wiki/Sorting_algorithms/Quicksort
https://www.youtube.com/watch?v=4s-aG6yGGLU
https://www.youtube.com/watch?v=dQw4w9WgXcQ
https://www.youtube.com/watch?v=maibrCbZWKw
https://www.geeksforgeeks.org/quick-sort/
https://www.youtube.com/watch?v=uXBnyYuwPe8