The goal of this project is two-fold:
- provide a visualization and comparison of in-place sorting algorithms
- to demonstrate monadic software design
This project depends on Jane Street's Core library. The easiest way to get these is to install opam and then use opam to install core.
opam install core
opam install ocamlbuild
You can then compile the program by running "make".
To run the program, simply invoke "main.native" with the name of the sorts you want to run. For example:
./main.native insertion quicksort heapsort
Running main.native with no arguments will cause the available sorting algorithms to be listed. Running with -help will show additional options
This program also supports custom bash tab completion. Simply source the
complete.sh script that is generated by make: . complete.sh.
To implement a new sorting algorithm, you need to implement the Sort module
interface in sorts.mli. This requires a name and a sort function.
The sort function is parameterized by a SortMonad implementation. The sort
monad provides the monadic operations bind and return, and the Monad.Utils
functor provides additional operations for sequencing and loops.
In addition to the monadic operators, SortMonad provides three
functions for interacting with the array being sorted: length,
compare, and swap. There is no way to access the elements of
the array; this forces all sorts to be in-place compare-and-swap
algorithms.
The SortMonad also provides a printf function that can be used to report
what the sorting algorithm is doing. In the animation, the messages printed
by printf are displayed under the array being sorted.
For examples, see the existing sorts in the sorts/ folder.
To register the sort algorithm, edit main.ml and add new sorts to the sorts
list.