Sort list elements by Frequency in Python

You are given a list containing duplicate elements. The goal is to arrange the list of elements in descending order by their frequency of occurrence.

For example, suppose we have a list = [2, 2, 2, 2, 3, 1, 1, 1, 4, 4], where each number represents an element in the list. The frequency of occurrence of the elements in this list is: 2 appears four times, 3 appears once, 1 appears three times, and 4 appears twice. The sorted list based on frequency would be [2, 2, 2, 2, 1, 1, 1, 4, 4, 3], where the elements with the highest frequency come first.

There are various methods to achieve the goal in Python. Some of the effective and efficient methods are listed below:

Method 1 - Using a Python Dictionary to Count the Frequency of Each Element and Sorting Based on the Frequency Count.

The program can be summarized as follows:

• Create a dictionary to store the elements as keys and frequency as their values.
• Iterate over each element in the list using a loop
• Check whether the element is already a key in the dictionary.
  • If yes, increase the frequency count by 1
  • If not, add the element as a key and set the frequency 1
• Sort the dictionary using the sorted function. The key should be the frequency of the element, and the reverse argument must be True.
• Sorted function will return a list of tuples (key, frequency). You can either loop it or convert it into a dictionary.
• Obtain a list containing all the elements sorted by their frequency using necessary methods.

Here is the Python program to sort a list of elements by frequency:

Output:

list_1 = [2, 3, 2, 8, 5, 6, 8, 6, 5, 2, 8]
Sorted list_1 = [2, 2, 2, 8, 8, 8, 5, 5, 6, 6, 3]
list_2 = [1, 4, 1, 4, 5, 4, 3, 3, 5, 2, 1]
Sorted list_2 = [1, 1, 1, 4, 4, 4, 5, 5, 3, 3, 2]

Explanation:

The above program creates a dictionary name freq_dict to store the frequency of unique elements. It then iterates over each element in the input list using a for loop. It then checks whether the element is already in the freq_dict or not. If yes, it increases the frequency by 1 and moves to the next iteration. Else, creates a new key and sets the frequency equal to 1.

Later, it sorts the freq_dict using the sorted function and passes frequency counts as the key. Also, sets the reverse = True, which sorts the dictionary by frequency in descending order.

Lastly, it creates a list named sorted_list to store the elements back. It then iterates for each key in the dictionary frequency number of times and stores them in the sorted list. In the end, it returns the sorted list of elements by frequency.

Time complexity = O(n logn): A for loop is used to iterate over each element in the list to count the frequency. The sorted algorithm used has the worst time complexity of O(n logn).

Space Complexity = O(n): We have used two data structure sorted_dict and sorted_list, whose sizes depends on the size of the input list. In the worst case, the space complexity becomes O(n), where n is the number of elements in the list.

Method 2 - Using Counter form collections to Count the Frequency of Each Element and Sorting Based on the Frequency Count.

We can easily reduce the number of lines of code in method 1 and optimize the code by using Counter from collections.

The program can be summarized as follows:

• Create a Counter object and pass the input list as the argument.
• Sort the input list using the sorted function. Pass the frequency as the key from the counter object and set the reverse = Ture.
• Return the result (a sorted list by frequency).

Output:

list_1 = [2, 3, 2, 8, 5, 6, 8, 2, 6, 5, 2, 8]
Sorted list_1 = [2, 2, 2, 2, 8, 8, 8, 5, 5, 6, 6, 3]
list_2 = [1, 4, 1, 1, 4, 5, 4, 3, 3, 5, 2, 1]
Sorted list_2 = [1, 1, 1, 1, 4, 4, 4, 5, 5, 3, 3, 2]

Explanation:

The above program creates a Counter object, passes the input list as the argument, and stores the Counter object (a dictionary) to freq_dict.

The key parameter of the sorted() function takes a lambda function as input, where The lambda function takes an element x from the list and returns a tuple (a, b) where:

• a is the negative count of the element x (i.e., -counter[x]). By taking the negative of the count, we are sorting the list in descending order of frequency.
• b is the element x itself. This is included to ensure that in the case of a tie (i.e., two elements with the same frequency), the elements are sorted in ascending order.

In the end, the function returns a sorted list.

Time Complexity = O(n logn): The sorted algorithm has the worst-case time complexity of O(n logn)

Space Complexity = O(n): The size of the sorted list depends on the size of the input list. In the worst case, it can be O(n).

Method 3 - Using dictionary comprehension and the sorted() function with a lambda function.

The program can be summarized as follows:

• Use dictionary comprehension to create a dictionary with elements as keys and their frequency as values.
• Use list.count() to count the occurrences of each element.
• Sort the dictionary using the sorted function and pass the negative frequency of the element as the key to sort in descending order.
• You can either pass the value with the frequency if you want to sort the elements in ascending order in case of a tie.
• Return the sorted list.

Output:

list_1 = [2, 3, 2, 8, 5, 6, 8, 2, 6, 5, 2, 8]
Sorted list_1 = [2, 2, 2, 2, 8, 8, 8, 5, 5, 6, 6, 3]
list_2 = [1, 4, 1, 1, 4, 5, 4, 3, 3, 5, 2, 1]       
Sorted list_2 = [1, 1, 1, 1, 4, 4, 4, 3, 3, 5, 5, 2]

Explanation:

In the above program, we have implemented the idea of dictionary comprehension to create a dictionary. The lst.count(x) returns the frequency of that element in the list which is stored in the freq_dict as the value of x.

Then have used a sorted function to sort the dictionary based on the frequency count of each element in the list. In the key argument, we have passed a lambda function that returns a tuple (-a, b) where a is the frequency count of b and b is the element itself. By taking the negative of the frequency, we are sorting the list in descending order. And in the case of a tie, the elements are sorted in ascending order that is where b comes into the picture. Finally, the function returns a sorted list.

Time Complexity = O(n logn): The sorted algorithm has the worst-case time complexity of O(n logn)

Space Complexity = O(n): The size of the sorted list depends on the size of the input list. In the worst case, it can be O(n).