Quicksort

[jjcnn]

A non-randomized quicksort algorithm.

The algorithm could probably be made more robust. Currently, the assumption is that the n input elements are located in the first n memory addresses, which won't be true in general if called from another program.

I have not looked into how to pick the pivot element at random.

[jjcnn]

* Did you test it in Rust with some more inputs?

I tested it on the command line with various combinations of input. I haven't done any performance testing on it, though - I don't think I went above 16 elements.

* Can you add it to the std lib if @bobbinth agrees?

Sure, though we should change it to be more flexible if it is to be added to the standard library. For one thing, it should be able to sort an array (i.e., a sequential block of memory) starting from any address, not just from address 0.

I'm also not sure we can add randomization when choosing the pivot element, so the algorithm runs in O(n^2) time. This means that we could just as well just use bubblesort, which is a simpler algorithm.

[sonarcloud[bot]]

Kudos, SonarCloud Quality Gate passed!   

0 Bugs
0 Vulnerabilities
0 Security Hotspots
0 Code Smells

No Coverage information
No Duplication information