## PackageDescription: SYSEXT-Median

SYSEXT - MedianLast 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)