Quicksort – Demens Deum

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(n²).

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

Links

References

Published by demensdeum