You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 
Emberlynn McKinney 57150c979c initial commit 2 years ago
..
Makefile initial commit 2 years ago
README initial commit 2 years ago
compare.py initial commit 2 years ago
quicksort.cpp initial commit 2 years ago
quicksort.hpp initial commit 2 years ago
sentence initial commit 2 years ago
words initial commit 2 years ago

README

To pick pivot selection methods, I tested on a list of English word with
compare.py. The most promising were last, middle, and random.

For each, the input was:
"Algorithms are the backbone of computer science"

They all output:
"Aghilmorst aer eht abbcekno fo cemoprtu cceeins"

Baseline for Testbench
----------------------

I ran each 1000 times so that time would actually display something, which
incurs overhead from the shell:

> /usr/bin/time sh -c 'for x in `seq 1 1000`; do cat <sentence>/dev/null; done'
0.46user 0.18system 0:00.61elapsed 104%CPU (0avgtext+0avgdata 3456maxresident)k
0inputs+0outputs (0major+139191minor)pagefaults 0swaps

Last
----

Select the last location for the pivot: between the last to elements.

> /usr/bin/time sh -c 'for x in `seq 1 1000`; do ./last <sentence>/dev/null; done'
0.73user 0.19system 0:00.90elapsed 102%CPU (0avgtext+0avgdata 3472maxresident)k
0inputs+0outputs (0major+177228minor)pagefaults 0swaps

Middle
------

Put the pivot at floor((lo+hi)/2).

> /usr/bin/time sh -c 'for x in `seq 1 1000`; do ./middle <sentence>/dev/null; done'
0.75user 0.15system 0:00.89elapsed 102%CPU (0avgtext+0avgdata 3448maxresident)k
0inputs+0outputs (0major+178294minor)pagefaults 0swaps

Random
------

Select a random pivot each time.

> /usr/bin/time sh -c 'for x in `seq 1 1000`; do ./random <sentence>/dev/null; done'
0.75user 0.18system 0:00.90elapsed 102%CPU (0avgtext+0avgdata 3480maxresident)k
0inputs+0outputs (0major+180278minor)pagefaults 0swaps

Comparison
----------

Words are such small lists that as long as the pivot selection is simple, it
doesn't seem to matter that much for performance. I would use the middle, as it
is simple, and performed best on both this and the theoretical Python test.