PackageDescription: SYSEXT-Median


SYSEXT - Median

Last published: April 29, 2020 by 'nice'

Defines 0 Classes
Extends 3 Classes

Implement the median of a collection.
This is using the median of medians algorithm (see https://en.wikipedia.org/wiki/Median_of_medians).
This algorithm generally has a cost in O(n) rather than O(n*log(n)) for full sort.
This is ported from Squeak http://www.squeaksource.com/MedianOfMedians.html.

The 5 main methods are for
- finding the nth highest element in a collection (self highestOfRank: n)
- finding the nth smallest element in a collection (self smallestOfRank: n)
- finding the n highest elemenst in a collection in decreasing order (self highest: n)
- finding the n smallest elements in a collection in increasing order (self smallest: n)
- finding the median (self median)

Note that we expect (self highestOfRank: self size) = (self smallestOfRank: 1).
And (self smallestOfRank: n) = (self sorted at: n).
For odd size, simply answer the central element: (self median) = (self highest: self size // 2).
For even size, use arithmetic mean: (self median) = ((self highest: self size // 2) + (self smallest: self size // 2) / 2).

Examples:
(3 to: 9) asSet median = 6.
(3 to: 10) asSet median = (13 / 2).
((3 to: 23 by: 5) asSet smallestOfRank: 2) = 8.
((3 to: 23 by: 5) asSet highestOfRank: 2) = 18.
((3 to: 23 by: 5) asSet smallest: 2) = #(3 8)
((3 to: 23 by: 5) asSet highest: 2) = #(23 18)