use std::cmp::Ordering;
use rand::prelude::*;
use super::{insertion_sort_x, is_sorted};
pub struct QuickSort;
fn partition<T: Clone + Ord>(arr: &mut [T], lo: usize, hi: usize) -> usize {
let mut i = lo;
let mut j = hi + 1;
let v = arr[i].clone();
loop {
loop {
i += 1;
if arr[i] >= v || i == hi {
break;
}
}
loop {
j -= 1;
if v >= arr[j] || j == lo {
break;
}
}
if i >= j {
break;
}
arr.swap(i, j);
}
arr.swap(lo, j);
j
}
fn sort<T: Clone + Ord>(arr: &mut [T], lo: usize, hi: usize) {
if hi <= lo {
return;
}
let j = partition(arr, lo, hi);
sort(arr, lo, j.saturating_sub(1));
sort(arr, j + 1, hi);
debug_assert!(is_sorted(&arr[lo..=hi]));
}
fn three_way_sort<T: Clone + Ord>(arr: &mut [T], lo: usize, hi: usize) {
if hi <= lo {
return;
}
let v = arr[lo].clone();
let mut lt = lo;
let mut gt = hi;
let mut i = lo + 1;
while i <= gt {
match arr[i].cmp(&v) {
Ordering::Less => {
arr.swap(lt, i);
lt += 1;
i += 1;
}
Ordering::Greater => {
arr.swap(i, gt);
gt -= 1;
}
Ordering::Equal => {
i += 1;
}
}
}
three_way_sort(arr, lo, lt.saturating_sub(1));
three_way_sort(arr, gt + 1, hi);
debug_assert!(is_sorted(&arr[lo..=hi]));
}
fn median3<T: Ord>(arr: &mut [T], i: usize, j: usize, k: usize) -> usize {
if arr[i] < arr[j] {
if arr[j] < arr[k] {
j
} else if arr[i] < arr[k] {
k
} else {
i
}
} else {
if arr[k] < arr[j] {
j
} else if arr[k] < arr[i] {
k
} else {
i
}
}
}
const INSERTION_SORT_CUTOFF: u8 = 8;
const MEDIAN_OF_3_CUTOFF: u8 = 40;
fn optimized_sort<T: Clone + Ord>(arr: &mut [T], lo: usize, hi: usize) {
let n = hi + 1 - lo;
if n <= INSERTION_SORT_CUTOFF as usize {
insertion_sort_x(arr);
return;
}
else if n <= MEDIAN_OF_3_CUTOFF as usize {
let m = median3(arr, lo, lo + n / 2, hi);
arr.swap(m, lo);
}
else {
let eps = n / 8;
let mid = lo + n / 2;
let m1 = median3(arr, lo, lo + eps, lo + 2 * eps);
let m2 = median3(arr, mid - eps, mid, mid + eps);
let m3 = median3(arr, hi - 2 * eps, hi - eps, hi);
let ninther = median3(arr, m1, m2, m3);
arr.swap(ninther, lo);
}
let (mut i, mut j) = (lo, hi + 1);
let (mut p, mut q) = (lo, hi + 1);
let v = arr[lo].clone();
loop {
loop {
i += 1;
if arr[i] >= v || i == hi {
break;
}
}
loop {
j -= 1;
if v >= arr[j] || j == lo {
break;
}
}
if i == j && arr[i] == v {
p += 1;
arr.swap(p, i);
}
if i >= j {
break;
}
arr.swap(i, j);
if arr[i] == v {
p += 1;
arr.swap(p, i);
}
if arr[j] == v {
q -= 1;
arr.swap(q, j);
}
}
i = j + 1;
for k in lo..=p {
arr.swap(k, j);
j = j.saturating_sub(1)
}
for k in (q..=hi).rev() {
arr.swap(k, i);
i += 1;
}
optimized_sort(arr, lo, j);
optimized_sort(arr, i, hi);
}
impl QuickSort {
pub fn sort<T: Clone + Ord>(arr: &mut [T]) {
let mut rand = rand::rng();
arr.shuffle(&mut rand);
sort(arr, 0, arr.len() - 1);
debug_assert!(is_sorted(arr))
}
pub fn three_way_sort<T: Clone + Ord>(arr: &mut [T]) {
let mut rand = rand::rng();
arr.shuffle(&mut rand);
three_way_sort(arr, 0, arr.len() - 1);
debug_assert!(is_sorted(arr));
}
pub fn optimized<T: Clone + Ord>(arr: &mut [T]) {
optimized_sort(arr, 0, arr.len() - 1);
debug_assert!(is_sorted(arr));
}
}
#[cfg(test)]
mod tests {
use super::*;
fn quick_sort<T: Clone + Ord>(arr: &mut [T]) {
QuickSort::sort(arr)
}
fn three_way_quick_sort<T: Clone + Ord>(arr: &mut [T]) {
QuickSort::three_way_sort(arr)
}
fn optimized_quick_sort<T: Clone + Ord>(arr: &mut [T]) {
QuickSort::optimized(arr);
}
test_sort!(quick_sort, three_way_quick_sort, optimized_quick_sort);
}