3

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)

Improve this question
2
  • 4
    I dont think you can get to O(n) in worst case. If your requirement is that unique items are being sorted as well, that already gives you O(n*log n). Commented Jan 16, 2019 at 10:47
  • 1
    Count sort is one choice to meet o(n) if the frequency is small Commented Jan 17, 2019 at 0:16

8 Answers 8

Reset to default
9

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]

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

I was about to post this let array = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] let freq = array.reduce(into: [:]) { $0[$1, default: 0] += 1 } let sortedArray = array.sorted() { freq[$0]! < freq[$1]! } sortedArray
It cannot be done in O(n). You need to sort this array first, then use the method mentioned above.
@RakeshaShastri no, you don't need to sort the array first, that's done in the sorted call. However, you're right, the overall time complexity of my algorithm is O(nlogn), updated my answer to reflect that
sorted(by:) is not O(n).
@LeoDabus I was thinking about doing that for the second solution as well, but used < instead of <=, which didn't work, so came up with a longer solution, but updated my answer with your idea if you don't mind :)
|
3

You can try

let dd = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] let res = dd.sorted { f, s in dd.filter { $0 == f }.count < dd.filter { $0 == s }.count } print(res) // [1, 4, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]
Improve this answer

3 Comments

I wonder if this is O(n). – Note also that the sort is not stable, there is no guarantee that the order of numbers which occur equally often is preserved.
@MartinR i don't think such problem be solved with in O(n) , sure there may be other less extensive answer also
Thanks for the answer @Sh_Khan, but expected output should be [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]
2

There is no way to sort with O(n) time complexity. Look at the worst case complexity for popular algorithms at Wikipedia.

The better worst-case time complexity is O(nlogn). Here is how we can solve it with O(nlogn) time complexity:

 let array = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] extension Array where Element: Comparable & Hashable { func countableSorted() -> [Element] { var counts = [Element: Int]() // O(n) for element in self { counts[element] = (counts[element] ?? 0) + 1 } // I think that standart method uses O(nlogn) time complexity. // O(nlogn) + O(n) approximately equal to O(nlogn). let sorted = counts.sorted { item1, item2 -> Bool in if item2.value > item1.value { return true } if item2.value == item1.value { return item2.key > item1.key } return false } var result = [Element]() // O(n) for item in sorted { let items = Array(repeating: item.key, count: item.value) result.append(contentsOf: items) } // Total time complexity for worst case scenario is O(nlogn) return result } } print(array.countableSorted()) // Output: [1, 3, 4, 2, 2, 5, 5, 5, 6, 6, 6, 6]
Improve this answer

Comments

1

You can try the below code, this worked properly.

var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] inputArray.sort() let freq = inputArray.sorted { f, s in inputArray.filter { $0 == f}.count < inputArray.filter { $0 == s}.count } print(freq)

Not sure about the time complexity.

Improve this answer

Comments

1

I want to add a solution in O(n)

Sorting takes O(nLogn) but this question can also be solved without using sorting by help of HashMap in Java because it contains the pairs sorted in accordance to the key.

import java.util.*; class Simple { public static void main(String[] arg) { int inputArray[] = {1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2}; Map<Integer,Integer> map = new HashMap<Integer,Integer>(); Map<Integer,List<Integer>> map2 = new HashMap<Integer,List<Integer>>(); for(int i: inputArray) { if(map.get(i) == null){ map.put(i, 1) ; } else{ int a = map.get(i); map.put(i,a+1); } } // using for-each loop for iteration over Map.entrySet() for (Map.Entry<Integer,Integer> entry : map.entrySet()) { if(map2.get(entry.getValue()) == null){ map2.put(entry.getValue(), new ArrayList<Integer>()) ; } map2.get(entry.getValue()).add(entry.getKey()); } for(Map.Entry<Integer,List<Integer>> entry : map2.entrySet()){ for(int j=0; j<entry.getValue().size(); j++){ for(int i=0; i<entry.getKey(); i++){ System.out.print(entry.getValue().get(j) + " "); } } } } }
  1. In First for loop I am iterating through array saving pair of (value,Occurrence) in map1(HashMap). This will take O(n) as HashMap put operation(insertion) takes O(1).
  2. In second for loop I am iterating map1 and inserting pair of (occurrence, list of numbers in the given array with that occurrence) in map2(HashMap2).
  3. Now in last for loop I am iterating through map2 and printing all the lists one by one it means I am printing each element of given array once i.e. I am iterating through the list of each key and printing each element of the list key number of times. So this would also take O(n).

more about HashMap Time Complexity : O(n)

Swift Version of above code

extension Array where Element: Comparable & Hashable { func sortByNumberOfOccurences() -> [Element] { let occurencesDict = self.reduce(into: [Element:Int](), { currentResult, element in currentResult[element, default: 0] += 1 }) let dict = occurencesDict.sorted(by: {$0.0 < $1.0}) var dictioanary = [Int:Array]() for (element,occurence) in dict { if dictioanary[occurence] == nil { dictioanary[occurence] = Array() } dictioanary[occurence]?.append(element) } var resultArray = Array() let finalDict = dictioanary.sorted(by: {$0.0 < $1.0}) for (frequency,allValuesOccuringWithThisFrequncy) in finalDict { for i in allValuesOccuringWithThisFrequncy { var j = 0 while(j < frequency) { resultArray.append(i) j = j + 1 } } } print(resultArray) return resultArray }

}

Time Complexity in Swift O(nLogn)

Improve this answer

2 Comments

Can you try the same approach in swift?
@Bappaditya Hi I tried to write the code in swift. I am adding the code. But as Dictionary in Swift does not maintain the order we need to apply the sort method in that and it makes complexity O(nLogn). But in java HashMap insert pairs in sorted way on the basis of key. I wish we had a similar type of collection in Swift too. Sad :( I think we need to write our own HashMap in Swift :P
1 
var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] var map:[Int: Int] = [:] for element in inputArray { let count = map[element] if count == nil { map[element] = 1 } else { map[element] = count! + 1 } } var keysArray = map.keys let sortedKeys = keysArray.sorted { (number1, number2) -> Bool in if map[number1]! == map[number2]! { return number1 < number2 } else { return map[number1]! < map[number2]! } } var finalArray: [Int] = [] for element in sortedKeys { for _ in 1...map[element]! { finalArray.append(element) } } print(finalArray)

Time Complexity: O(nlogn)

Improve this answer

1 Comment

@LeoDabus Thanks. Edited. Further, optional checking shall be done as well. But this solves the basic problem for us.
0

Try this solution. It worked for me like a charm :)

func numberOfOccurences(in array: [Int], of element: Int) -> Int { let object = NSCountedSet(array: array) return object.count(for: element) } var inputArray = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] var uniqueElements = Array(Set(inputArray)) var otherArray: [Int] = [] var duplicateElements = uniqueElements.filter { (element) -> Bool in return (inputArray.contains(element) && numberOfOccurences(in: inputArray, of: element) > 1) } uniqueElements = uniqueElements.filter({ !duplicateElements.contains($0) }).sorted() for item in duplicateElements { let occurences = numberOfOccurences(in: inputArray, of: item) for _ in 0...occurences - 1 { otherArray.append(item) } } otherArray = otherArray.sorted() duplicateElements.removeAll() let mergedArray = uniqueElements + otherArray print(mergedArray)
Improve this answer

2 Comments

If you are declaring a loop condition of x...y - 1, it makes more sense to do x..<y.
For the input [1, 1, 1, 2, 2, 3] your code produces the result [3, 1, 1, 1, 2, 2], which looks wrong to me.
0

I think this kind of sorting can be achieved in O(n), with something like the following:

let input = [1, 6, 6, 6, 6, 4, 3, 5, 5, 5, 2, 2] // build the frequency dictionary (easy task) let frequencies = input.reduce(into: [:]) { $0[$1] = ($0[$1] ?? 0) + 1 } // allocate a 2-D array of ints, each item in this array will hold the numbers that // appear I times in the input array let frequencyTable: [[Int]] = frequencies.reduce(into: Array(repeating: [Int](), count: input.count)) { // substracting one as arrays are zero indexed // we can't get of of bounds here since the maximum frequency is the // number of elements in the input array // Also replicating the numbers by their frequency, to have // the same contents as in the input array $0[$1.value - 1] += Array(repeating: $1.key, count: $1.value) } // lastly, simply flatten the 2-D array to get the output we need let output = frequencyTable.flatMap { $0 } print(output)

Sample result:

[4, 1, 3, 2, 2, 5, 5, 5, 6, 6, 6, 6]

Note that the order of numbers with the same frequency might differ based on how the dictionary hash function works.

Also we sacrifice space (allocated 2-D array) in favour of time.

The frequencyTable contents will look similar to this (again the order of 1, 4, 3 might differ):

[[4, 3, 1], [2, 2], [5, 5, 5], [6, 6, 6, 6], [], [], [], [], [], [], [], []]
Improve this answer

1 Comment

Otherwise known as Counting sort

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.