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
from collections import defaultdict
test_list = [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)]
print("The original list is : " + str(test_list))
freq_map = defaultdict(int)
for idx, val in test_list:
freq_map[val] += 1
res = sorted(test_list, key = lambda ele: freq_map[ele[1]], reverse = True)
print("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(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
from collections import Counter
test_list = [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)]
print("The original list is : " + str(test_list))
freq_map = Counter(val for key, val in test_list)
res = sorted(test_list, key = lambda ele: freq_map[ele[1]], reverse = True)
print("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), 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
def sort_by_frequency(test_list):
freq_dict = {val: len(list(group)) for val, group in groupby(sorted(test_list, key=lambda x: x[1]), lambda x: x[1])}
return sorted(test_list, key=lambda x: freq_dict[x[1]], reverse=True)
test_list = [(6, 5), (1, 7), (2, 5), (8, 7), (9, 8), (3, 7)]
print("The original list is : " + str(test_list))
print("The sorted list is : " + str(sort_by_frequency(test_list)))
|
Output
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
test_list = [(6, 5), (2, 7), (2, 5), (8, 7), (9, 8), (3, 7)]
print("The original list is : " + str(test_list))
arr = np.array(test_list)
counts = np.unique(arr[:, 1], return_counts=True)
sorted_indices = np.argsort(-counts[1])
sorted_arr = np.empty_like(arr)
start = 0
for 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
res = [tuple(row) for row in sorted_arr]
print("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)
Please Login to comment...