7 unstable releases (3 breaking)
0.4.0 | Apr 18, 2024 |
---|---|
0.3.3 | Apr 8, 2024 |
0.2.0 | Apr 7, 2024 |
0.1.0 | Apr 6, 2024 |
#526 in Algorithms
338 downloads per month
21KB
441 lines
cursorsort
CursorSort is an implementation of the QuickSort algorithm using only cursors, to both partition and select the accurately placed pivot element. It does so by choosing the initial and last elements of the array as its cursors and then in a loop swapping elements that are either greater than the two indexes the cursors point to and the first cursor is less than the second or vice versa.
This sorting algorithm works on any type implementing the PartialOrd
trait
and the test cases cover array
s and Vec
tors of integers, letters and words,
as well as String
s.
Depending on the descending
argument passed to the function it will either
sort in ascending or descending order.
Overview
The algorithm essentially works as follows:
-
Choose the first and last elements of the array as cursors
-
While the first cursor is not equal to the second loop over steps 3-5
-
If the element at the first cursor is greater than the element at the second cursor and the first cursor is smaller than the second or vice versa a. The first element is smaller but the first cursor is larger
-
Assuming step 3 is true Swap the elements at the first and last cursor and the cursors themselves, otherwise do nothing.
-
If the first counter is less than the second counter increment it, otherwise decrement it.
-
This correctly places a pivot element and from the cursors (now equal) we recursively call the function on the left and right halves of the array.
Installation
To use this algorithm in your project, run the following command:
cargo add cursorsort
Usage
Any type implementing the PartialOrd
traits can be used, with the cursorsort
function for arrays/slices and vectors. It operates on them in place and
requires only the core::cmp::PartialOrd
as a dependency, making it no_std
compatible.
If something can be converted into a Vec
it will be able to be sorted
(provided the trait requirements are met).
use cursorsort::cursorsort;
fn main() {
// For arrays:
let mut array = [5, 3, 2, 4, 1];
cursorsort(&mut array, false);
println!("Sorted array: {:?}", array); // [ 1, 2, 3, 4, 5 ]
// For Vecs:
let mut vector = vec![1, 2, 3, 4, 5];
cursorsort(&mut vector, true);
println!("Sorted vector: {:?}", vector); // [ 5, 4, 3, 2, 1 ]
// For Strings:
// Convert a String to a Vec<u8>
let mut bytes = String::from("hello world").into_bytes();
// Sort the vector in place
cursorsort(&mut bytes, false);
// Convert the sorted Vec<u8> back into a String
let sorted_string = String::from_utf8(bytes).expect("Invalid UTF-8");
println!("Sorted string: {:?}", sorted_string); // " dehllloorw"
}