Sometimes, while working with data, we can have a problem of sorting them. There are many types of basis on which sorting can be performed. But this article discusses sorting on basis of difference of both elements of pair. Let’s discuss certain ways in which this can be done.
Method #1 : Using sorted() + lambda The combination of above functionalities can be used to solve this problem. In this, sorting is performed by sorted() and lambda function is fed as key to perform desired sorting.
Python3
# Python3 code to demonstrate working of# Sort tuple list on basis of difference of elements# using sorted() + lambda# initialize list test_list = [(1, 4), (6, 5), (8, 10)]# printing original list print("The original list : " + str(test_list))# Sort tuple list on basis of difference of elements# using sorted() + lambdares = sorted(test_list, key = lambda sub: abs(sub[1] - sub[0]))# printing resultprint("List after sorting by difference : " + str(res)) |
The original list : [(1, 4), (6, 5), (8, 10)] List after sorting by difference : [(6, 5), (8, 10), (1, 4)]
Time Complexity: O(nlogn), where n is the length of the input list. This is because we’re using sorted() + lambda which has a time complexity of O(nlogn) in the worst case.
Auxiliary Space: O(n), as we’re using additional space res other than the input list itself with the same size of input list.
Method #2 : Using sort() + comparator + cmp() This is yet another way to perform this task. In this, we pass the sort(), a comparator function which performs the similar difference logic using cmp(). Works only in Python2.
Python
# Python code to demonstrate working of# Sort tuple list on basis of difference of elements# using sort() + comparator + cmp()# comparator functiondef diff_sort(ele1, ele2): return cmp(ele2[0] - ele2[1], ele1[0] - ele1[1])# initialize list test_list = [(1, 4), (6, 5), (8, 10)]# printing original list print("The original list : " + str(test_list))# Sort tuple list on basis of difference of elements# using sort() + comparator + cmp()test_list.sort(diff_sort)# printing resultprint("List after sorting by difference : " + str(test_list)) |
The original list : [(1, 4), (6, 5), (8, 10)] List after sorting by difference : [(6, 5), (8, 10), (1, 4)]
Time Complexity: O(n*nlogn), where n is the length of the list test_dict
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list
Method #3 : Using itemgetter
In this, we import the itemgetter function from the operator module. The itemgetter function takes an index as input and returns a function that retrieves that index from a tuple. We then use the itemgetter function to retrieve the first and second elements of each tuple and calculate their absolute difference. Finally, we pass the lambda function as the key for the sorted function to sort the list based on the difference between the elements of each tuple. The resulting sorted list is then printed to the console.
Python3
from operator import itemgetter# Original list of tuplesoriginal_list = [(1, 4), (6, 5), (8, 10)]# Sort the list by difference using itemgetter as keysorted_list = sorted(original_list, key=lambda x: abs(itemgetter(0)(x) - itemgetter(1)(x)))# Print the sorted listprint("List after sorting by difference:", sorted_list) |
List after sorting by difference: [(6, 5), (8, 10), (1, 4)]
The complexity analysis of the code is as follows:
Defining the original list of tuples:
This step takes O(n) time, where n is the size of the original list.
Sorting the list by difference using itemgetter as key:
Sorting takes O(nlogn) time in the worst case, where n is the size of the original list. Since we are sorting based on the difference between the first and second elements of each tuple, the time complexity of each comparison operation between the elements of the list is O(1). Therefore, the overall time complexity of the sorting operation in this code is O(nlogn).
Printing the sorted list:
This step takes O(n) time, where n is the size of the sorted list.
time complexity: O(nlogn)
Method #4: using the heapq module:
Algorithm:
1.Create a heap of tuples, where each tuple contains the difference between the two elements of the input tuple and the input tuple itself.
2.Heapify the created heap.
3.Pop the elements from the heap and add them to the output list until the heap is empty.
Python3
import heapq# initialize listtest_list = [(1, 4), (6, 5), (8, 10)]# printing original listprint("The original list : " + str(test_list))# Sort tuple list on basis of difference of elements# using heapq moduleheap = [((ele[1]-ele[0]), ele) for ele in test_list]heapq.heapify(heap)test_list = [heapq.heappop(heap)[1] for i in range(len(heap))]# printing resultprint("List after sorting by difference : " + str(test_list))#This code is contributed by Jyothi pinjala |
The original list : [(1, 4), (6, 5), (8, 10)] List after sorting by difference : [(6, 5), (8, 10), (1, 4)]
Time Complexity:
The time complexity of creating the heap is O(n), where n is the number of tuples in the input list. The time complexity of heapifying the heap is O(nlogn). The time complexity of popping the elements from the heap is O(nlogn). Therefore, the overall time complexity is O(nlogn).
Space Complexity:
The space complexity of creating the heap is O(n), where n is the number of tuples in the input list. The space complexity of heapifying the heap is O(1). The space complexity of popping the elements from the heap is O(1). Therefore, the overall space complexity is O(n).
