Python – Order Tuples by List

Sometimes, while working with Python tuples, we can have a problem in which we need to perform ordering of all the tuples keys using external list. This problem can have application in data domains such as Data Science. Let’s discuss certain ways in which this task can be performed.

Input : test_list = [(‘Gfg’, 10), (‘best’, 3), (‘CS’, 8), (‘Geeks’, 7)], ord_list = [‘Geeks’, ‘best’, ‘CS’, ‘Gfg’] 
Output : [(‘Geeks’, 7), (‘best’, 3), (‘CS’, 8), (‘Gfg’, 10)] 

Input : test_list = [(‘best’, 3), (‘CS’, 8), (‘Geeks’, 7)], ord_list = [‘Geeks’, ‘best’, ‘CS’] 
Output : [(‘Geeks’, 7), (‘best’, 3), (‘CS’, 8)]

Method #1 : Using dict() + list comprehension The combination of above functions can be used to solve this problem. In this, we perform this task by converting tuple list to dictionaries, and as a second step use list comprehension to iterate through list and map the dictionary keys with values. 

The original list is : [('Gfg', 3), ('best', 9), ('CS', 10), ('Geeks', 2)]
The ordered tuple list : [('Geeks', 2), ('best', 9), ('CS', 10), ('Gfg', 3)]

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

Method #2 : Using setdefault() + sorted() + lambda The combination of above functions can be used to solve this problem. In this, we perform task of mapping elements to indices and creating a lookup using setdefault. And, as a second step, using sorted to sort list using lookup dictionary value list. 

The original list is : [('Gfg', 3), ('best', 9), ('CS', 10), ('Geeks', 2)]
The ordered tuple list : [('Geeks', 2), ('best', 9), ('CS', 10), ('Gfg', 3)]

Time complexity: O(n log n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.

Method #3: Using lists and index() method

The original list is : [('Gfg', 3), ('best', 9), ('CS', 10), ('Geeks', 2)]
The ordered tuple list : [('Geeks', 2), ('best', 9), ('CS', 10), ('Gfg', 3)]

Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list .

Method #4 : Using lambda

Approach

Using the sorted function and a lambda function to sort the tuples based on the index of the first element in ord_list.

Algorithm

1. Sort the test_list using the sorted() function with a lambda function that takes a tuple as an argument and returns the index of its first element in ord_list.
2. Return the sorted list of tuples.

[('Geeks', 7), ('best', 3), ('CS', 8), ('Gfg', 10)]

Time complexity: O(nlogn) because we sort the list of tuples. 
Auxiliary Space: O(n) because we create a dictionary with n elements.

METHOD 4:Using sorted() function with itemgetter() function

APPROACH:

This program orders a list of tuples based on the second element of each tuple

ALGORITHM:

1.Import the itemgetter function from the operator module.
2.Define the original list of tuples.
3.Sort the list using the sorted() function with itemgetter(1) as the key parameter.
4.Store the sorted list in a new variable.
5.Print the new ordered list.

[('Geeks', 2), ('Gfg', 3), ('best', 9), ('CS', 10)]

Time Complexity: O(nlogn): Sorting the list takes O(nlogn) time complexity.

Space Complexity: O(n): A new list is created to store the sorted tuples, which takes O(n) space complexity.

METHOD 5:Using reduce():

Algorithm:

1. Initialize the original list with tuples and the order list.
2. Create an empty list res to hold the ordered tuples.
3. Iterate over the tuples in the original list, extract the first element of each tuple and append it to a list x.
4. Iterate over the elements of the order list.
5. If the current element is in the list x, then append the corresponding tuple to the list res.
6. Return the list res.
    

The original list is : [('Gfg', 3), ('best', 9), ('CS', 10), ('Geeks', 2)]
The ordered tuple list : [('Geeks', 2), ('best', 9), ('CS', 10), ('Gfg', 3)]

Time Complexity:

Creating the original list and order list takes constant time O(1).
Iterating over the tuples in the original list takes O(n) time, where n is the number of tuples in the original list.
Extracting the first element of each tuple and appending it to the list x takes O(n) time.
Iterating over the elements of the order list takes O(m) time, where m is the number of elements in the order list.
If the current element is in the list x, then finding its index in the list x takes O(1) time, and appending the corresponding tuple to the list res takes O(1) time. This step is executed at most m times.
Therefore, the total time complexity of the code is O(n + m).

Space Complexity:

The space required to store the original list and order list is O(1).
The space required to store the list res is at most O(m).
The space required to store the list x is at most O(n).
Therefore, the total space complexity of the code is O(n + m).

manjeet_04

Follow

Improve