rust_sort/
quick_sort.rs

1use super::Sortable;
2
3/// Quick sort sorts unstable, in-place, in ascending order a mutable ref slice of type T: Sortable
4///
5/// Quicksort is a divide and conquer sort. It first divides a large array into two smaller sub-arrays:
6/// the low elements and the high elements. Quicksort can then recursively sort the sub-arrays.
7///
8/// The steps are:
9///
10/// 1. Pick an element, called a pivot, from the array.
11///
12/// 2. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot,
13/// while all elements with values greater than the pivot come after it (equal values can go either way).
14/// After this partitioning, the pivot is in its final position. This is called the partition operation.
15///
16/// 3. Recursively apply the above steps to the sub-array of elements with smaller values and separately
17/// to the sub-array of elements with greater values.
18///
19/// # Examples
20///
21/// ```
22/// use rust_sort::quick_sort::sort;
23///
24/// let mut arr = [3, 2, 1, 7, 9, 4, 1, 2];
25/// sort(&mut arr);
26/// assert_eq!(arr, [1, 1, 2, 2, 3, 4, 7, 9]);
27///
28/// ```
29pub fn sort<T: Sortable>(list: &mut [T]) {
30    quick_sort(list);
31}
32
33pub fn quick_sort<T:Sortable>(list: &mut [T]) {
34    let len = list.len();
35    if len <= 1 {
36        return
37    }
38    let pivot = len-1;
39    let mut left = 0;
40    let mut right = pivot -1;
41
42    while left != right {
43        if list[left] > list[pivot] {
44            list.swap(left, right);
45            right -=1;
46        } else {
47            left += 1;
48        }
49    }
50    let new_pivot_pos = if list[left] > list[pivot] {
51        list.swap(left, pivot);
52        left
53    } else {
54        list.swap(left+1, pivot);
55        left + 1
56    };
57
58    quick_sort(&mut list[..new_pivot_pos]);
59    quick_sort(&mut list[new_pivot_pos+1..]);
60}
rust_sort/quick_sort.rs

rust_sort/
quick_sort.rs
