Given a list containing repeated and non-repeated elements, the task is to sort the given list on basis of the frequency of elements. Let’s discuss few methods for the same.
Method #1: Using collections.counter()
Python3
# Python code to demonstrate# sort list by frequency# of elementsfrom collections import Counterini_list = [1, 2, 3, 4, 4, 5, 5, 5, 5, 7, 1, 1, 2, 4, 7, 8, 9, 6, 6, 6]# printing initial ini_listprint ("initial list", str(ini_list))# sorting on basis of frequency of elementsresult = [item for items, c in Counter(ini_list).most_common() for item in [items] * c]# printing final resultprint("final list", str(result)) |
Output:
initial list [1, 2, 3, 4, 4, 5, 5, 5, 5, 7, 1, 1, 2, 4, 7, 8, 9, 6, 6, 6] final list [5, 5, 5, 5, 1, 1, 1, 4, 4, 4, 6, 6, 6, 2, 2, 7, 7, 3, 8, 9]
Time Complexity: O(n), where n is the length of the list ini_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the ini list
Method #2: Using iterables
Python3
# Python code to demonstrate# sort list by frequency# of elementsfrom collections import Counterfrom itertools import repeat, chainini_list = [1, 2, 3, 4, 4, 5, 5, 5, 5, 7, 1, 1, 2, 4, 7, 8, 9, 6, 6, 6]# printing initial ini_listprint ("initial list", str(ini_list))# sorting on basis of frequency of elementsresult = list(chain.from_iterable(repeat(i, c) for i, c in Counter(ini_list).most_common()))# printing final resultprint("final list", str(result)) |
Output:
initial list [1, 2, 3, 4, 4, 5, 5, 5, 5, 7, 1, 1, 2, 4, 7, 8, 9, 6, 6, 6] final list [5, 5, 5, 5, 1, 1, 1, 4, 4, 4, 6, 6, 6, 2, 2, 7, 7, 3, 8, 9]
Time Complexity: O(n), where n is the length of the list ini_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the ini list
Method #3: Using sorted
Python3
# Python code to demonstrate# sort list by frequency# of elementsini_list = [1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 4, 4, 4, 4, 4, 4]# printing initial ini_listprint ("initial list", str(ini_list))# sorting on basis of frequency of elementsresult = sorted(ini_list, key = ini_list.count, reverse = True)# printing final resultprint("final list", str(result)) |
Output:
initial list [1, 1, 2, 2, 2, 3, 3, 3, 3, 3, 5, 5, 5, 4, 4, 4, 4, 4, 4] final list [4, 4, 4, 4, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2, 5, 5, 5, 1, 1]
Time Complexity: O(n*logn)
Auxiliary Space: O(n), where n is length of list
Method #4: Using dictionary comprehension
Here is an example of how the to use dictionary comprehension for creating the frequency dictionary:
Python3
ini_list = [1, 2, 3, 4, 4, 5, 5, 5, 5, 7, 1, 1, 2, 4, 7, 8, 9, 6, 6, 6]# create a dictionary to store the frequency of each element using dictionary comprehensionfrequency_dict = {element: ini_list.count(element) for element in ini_list}# sort the dictionary by values in descending ordersorted_dict = {k: v for k, v in sorted(frequency_dict.items(), key=lambda item: item[1], reverse=True)}# create a new list with the elements in the sorted orderresult = []for element, frequency in sorted_dict.items(): result.extend([element] * frequency)# print the final resultprint(result)#This code is contributed by Edula Vinay Kumar Reddy |
[5, 5, 5, 5, 1, 1, 1, 4, 4, 4, 6, 6, 6, 2, 2, 7, 7, 3, 8, 9]
Using dictionary comprehension allows us to create the frequency dictionary in a single line of code, which can make the code more concise and easier to read.
Time complexity: O(nlogn)
Auxiliary Space: O(n)
