Sort array elements based on their frequency

Question

I need to sort an array of elements based on their frequency, for example:

Input array: [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]
Expected output: [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]

I tried with the code below:

var set: NSCountedSet = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2]

var dictionary = [Int: Int]()
set.forEach { (item) in
    dictionary[item as! Int] = set.count(for: item)
}
dictionary.keys.sorted()
print(dictionary)

Description: As 1, 3, 4 occur only once, they are shown at the beginning, 2 occurs two times, 5 three times, 6 four times. And [1, 3, 4] are sorted among them.

Expected result: Time complexity should be O(n)

Answer 1

You can achieve the results in O(nlogn) time by first creating a Dictionary containing the number of occurrences for each element (O(n)), then calling sorted on the Array (Swift uses Introsort, which is O(nlogn)) and using the values from the previously created Dictionary for the sorting. The elements of your array need to be Comparable for sorting to work and Hashable to be able to store them in a Dictionary, which provides O(1) element lookup.

extension Array where Element: Comparable & Hashable {
    func sortByNumberOfOccurences() -> [Element] {
        let occurencesDict = self.reduce(into: [Element:Int](), { currentResult, element in
            currentResult[element, default: 0] += 1
        })
        return self.sorted(by: { current, next in occurencesDict[current]! < occurencesDict[next]!})
    }
}

[1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2].sortByNumberOfOccurences() // [1, 4, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]

The above solution preserves the order of elements that occur an equal number of times. If you actually want to sort such elements based on their compared values (which is what your sample output does), you can modify the closure in sorted like below:

return self.sorted(by: {occurencesDict[$0]! <= occurencesDict[$1]! && $0 < $1})

Or even shorter, comparing tuples for sorting:

return self.sorted(by: {(occurencesDict[$0]!,$0) < (occurencesDict[$1]!,$1)})

which produces the sample output you provided, [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]