Sometimes, while working with Python list, we can come across a problem in which we need to sort the list according to any tuple element. These must be a generic way to perform the sort by particular tuple index. This has a good utility in web development domain. Let’s discuss certain ways in which this task can be performed.
Method #1: Using sort() + lambda The combination of above functions can be used to perform this task. In this, we just pass a lambda function to sort() with an appropriate tuple element index according to which sort has to be performed.
Step-by-step approach:
- Set the value of variable N to 1.
- Use the sort() method to sort the list of tuples test_list based on the Nth element of each tuple.
- The sorting is done using the lambda function which takes each tuple as its argument and returns the Nth element of the tuple.
- Print the sorted list of tuples test_list.
Below is the implementation of the above approach:
Python3
# Python3 code to demonstrate working of# Sort tuple list by Nth element of tuple# using sort() + lambda# initializing listtest_list = [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)]# printing original listprint("The original list is : " + str(test_list))# index according to which sort to performN = 1# Sort tuple list by Nth element of tuple# using sort() + lambdatest_list.sort(key = lambda x: x[N])# printing result print("List after sorting tuple by Nth index sort : " + str(test_list)) |
The original list is : [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)] List after sorting tuple by Nth index sort : [(6, 1, 5), (6, 2, 4), (7, 4, 2), (4, 5, 1)]
Time Complexity: O(n*logn)
Auxiliary Space: O(1)
Method #2: Using sort() + itemgetter() This is similar to the above method. The difference is just that we use itemgetter(), to perform this task that is done by lambda in the above method.
Step-by-step approach:
- It initializes the variable N to a value of 1, indicating that we want to sort the list based on the second element of each tuple.
- It uses the sort() method of the test_list object and passes in the key argument, which is set to the itemgetter(N) function. This means that the sort() method will sort the list based on the element at the Nth index of each tuple.
- It prints the sorted list using the print() function and string concatenation.
Below is the implementation of the above approach:
Python3
# Python3 code to demonstrate working of# Sort tuple list by Nth element of tuple# using sort() + itemgetter()from operator import itemgetter# initializing listtest_list = [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)]# printing original listprint("The original list is : " + str(test_list))# index according to which sort to performN = 1# Sort tuple list by Nth element of tuple# using sort() + itemgetter()test_list.sort(key = itemgetter(N))# printing result print("List after sorting tuple by Nth index sort : " + str(test_list)) |
The original list is : [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)] List after sorting tuple by Nth index sort : [(6, 1, 5), (6, 2, 4), (7, 4, 2), (4, 5, 1)]
Time Complexity: O(n log n) – Sorting the list using sort() method.
Auxiliary Space: O(1) – No extra space is used.
Method #3: using sorted and custom function
Python3
# Python3 code to demonstrate working of# Sort tuple list by Nth element of tuple# using sorted() and custom function# custom sorting functiondef sort_by_nth_element(tup): return tup[N]# initializing listtest_list = [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)]# printing original listprint("The original list is : " + str(test_list))# index according to which sort to performN = 1# Sort tuple list by Nth element of tuple using sorted() and custom functionsorted_list = sorted(test_list, key = sort_by_nth_element)# printing resultprint("List after sorting tuple by Nth index sort : " + str(sorted_list))#This code is contributed by Edula Vinay Kumar Reddy |
The original list is : [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)] List after sorting tuple by Nth index sort : [(6, 1, 5), (6, 2, 4), (7, 4, 2), (4, 5, 1)]
Time complexity: O(n log n), where n is the number of tuples in the list
Auxiliary space: O(n log n), where n is the number of tuples in the list
Method #4: using Bubble sort algorithm
It is a simple sorting algorithm, In this we use a flag variable to keep track of any swaps made during a pass of the outer loop if no swaps were made the list is already sorted and the loop can be broken.
Python3
test_list = [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)]N=1print("The original list:",test_list )# initialize the flag variable to indicate if any swap has been madeflag = True# while loop runs until no more swaps are madewhile flag: # reset the flag variable flag = False # outer for loop iterates through the elements in the list for i in range(len(test_list ) - 1): # inner for loop starts from next element of outer for loop and compare with outer for loop element for j in range(i+1, len(test_list )): # check if second element in the tuple of the first element is less than the second element in the tuple of the next element if test_list [i][N] < test_list [j][N]: # swap the elements test_list [i], test_list [j] = test_list [j], test_list[i] # set the flag variable to indicate that a swap has been made flag = True# print the sorted listprint("Sorted list:", test_list ) |
The original list: [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)] Sorted list: [(4, 5, 1), (7, 4, 2), (6, 2, 4), (6, 1, 5)]
Time complexity : O(n^2)
Auxiliary Space: O(1)
Method 5: Using the heapq.nsmallest() function
This approach uses the heapq.nsmallest() function to return a sorted list of tuples. The nsmallest() function takes three arguments: n, the number of smallest elements to return (in this case, the length of the list); iterable, the list of tuples to sort; and key, a function that returns the value of the Nth element of each tuple. The resulting sorted list is assigned to the sorted_list variable.
Python3
import heapq# initializing listtest_list = [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)]# printing original listprint("The original list is : " + str(test_list))# index according to which sort to performN = 1# Sort tuple list by Nth element of tuplesorted_list = heapq.nsmallest(len(test_list), test_list, key=lambda x: x[N])# printing resultprint("List after sorting tuple by Nth index sort : " + str(sorted_list)) |
The original list is : [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)] List after sorting tuple by Nth index sort : [(6, 1, 5), (6, 2, 4), (7, 4, 2), (4, 5, 1)]
Time complexity: O(n log n), where n is the length of the input list, because it uses a heap to sort the list.
Auxiliary space: O(n), because it creates a new sorted list.
Method#6: Using Recursive method.
Algorithm:
- Define a function called sort_tuple_by_nth_index which takes a list called test_list and an integer called N as input.
- Check if the length of the list is 1 or less, return the list as it is already sorted.
- Otherwise, set the pivot as the Nth element of the first element in the list.
- Create two sublists, one containing elements less than or equal to the pivot and the other containing elements greater than the pivot.
- Recursively sort the two sublists by calling the sort_tuple_by_nth_index function on them.
- Concatenate the sorted sublists with the first element of the original list in the middle.
- Return the sorted list.
Python3
def sort_tuple_by_nth_index(test_list, N): # base case: if the length of the list is 1 or less, it is already sorted if len(test_list) <= 1: return test_list # recursive case: # divide the list into two sublists, one containing elements less than or equal to the Nth element of the first element # and the other containing elements greater than the Nth element of the first element pivot = test_list[0][N] less_than_or_equal = [t for t in test_list[1:] if t[N] <= pivot] greater_than = [t for t in test_list[1:] if t[N] > pivot] # recursively sort the two sublists sorted_less_than_or_equal = sort_tuple_by_nth_index(less_than_or_equal, N) sorted_greater_than = sort_tuple_by_nth_index(greater_than, N) # return the sorted concatenation of the two sublists return sorted_less_than_or_equal + [test_list[0]] + sorted_greater_thantest_list = [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)]N = 1print("The original list:", test_list)sorted_list = sort_tuple_by_nth_index(test_list, N)print("List after sorting tuple by Nth index sort:", sorted_list) |
The original list: [(4, 5, 1), (6, 1, 5), (7, 4, 2), (6, 2, 4)] List after sorting tuple by Nth index sort: [(6, 1, 5), (6, 2, 4), (7, 4, 2), (4, 5, 1)]
The time complexity of the algorithm is O(nlogn) in the average and worst-case scenarios. This is because the algorithm uses a divide-and-conquer strategy, dividing the list into sublists and sorting them recursively.
The space complexity of the algorithm is O(n) due to the recursion stack. However, the worst-case scenario for space complexity is O(n^2) if the algorithm encounters a very unbalanced split of the input list at each recursive call.
