Get median of array

Question

I have an array that looks like this:

let arr = [1,2,3,4,5,6,7,8,9]

I know you can get min and max by:

let min = arr.min()
let max = arr.max()

But how do you get the median?

Petition

what if your array is [1,2,3,4,5,6,7,8] ? – Bouse

forums.swift.org/t/median/52279 – Bumgarner

Answer 1

To get the median you can use the following:

let median = arr.sorted(by: <)[arr.count / 2]

In your case it will return 5.

As @Nirav pointed out [1,2,3,4,5,6,7,8] will return 5 but should return 4.5.

Use this instead:

func calculateMedian(array: [Int]) -> Float {
    let sorted = array.sorted()
    if sorted.count % 2 == 0 {
        return Float((sorted[(sorted.count / 2)] + sorted[(sorted.count / 2) - 1])) / 2
    } else {
        return Float(sorted[(sorted.count - 1) / 2])
    }
}

Usage:

let array = [1,2,3,4,5,6,7,8]
let m2 = calculateMedian(array: array) // 4.5

Magic

Using sorted causes the algorithm to take O(n log n) time. If performance is important, opt for an algorithm that completes in O(n) time. – Shupe

Answer 2

The median is defined as the number in the middle of the sequence. If there is not one middle number, then it's the average of the two middle numbers.

extension Array where Element == Int {
    func median() -> Double {
        let sortedArray = sorted()
        if count % 2 != 0 {
            return Double(sortedArray[count / 2])
        } else {
            return Double(sortedArray[count / 2] + sortedArray[count / 2 - 1]) / 2.0
        }
    }
}

Ferine

Answer 3

Note that if the array is empty, the median is undefined. So a safe median function returns an optional, just like the min() and max() built-in methods do.

extension Array where Element == Int {
    func median() -> Double? {
        guard count > 0  else { return nil }

        let sortedArray = self.sorted()
        if count % 2 != 0 {
            return Double(sortedArray[count/2])
        } else {
            return Double(sortedArray[count/2] + sortedArray[count/2 - 1]) / 2.0
        }
    }
}

With that defined, you can write:

if let median = arr.median() {
    // do something
}

Armindaarming

Answer 4

If someone (like me) likes two*-liners:

let sorted = arr.sorted(by: <)
let median = Double(sorted[arr.count/2] + sorted.reversed()[arr.count/2])/2.0

Merwyn

Answer 5

Algorithms that use sorted take O(n log n) time. That's typically not a problem for 9 numbers, but if your array is large, use an algorithm that completes in O(n) time. An example is this k-th largest element algorithm. It recursively partitions the array, but doesn’t have to go through all the work to sort it, so it’s much faster.

Shupe