Python program to sort tuples by frequency of their absolute difference

Given a list of dual tuples, the task here is to write a Python program that can sort them by the frequency of their elements’ absolute differences.

Input : [(1, 6), (11, 3), (9, 1), (6, 11), (2, 10), (5, 7)]
Output : [(5, 7), (1, 6), (6, 11), (11, 3), (9, 1), (2, 10)]
Explanation : 7 - 5 = 2 occurs only 1 time. 5 occurs twice [( 6 - 1), (11 - 6)] 
              and 8 occurs 3 times as difference.

Input : [(1, 6), (6, 11), (5, 7)]
Output : [(5, 7), (1, 6), (6, 11)]
Explanation : 7 - 5 = 2 occurs only 1 time. 5 occurs twice [( 6 - 1), (11 - 6)].

Method 1: Using sorted(), abs(), count() and list comprehension

In this, we perform the task of computing each absolute difference using abs() and list comprehension. Then, sorted() and count() are used to sort tuples based on computed results of absolute difference.

Output:

The original list is : [(1, 6), (11, 3), (9, 1), (6, 11), (2, 10), (5, 7)]

Sorted Tuples : [(5, 7), (1, 6), (6, 11), (11, 3), (9, 1), (2, 10)]

Time Complexity: O(n*logn)
Auxiliary Space: O(1)

Method 2: operator.countOf() and list comprehension

The original list is : [(1, 6), (11, 3), (9, 1), (6, 11), (2, 10), (5, 7)]
Sorted Tuples : [(5, 7), (1, 6), (6, 11), (11, 3), (9, 1), (2, 10)]

Time Complexity: O(NLogN), where n is the length of the given string
Auxiliary Space: O(N)

Method 3: Using the map() function and a lambda function 

Step-by-step approach:

• Initialize the list of tuples.
• Use the map() function to create a list of the absolute differences between each tuple’s elements:
• Use the sorted() function with a lambda function as the key argument to sort the list of tuples by their corresponding absolute differences.
• Print the sorted list of tuples.

The original list is : [(1, 6), (11, 3), (9, 1), (6, 11), (2, 10), (5, 7)]
Sorted Tuples : [(5, 7), (1, 6), (6, 11), (11, 3), (9, 1), (2, 10)]

Time complexity: O(nlogn), where n is the length of the list of tuples since sorting takes O(nlogn) time. 
Auxiliary space: O(n), since we create a list of absolute differences that is the same length as the list of tuples

Method 4: Using the heapq module 

• Compute the absolute differences between the first and second elements of each tuple in the test_list using a list comprehension, and store the resulting list in diff_list.
• Create a new list of tuples named heap by zipping together diff_list and test_list using the zip() function, creating a tuple of (diff, t) for each element t in test_list and its corresponding absolute difference.
• Use the heapify() function from the heapq module to transform heap into a heap data structure. This step ensures that the tuples in heap are in heap order, which means that the smallest absolute difference is at the root of the heap.
• Use a list comprehension to extract the second element of each tuple in heap in heap order by repeatedly calling the heappop() function from the heapq module, which returns and removes the smallest element in the heap. We repeat this process a number of times equal to the length of the heap, storing each second element of the popped tuple in a new list named res.
• Print the sorted list of tuples named res using the print() function and string formatting to convert the list to a string.

The original list is : [(1, 6), (11, 3), (9, 1), (6, 11), (2, 10), (5, 7)]
Sorted Tuples : [(5, 7), (1, 6), (6, 11), (2, 10), (9, 1), (11, 3)]

Time complexity: O(n log n) 
Auxiliary space: O(n)