sorts

The goal of this project is two-fold:

1. provide a visualization and comparison of in-place sorting algorithms
2. to demonstrate monadic software design

Compiling

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

Running

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

Tab completion

This program also supports custom bash tab completion. Simply source the complete.sh script that is generated by make: . complete.sh.

Writing new sorting routines

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.