Skip to content

Instantly share code, notes, and snippets.

@Abraxos
Created July 5, 2016 05:33
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Abraxos/6bcddcefd5a6b6eb2aced6af13a9f52a to your computer and use it in GitHub Desktop.
Save Abraxos/6bcddcefd5a6b6eb2aced6af13a9f52a to your computer and use it in GitHub Desktop.
QuickSort implementation in Rust
fn quicksort(array: &mut Vec<i32>) {
let mut stack = vec![];
stack.push((0, array.len()));
while let Some(top) = stack.pop() {
let (start, end) = top;
match partition(array, start, end) {
None => continue,
Some(pivot_idx) => {
if pivot_idx > start {
// println!("{:?}", (start, pivot_idx));
stack.push((start, pivot_idx));
}
if end > (pivot_idx + 1) {
// println!("{:?}", (pivot_idx + 1, end));
stack.push((pivot_idx + 1, end));
}
// println!("{:?}", stack);
},
}
}
}
fn swap(array: &mut Vec<i32>, a: usize, b: usize) {
let tmp = array[a];
array[a] = array[b];
array[b] = tmp;
}
fn scan_for_next_lt(array: &mut Vec<i32>, start: usize, pivot_idx: usize) -> usize {
let mut i = start;
let pivot = array[pivot_idx];
while i > pivot_idx {
if array[i] < pivot {
return i
}
i -= 1;
}
i
}
fn scan_for_next_geq(array: &mut Vec<i32>, start: usize, pivot_idx: usize) -> usize {
let mut i = start;
let pivot = array[pivot_idx];
while i < pivot_idx {
if array[i] >= pivot {
return i
}
i += 1;
}
i
}
fn partition(array: &mut Vec<i32>, start: usize, end: usize) -> Option<usize> {
if end - start <= 1 {
// println!("Partitioned: {:?}", &array[start..end]);
None
} else if end - start == 2 {
if array[start] > array[end-1] {
swap(array, start, end-1);
}
// println!("Partitioned: {:?}", &array[start..end]);
None
} else {
let pivot_idx = end - 1;
let mut lt_counter = 0;
let pivot = array[pivot_idx];
for i in start..pivot_idx {
if array[i] < pivot {
lt_counter += 1;
}
}
let new_pivot_idx = start + lt_counter;
swap(array, pivot_idx, new_pivot_idx);
let mut top = end-1;
let mut bottom = start;
while bottom < new_pivot_idx && top > new_pivot_idx {
top = scan_for_next_lt(array, top, new_pivot_idx);
bottom = scan_for_next_geq(array, bottom, new_pivot_idx);
swap(array, top, bottom);
}
// println!("Partitioned: {:?}", &array[start..end]);
return Some(new_pivot_idx)
}
}
fn test_partition() {
let mut array = vec![3,7,8,5,2,1,9,5,4];
let len = array.len();
assert_eq!(partition(&mut array, 0, len), Some(3));
assert_eq!(partition(&mut array, 0, len-1), Some(4));
assert_eq!(partition(&mut array, 0, len-2), Some(6));
assert_eq!(partition(&mut array, 0, len-3), Some(5));
assert_eq!(partition(&mut array, 0, len-4), Some(4));
assert_eq!(partition(&mut array, 0, len-5), Some(3));
assert_eq!(partition(&mut array, 0, len-6), Some(1));
assert_eq!(partition(&mut array, 0, len-7), None);
assert_eq!(partition(&mut array, 0, len-8), None);
assert_eq!(partition(&mut array, 0, len-9), None);
let mut array = vec![3,1,2,4,5,8,9,5,7];
let len = array.len();
assert_eq!(partition(&mut array, 0, 3), Some(1));
assert_eq!(partition(&mut array, 4, len), Some(6));
let mut array = vec![7, 9, 5, 8];
let len = array.len();
assert_eq!(partition(&mut array, 0, len), Some(2));
println!("All partition tests passed!");
}
fn test_quicksort() {
let mut to_sort = vec![3,7,8,5,2,1,9,5,4];
quicksort(&mut to_sort);
assert_eq!(to_sort, [1, 2, 3, 4, 5, 5, 7, 8, 9]);
let mut to_sort = vec![];
quicksort(&mut to_sort);
assert_eq!(to_sort, vec![]);
let mut to_sort = vec![1,2];
quicksort(&mut to_sort);
assert_eq!(to_sort, vec![1,2]);
let mut to_sort = vec![2,1];
quicksort(&mut to_sort);
assert_eq!(to_sort, vec![1,2]);
let mut to_sort = vec![1];
quicksort(&mut to_sort);
assert_eq!(to_sort, vec![1]);
let mut to_sort = vec![6,5,3,1,8,7,2,4];
quicksort(&mut to_sort);
assert_eq!(to_sort, vec![1,2,3,4,5,6,7,8]);
let mut to_sort = vec![6,5,3,1,8,7,2,4,9,10,11,12,13];
quicksort(&mut to_sort);
assert_eq!(to_sort, vec![1,2,3,4,5,6,7,8,9,10,11,12,13]);
println!("All sorting tests passed!");
}
fn main() {
test_partition();
test_quicksort();
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment