Sorting is an essential utility used in majority of programming, be it for competitive programming or development. Conventional sorting has been dealt earlier many times. This particular article deals with sorting with respect to some other list elements.
Let’s discuss certain ways to sort list according to other list order.
Method #1 : Using List comprehension
List comprehension can be used to achieve this particular task. In this, we just check for each element in list 2 matches with the current tuple, and append accordingly, in a sorted manner.
Python3
# Python3 code to demonstrate# to sort according to other list# using list comprehension# initializing list of tuplestest_list = [ ('a', 1), ('b', 2), ('c', 3), ('d', 4)]# initializing sort ordersort_order = ['d', 'c', 'a', 'b']# printing original listprint ("The original list is : " + str(test_list))# printing sort order listprint ("The sort order list is : " + str(sort_order))# using list comprehension# to sort according to other listres = [tuple for x in sort_order for tuple in test_list if tuple[0] == x]# printing resultprint ("The sorted list is : " + str(res)) |
The original list is : [('a', 1), ('b', 2), ('c', 3), ('d', 4)]
The sort order list is : ['d', 'c', 'a', 'b']
The sorted list is : [('d', 4), ('c', 3), ('a', 1), ('b', 2)]
Time complexity: O(n^2), where n is the length of the input list test_list.
Auxiliary Space: O(n), where n is the length of the input list test_list, for storing the result list res.
Method #2 : Using sort() + lambda + index()
The shorthand to perform this particular operation, sort function can be used along with lambda with key to specify the function execution for each pair of tuple, and list order of other list is maintained using index function.
Python3
# Python code to demonstrate# to sort according to other list# using sort() + lambda + index()# initializing list of tuplestest_list = [ ('a', 1), ('b', 2), ('c', 3), ('d', 4)]# initializing sort ordersort_order = ['d', 'c', 'a', 'b']# printing original listprint ("The original list is : " + str(test_list))# printing sort order listprint ("The sort order list is : " + str(sort_order))# using sort() + lambda + index()# to sort according to other list# test_list.sort(key = lambda(i, j): sort_order.index(i)) # works in python 2test_list.sort(key = lambda i: sort_order.index(i[0])) # works in python 3# printing resultprint ("The sorted list is : " + str(test_list)) |
The original list is : [('a', 1), ('b', 2), ('c', 3), ('d', 4)]
The sort order list is : ['d', 'c', 'a', 'b']
The sorted list is : [('d', 4), ('c', 3), ('a', 1), ('b', 2)]
Time Complexity: O(n*logn), as sort() function is used.
Auxiliary Space : O(n), where n is length test_list.
Method #3 : Using dictionary
Here is an alternative approach that you can use:
- Create an empty result list.
- Create a dictionary that maps the elements in the sort order list to their indices.
- Iterate over the tuples in the original list.
- For each tuple, get the index of its first element in the sort order list using the dictionary.
- Append the tuple and its index to a list of tuples.
- Sort the list of tuples by index using the sort() function and a lambda function as the key.
- Append the sorted tuples to the result list.
- Return the result list.
Here is an example of how you can implement this approach:
Python3
# Initialize the original list and the sort order listtest_list = [('a', 1), ('b', 2), ('c', 3), ('d', 4)]sort_order = ['d', 'c', 'a', 'b']# Create a dictionary that maps the elements in the sort order list to their indicessort_order_dict = {x: i for i, x in enumerate(sort_order)}# Create a list of tuples (tuple, index)tuple_list = [(tuple, sort_order_dict[tuple[0]]) for tuple in test_list]# Sort the list of tuples by index using the sort() function and a lambda function as the keytuple_list.sort(key=lambda x: x[1])# Append the sorted tuples to the result listresult = [tuple for tuple, index in tuple_list]# Print the resultprint(result) |
[('d', 4), ('c', 3), ('a', 1), ('b', 2)]
Time complexity: O(n log n) because it involves sorting the list of tuples, which has a time complexity of O(n log n) . However, it may be faster in practice if the lists are small and the tuples are already stored in memory.
Auxiliary space: O(n) because it involves creating a new list and a dictionary with a size proportional to the number of elements in the original list.
Method #4: Using a custom function and sorted() function
Steps:
- Initialize the original list and the sort order list
- Create a custom function to retrieve the index of an element in the sort order list
- Use the sorted() function with the custom function as the key to sort the original list based on the sort order list
- Store the sorted list in the result variable
- Print the result
Python3
# Initialize the original list and the sort order listtest_list = [('a', 1), ('b', 2), ('c', 3), ('d', 4)]sort_order = ['d', 'c', 'a', 'b']# Define a custom function to retrieve the index of an element in the sort order listdef get_index(element): return sort_order.index(element[0])# Sort the original list based on the sort order list using sorted() function and the custom function as the keyresult = sorted(test_list, key=get_index)# Print the resultprint(result) |
[('d', 4), ('c', 3), ('a', 1), ('b', 2)]
Time complexity: O(nlogn) (due to the use of sorted() function)
Auxiliary space: O(n) (for storing the sorted list in the result variable)
