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 and Copy traits - the test cases cover arrays of integers, letters and words.

Overview

The algorithm essentially works as follows:

1. Choose the first and last elements of the array as cursors

2. While the first cursor is not equal to the second loop over steps 3-5

3. 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

4. Assuming step 3 is true Swap the elements at the first and last cursor and the cursors themselves, otherwise do nothing.

5. If the first counter is less than the second counter increment it, otherwise decrement it.

6. 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 and Copy traits can be used, with either the cursorsort or cursorsort_vec functions for arrays/slices and std::vec::Vec respectively. If something can be converted into a Vec it will be able to be sorted (provided the trait requirements are met).

use cursorsort::*;

fn main() {
    // For arrays:

    let mut array = [5, 3, 2, 4, 1];
    cursorsort(&mut array);
    println!("Sorted array: {:?}", array); // [ 1, 2, 3, 4, 5 ]

    // For Vecs:

    let mut vector = vec![5, 3, 2, 4, 1];
    cursorsort_vec(&mut vector);
    println!("Sorted vector: {:?}", vector); // [ 1, 2, 3, 4, 5 ]

    // For Strings:

    // Convert a String to a Vec<u8>
    let mut bytes = String::from("hello world").into_bytes();
    // Sort the vector in place
    cursorsort_vec(&mut bytes);
    // 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"
}