The task is to write a Python Program to sort a list of tuples in increasing order by the last element in each tuple.
Input: [(1, 3), (3, 2), (2, 1)] Output: [(2, 1), (3, 2), (1, 3)] Explanation: sort tuple based on the last digit of each tuple.
Methods #1: Using sorted().
Sorted() method sorts a list and always returns a list with the elements in a sorted manner, without modifying the original sequence.
Approach:
- Take a list of tuples from the user.
- Define a function that returns the last element of each tuple in the list of tuples.
- Define another function with the previous function as the key and sort the list.
- Print the sorted list.
Python3
def last(n): return n[-1] def sort(tuples): return sorted(tuples, key=last) a=[(1, 3), (3, 2), (2, 1)]print("Sorted:")print(sort(a)) |
Output:
Sorted: [(2, 1), (3, 2), (1, 3)]
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Methods #2: Using Bubble Sort.
Access the last element of each tuple using the nested loops. This performs the in-place method of sorting. The time complexity is similar to the Bubble Sort i.e. O(n^2).
Python3
# Python program to sort# a list of tuples by the second Item # Function to sort the list# of tuples by its second itemdef Sort_Tuple(tup): # getting length of list of tuples lst = len(tup) for i in range(0, lst): for j in range(0, lst-i-1): if (tup[j][-1] > tup[j + 1][-1]): temp = tup[j] tup[j]= tup[j + 1] tup[j + 1]= temp return tup # Driver Code tup =[(1, 3), (3, 2), (2, 1)] print(Sort_Tuple(tup)) |
Output:
[(2, 1), (3, 2), (1, 3)]
Time complexity: O(n^2) – The program uses a nested loop to compare each element with the rest of the elements in the list.
Auxiliary space: O(1) – The program uses a constant amount of extra space to swap elements in the list.
Methods #3: Using sort().
The sort() method sorts the elements of a given list in a specific ascending or descending order.
Python3
# Python program to sort a list of# tuples by the second Item using sort() # Function to sort the list by second item of tupledef Sort_Tuple(tup): # reverse = None (Sorts in Ascending order) # key is set to sort using second element of # sublist lambda has been used tup.sort(key = lambda x: x[-1]) return tup # Driver Code tup = [(1, 3), (3, 2), (2, 1)] # printing the sorted list of tuplesprint(Sort_Tuple(tup)) |
Output:
[(2, 1), (3, 2), (1, 3)]
Time complexity: O(n log n), where n is the number of tuples in the list.
Auxiliary space: O(1). This is because the sorting is done in place, without creating any additional data structures.
Method #4: Using Insertion Sort.
- Define a function called Sort_Tuple(tup) that takes a list of tuples as input.
- Define a variable called n and set it equal to the length of the input list.
- Use a for loop to iterate from the second element to the end of the list.
- For each element in the loop, store the tuple in a temporary variable called key.
- Define a variable called j and set it equal to the index of the element before the current element.
- Use a while loop to compare the second element of the tuple in the temporary variable with the second element of the tuple at index j.
- If the second element of the tuple at index j is greater than the second element of the tuple in the temporary variable, then swap the two tuples.
- Decrement j by 1 and continue the while loop until j is less than 0 or the second element of the tuple at index j is less than or equal to the second element of the tuple in the temporary variable.
- Insert the temporary variable into the correct position in the list.
- Return the sorted list of tuples.
Python3
def Sort_Tuple(tup): n = len(tup) for i in range(1, n): key = tup[i] j = i - 1 while j >= 0 and key[1] < tup[j][1]: tup[j + 1] = tup[j] j -= 1 tup[j + 1] = key return tup# Driver Codetup = [(1, 3), (3, 2), (2, 1)] # printing the sorted list of tuplesprint(Sort_Tuple(tup)) |
[(2, 1), (3, 2), (1, 3)]
Time complexity: O(n^2) in the worst case scenario.
Auxiliary space: O(1) as the space used is only for temporary variables.
Method #5: Using Merge Sort
- Define a function called merge_sort which will take a list as an input.
- Check the length of the list. If the length is less than or equal to 1, return the list.
- Define a variable mid which will be equal to the length of the list divided by 2.
- Define two variables left and right which will be equal to the left and right halves of the list respectively.
- Recursively call merge_sort on left and right until the length of the list is less than or equal to 1.
- Define a function called merge which will take two lists as inputs.
- Define an empty list called result.
- Define two variables i and j which will be equal to 0.
- Use a while loop to iterate through both lists until either i or j is equal to the length of the list.
- Compare the elements at i index of left and j index of right. If the element at i index of left is smaller, append it to the result list and increment i by 1. If the element at j index of right is smaller, append it to the result list and increment j by 1.
- Use a while loop to append the remaining elements of left to the result list.
- Use a while loop to append the remaining elements of right to the result list.
- Return the result list.
- Modify the Sort_Tuple function to call merge_sort instead of insertion sort.
- Return the sorted tuple.
Python3
def merge_sort(lst): if len(lst) <= 1: return lst mid = len(lst) // 2 left = lst[:mid] right = lst[mid:] left = merge_sort(left) right = merge_sort(right) return merge(left, right)def merge(left, right): result = [] i, j = 0, 0 while i < len(left) and j < len(right): if left[i][1] <= right[j][1]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 while i < len(left): result.append(left[i]) i += 1 while j < len(right): result.append(right[j]) j += 1 return resultdef Sort_Tuple(tup): return merge_sort(tup)# Driver Codetup = [(1, 3), (3, 2), (2, 1)] # printing the sorted list of tuplesprint(Sort_Tuple(tup)) |
[(2, 1), (3, 2), (1, 3)]
Time Complexity: O(n log n)
Auxiliary Space: O(n)
Method #6: Using Selection Sort
- Initialize the starting index of the unsorted sublist as 0.
- Repeat the following until the entire list is sorted:
- Find the index of the minimum element in the unsorted sublist by comparing the second element of each tuple.
- Swap the minimum element with the first element of the unsorted sublist.
- Increment the starting index of the unsorted sublist by 1.
- Return the sorted list of tuples.
Python3
# Python program to sort a list of tuples# by the second Item using Selection Sort# Function to sort the list by second# item of tupledef Sort_Tuple(tup): n = len(tup) for i in range(n-1): min_index = i # Find the minimum index for j in range(i+1, n): if tup[j][1] < tup[min_index][1]: min_index = j tup[i], tup[min_index] = tup[min_index], tup[i] # Return the tuple return tup# Driver Codetup = [(1, 3), (3, 2), (2, 1)]print(Sort_Tuple(tup)) |
[(2, 1), (3, 2), (1, 3)]
Time Complexity: O(N2)
Auxiliary Space: O(1)
Note: In the original code provided, Method #3 is redundant as tup.sort() already sorts the list in place.
