How to sort a list of integers by frequncy using comparators in Python?

Question

I have written a program that sorts a given list of integers according to frequency of elements. That is elements that have higher frequency come first. If frequencies of two elements are same, then smaller number comes first.

But my code doesn't print output correctly I have made use of comparators and imported the functools library and made use of the sub function cmp_to_key to generate the final result.

here is my code

class Element:
    def __init__(self, val, freq, idx):
        self.val = val
        self.freq = freq
        self.idx = idx

import functools

class Solution:
    def sortElements(self, array):
        frequency = self.findFrequencies(array)
        elements=[]
        for i in range(len(array)):
            val = array[i]
            freq = frequency[val]
            idx = i
            el=Element(val,freq,idx)
            elements.append(el)
        
        sortedElements = sorted(elements, key=functools.cmp_to_key(self.customSortingComparator))
        for i in sortedElements:
            print(i.val, end=" ")
        
    def customSortingComparator(self, e1, e2):
        #print("E1: ",e1.val, e1.freq, e1.idx)
        #print("E2: ",e2.val, e2.freq, e2.idx)
        if(e1.freq!=e2.freq):
            return 1 if e1.freq<e2.freq else -1
        if(e1.idx!=e2.idx):
            return -1 if e1.idx<e2.idx else 1
        if(e1.val!=e2.val):
            return -1 if e1.val<e2.val else 1
        
            
        
    
    def findFrequencies(self, array):
        frequency={}
        for i in array:
            frequency[i] = frequency.get(i, 0)+1
    
        return frequency

sol=Solution()
sol.sortElements([2, 5, 2, 6, -1, 9999999, 5, 8, 8, 8])

Output: 8 8 8 2 5 2 5 6 -1 9999999
Desired O/P: 8 8 8 2 2 5 5 6 -1 9999999 

I suspect the error in my comparator logic, can someone please me fix this?

Here are some contstraints:

1. cannot use the lambda function to get the result,
2. cannot use any external library like pandas,numpy, etc. to get the result
3. This exercise strictly needs to be performed making use of functools.cmp_to_key that needs to be passed in the sorted() function.

Answer 1

The problem appears to be cause by sorting by idx instead of by val.

remove this:

if(e1.idx!=e2.idx):
            return -1 if e1.idx<e2.idx else 1

Not sure why you put it there, considering the constraints.