Expected O(n) algorithm to find the k largest numbers and median of a Java array
Switch branches/tags
Nothing to show
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.settings
doc
evaluation/com/pwnetics/math
src/com/pwnetics
test/com/pwnetics
.classpath
.gitignore
.project
LICENSE.txt
README.md

README.md

Overview

This code implements two algorithms: QuickSelect and QuickMedian.
QuickSelect can be used to find the k-th largest value in a sequence
and the k largest values in expected O(n) time. QuickMedian can be
used to find the median value of a sequence in expected O(n) time.
However, both algorithms are worst-case O(n^2) time.

The examples package contains short examples and my blog
has a writeup of an empirical runtime evaluation.

This implementation only works on double arrays. Let me know if
you're interested in seeing versions for other array types and
collections, and that will get done a bit sooner.

Brian Romanowski
romanows@gmail.com

Empirical Runtime Evaluation

There are plots of runtime evaluation data and an analysis writeup on
my blog
. The image below shows a number of things, but the gist is
that finding the median using QuickMedian is indeed better than
finding the median using a sort-based method, all other things being
equal.

Click on the image to view a larger, annotated version.

Thumbnail image linking to the full image that analyzes QuickMedian vs. SortMedian runtimes.  See analysis.txt for a writeup of the evaluation data.

Bugs

Please file bug reports and bug fixes in the GitHub issue tracker.
Feel free to shoot the author an email if you find this software
useful, it would make his day.

LICENSE

This software is released under the Simplified BSD License, see
LICENSE.TXT.