ITMO University
“Programming Technologies” Department

Development of the order statistic and quantiles search algorithm visualizer based on Vizi technology

© 2004 A.A. Vladykin

Saint-Petersburg State University of Information Technologies, Mechanics and Optics

Project documentation (in Russian)
Source code
Visualizer (online)

Annotation

The terms order statistic and quantile are related to the so called selection problem. It can be reduced to the sorting problem and solved for the time of O(nlog₂n) at best. However there exists another solution proposed by C. Hoare. It has the average time complexity of O(n), and thus is widely used in practice.

Present work contains the implementation of the last mentioned quick algorithm. On its basis the mechanism of finding k-th quantiles is illustrated. The implementation uses the Vizi technology and represents a Java-applet, which can demonstrate the algorithm step-by-step. This technology uses an automata-based approach to visualizer development.

The documentation includes algorithm details, possible modifications, and source codes of the visualizer.