Search code examples
javaalgorithmmedian

Java implementation of quickselect-median

There is implementation at

http://www.java-tips.org/java-se-tips/java.lang/quickselect-implementation-with-median-of-three-partitioning-and-cutoff.html

Using Scala syntax

val arr = Array[Comparable[_]](1, 7, 10, 11, 3, 6, 0, 2, 9, 4, 8, 5)
quickSelect(arr, 6)
println(s"${arr.mkString(" ")} | ${arr(6)}")

And output: 1 4 2 0 3 5 11 10 9 7 8 6 | 11 . So, median is 11 instead of 6. Does anybody know what is the bug in implementation?

Solution

  • Link you provided says that

    * Quick selection algorithm.
* Places the kth smallest item in a[k-1].

    6th element in zero-based array is a[5]