Quicksort is a divide-and-conquer sorting algorithm. Recursively, in parts, parse the array of numbers, setting the numbers in the smaller and larger order from the selected pivot element, insert the pivot element itself into the hot-point between them. After a few recursive iterations, you’ll end up with a sorted list. Time complexity O(n2).
Scheme:
- We start with the fact that we get a list of elements outside, sorting boundaries. In the first step, the sort boundaries will be from start to finish.
- Check that the boundaries of the beginning and end do not intersect, if this happens, then it’s time to finish
- Select some element from the list, call it pivot
- Shift to the right to the end to the last index, so as not to interfere
- Create a counter of *smaller numbers* while equal to zero
- Loop through the list from left to right, up to and including the last index where the anchor element is located
- Each element is compared to the pivot
- If it is less than the reference, then we swap it in places according to the index of the counter of smaller numbers. Increment the counter of smaller numbers.
- When the cycle reaches the anchor element, we stop, swap the anchor element with the element by the counter of smaller numbers.
- We run the algorithm separately for the left smaller part of the list, and separately for the right most part of the list.
- As a result, all recursive iterations will start to stop due to the check in paragraph 2
- Get sorted list
Quicksort was invented by the scientist Charles Antony Richard Hoare at Moscow State University, having learned Russian, he studied computer translation, as well as probability theory at the Kolmogorov school. In 1960, due to a political crisis, he left the Soviet Union.
An example implementation in 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);
}
}
If you don't understand anything, I suggest watching a video by Rob Edwards from the San Diego State University https://www.youtube.com/watch?v=ZHVk2blR45Q it most simply, step by step, shows the essence and implementation of the algorithm.
Links
https://gitlab.com/demensdeum/algorithms/-/tree/master/sortAlgorithms/quickSort
References
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