Given list of tuples, sort by frequency of second element of tuple.
Input : test_list = [(6, 5), (1, 7), (2, 5), (8, 7), (9, 8), (3, 7)]
Output : [(1, 7), (8, 7), (3, 7), (6, 5), (2, 5), (9, 8)]
Explanation : 7 occurs 3 times as 2nd element, hence all tuples with 7, are aligned first.Input : test_list = [(1, 7), (8, 7), (9, 8), (3, 7)]
Output : [(1, 7), (8, 7), (3, 7), (9, 8)]
Explanation : 7 occurs 3 times as 2nd element, hence all tuples with 7, are aligned first.
Method #1 : Using sorted() + loop + defaultdict() + lambda
In this, we compute the frequency using defaultdict() and use this result to pass as param to lambda function to perform sorting using sorted() on basis of it.
Python3
# Python3 code to demonstrate working of # Sort by Frequency of second element in Tuple List# Using sorted() + loop + defaultdict() + lambdafrom collections import defaultdict# initializing listtest_list = [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)]# printing original listprint("The original list is : " + str(test_list))# constructing mappingfreq_map = defaultdict(int)for idx, val in test_list: freq_map[val] += 1# performing sort of result res = sorted(test_list, key = lambda ele: freq_map[ele[1]], reverse = True)# printing resultsprint("Sorted List of tuples : " + str(res)) |
The original list is : [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)] Sorted List of tuples : [(2, 7), (8, 7), (3, 7), (6, 5), (2, 5), (9, 8)]
Time Complexity: O(logn)
Auxiliary Space: O(n)
Method #2 : Using Counter() + lambda + sorted()
In this, the task of frequency computation is done using Counter(), rest all functionality is similar to above method.
Python3
# Python3 code to demonstrate working of # Sort by Frequency of second element in Tuple List# Using Counter() + lambda + sorted()from collections import Counter# initializing listtest_list = [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)]# printing original listprint("The original list is : " + str(test_list))# constructing mapping using Counterfreq_map = Counter(val for key, val in test_list)# performing sort of result res = sorted(test_list, key = lambda ele: freq_map[ele[1]], reverse = True)# printing resultsprint("Sorted List of tuples : " + str(res)) |
The original list is : [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)] Sorted List of tuples : [(2, 7), (8, 7), (3, 7), (6, 5), (2, 5), (9, 8)]
Time complexity: O(n log n), where n is the length of the input list test_list. The sorting operation takes O(n log n) time complexity, and constructing the frequency map using Counter() takes O(n) time complexity. Since O(n log n) is the dominant term.
Auxiliary Space: O(n), where n is the length of the input list test_list. This is because we are using a Counter() to construct a frequency map of the second element of each tuple in the input list, which takes O(n) auxiliary space. Additionally, we are storing the sorted list of tuples in memory, which also takes O(n) auxiliary space.
Method #3 : Using groupby() + sorted()
In this, the task of frequency computation is done by sorted() and groupby() functions from the itertools module.
Algorithm
Sort the input list of tuples by the second element. Count the frequency of each second element using a dictionary. Sort the input list of tuples by the frequency of the corresponding second element, in reverse order. Return the sorted list.
Python
from itertools import groupby # import groupby function from itertools moduledef sort_by_frequency(test_list): # define function called sort_by_frequency that takes a list called test_list as input freq_dict = {val: len(list(group)) for val, group in groupby(sorted(test_list, key=lambda x: x[1]), lambda x: x[1])} # create a dictionary called freq_dict where each key is a unique second element of a tuple in test_list and its value is the number of times that second element appears in test_list # we do this by using the groupby function to group the tuples in test_list by their second element, then using len to count the number of tuples in each group # we use sorted to sort the list of tuples by their second element before using groupby, and we use a lambda function to specify that we want to group by the second element of each tuple # the resulting dictionary has keys that are unique second elements from test_list and values that are the frequency of each second element in test_list return sorted(test_list, key=lambda x: freq_dict[x[1]], reverse=True) # sort the original list of tuples (test_list) based on the values in freq_dict # we use a lambda function to specify that we want to sort by the value in freq_dict corresponding to the second element of each tuple in test_list # we sort the list in reverse order (highest frequency first) test_list = [(6, 5), (1, 7), (2, 5), (8, 7), (9, 8), (3, 7)] # define test_listprint("The original list is : " + str(test_list)) # print the original listprint("The sorted list is : " + str(sort_by_frequency(test_list))) # print the sorted list returned by the sort_by_frequency function |
The original list is : [(6, 5), (1, 7), (2, 5), (8, 7), (9, 8), (3, 7)] The sorted list is : [(1, 7), (8, 7), (3, 7), (6, 5), (2, 5), (9, 8)]
Time complexity: O(n log n),where n is the length of test_list
Auxiliary Space: O(n),where n is the length of test_list
Method #4: Using numpy
- Convert the list of tuples into a numpy array.
- Use numpy’s argsort function to sort the array based on the frequency of the second element.
- Use numpy’s take function to get the sorted array based on the argsort indices.
- Convert the sorted array back to a list of tuples.
Python3
import numpy as np# initializing listtest_list = [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)]# printing original listprint("The original list is : " + str(test_list))# convert the list to a numpy arrayarr = np.array(test_list)# get the frequency of each second element using numpy's unique functioncounts = np.unique(arr[:, 1], return_counts=True)# sort the indices based on the frequency of the second element using numpy's argsort functionsorted_indices = np.argsort(-counts[1])# create an empty array to store the sorted tuplessorted_arr = np.empty_like(arr)# iterate over the sorted indices and fill in the sorted arraystart = 0for i in sorted_indices: freq = counts[1][i] indices = np.where(arr[:, 1] == counts[0][i])[0] end = start + freq sorted_arr[start:end] = arr[indices] start = end# convert the sorted array back to a list of tuplesres = [tuple(row) for row in sorted_arr]# printing resultsprint("Sorted List of tuples : " + str(res)) |
Output:
The original list is : [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)] Sorted List of tuples : [(2, 7), (8, 7), (3, 7), (6, 5), (2, 5), (9, 8)]
Time complexity: O(n log n) (due to sorting)
Auxiliary space: O(n) (due to creating a numpy array)
