Sometimes, while working with data records, we can have a problem in which we receive data in custom format, and we need to perform a sort. We can receive both name of person and space-separated score and require to get the best to worst sorting. Lets discuss a way in which this particular problem can be solved.
Method #1 : Using split() + sort() + key function The combination of above functionalities can be used to perform this task. In this, we perform a sort using external function in which we split the string and extract the numeric part.
Python3
# Python3 code to demonstrate # Numeric Sort in Mixed Pair String List# using split() + sort() + key function# helper function def helper_func(ele): name, val = ele.split() return int(val)# Initializing listtest_list = ["Manjeet 5", "Akshat 7", "Akash 6", "Nikhil 10"]# printing original listprint("The original list is : " + str(test_list))# Numeric Sort in Mixed Pair String List# using split() + sort() + key functiontest_list.sort(key = helper_func, reverse = True) # printing result print ("The reverse sorted numerics are : " + str(test_list)) |
The original list is : ['Manjeet 5', 'Akshat 7', 'Akash 6', 'Nikhil 10'] The reverse sorted numerics are : ['Nikhil 10', 'Akshat 7', 'Akash 6', 'Manjeet 5']
Time Complexity: O(nlogn) where n is the number of elements in the list “test_list”.
Auxiliary Space: O(n) where n is the number of elements in the list “test_list”.
Method #2 : Using split() + lambda + sorted() The combination of above methods can be used to perform this task. In this, we perform split on numbers as above. The difference is that it is one liner and use lambda function to perform.
Python3
# Python3 code to demonstrate # Numeric Sort in Mixed Pair String List# using split() + sorted() + lambda# Initializing listtest_list = ["Manjeet 5", "Akshat 7", "Akash 6", "Nikhil 10"]# printing original listprint("The original list is : " + str(test_list))# Numeric Sort in Mixed Pair String List# using split() + sorted() + lambdares = sorted(test_list, reverse = True, key = lambda ele: int(ele.split()[1]))# printing result print ("The reverse sorted numerics are : " + str(res)) |
The original list is : ['Manjeet 5', 'Akshat 7', 'Akash 6', 'Nikhil 10'] The reverse sorted numerics are : ['Nikhil 10', 'Akshat 7', 'Akash 6', 'Manjeet 5']
Time Complexity: O(nlogn), where n is the length of the list test_list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res dictionary
Method #3:Recursive method.
Algorithm:
- If the length of the input list is less than or equal to 1, return the input list as it is.
- Choose the first element of the input list as the pivot.
- Create two empty sublists to store elements greater than or equal to the pivot and elements less than the pivot.
- Loop through the input list starting from the second element and compare the numeric value of each element with the pivot.
- If the numeric value of an element is greater than or equal to the pivot, append it to the left sublist. Otherwise, append it to the right sublist.
- Recursively apply the algorithm on the left and right sublists.
- Concatenate the sorted left sublist, pivot, and sorted right sublist to get the final sorted list.
Python3
def sort_mixed_pair_list(test_list): if len(test_list) <= 1: return test_list pivot = test_list[0] left = [] right = [] for ele in test_list[1:]: if int(ele.split()[1]) >= int(pivot.split()[1]): left.append(ele) else: right.append(ele) return sort_mixed_pair_list(left) + [pivot] + sort_mixed_pair_list(right)# Initializing listtest_list = ["Manjeet 5", "Akshat 7", "Akash 6", "Nikhil 10"]# printing original listprint("The original list is : " + str(test_list))# Numeric Sort in Mixed Pair String List using recursiontest_list = sort_mixed_pair_list(test_list)# printing result print("The reverse sorted numerics are : " + str(test_list)) |
The original list is : ['Manjeet 5', 'Akshat 7', 'Akash 6', 'Nikhil 10'] The reverse sorted numerics are : ['Nikhil 10', 'Akshat 7', 'Akash 6', 'Manjeet 5']
The time complexity of the recursive algorithm is O(n log n) in the average and best cases and O(n^2) in the worst case.
The space complexity is O(n) in the worst case due to the recursive call stack.
Method 4: Using heapq library
- Import the heapq library
- Create an empty list to store the result.
- Use a for loop to iterate over each element in the input list.
- For each element, split it into name and number parts.
- Append a tuple of negative integer value of number and the element to the result list. Negative value is used to sort the list in descending order of number values.
- Use the heapify() function from the heapq library to convert the list into a heap.
- Use the heappop() function in a loop to pop the smallest element from the heap and append it to a new list. Since the elements were added as negative integers, popping the smallest element from the heap will return the element with the highest numeric value.
- Reverse the resulting list to get the elements in descending order of numeric values
Python3
import heapqdef sort_mixed_pair_list(test_list): result = [] for elem in test_list: name, num = elem.split() heapq.heappush(result, (-int(num), elem)) heapq.heapify(result) sorted_list = [] while result: sorted_list.append(heapq.heappop(result)[1]) return sorted_list[::-1]# Initializing listtest_list = ["Manjeet 5", "Akshat 7", "Akash 6", "Nikhil 10"]# printing original listprint("The original list is : " + str(test_list))# Numeric Sort in Mixed Pair String List using heapq librarytest_list = sort_mixed_pair_list(test_list)# printing result print("The reverse sorted numerics are : " + str(test_list)) |
The original list is : ['Manjeet 5', 'Akshat 7', 'Akash 6', 'Nikhil 10'] The reverse sorted numerics are : ['Manjeet 5', 'Akash 6', 'Akshat 7', 'Nikhil 10']
Time complexity: O(n log n), where n is the number of elements in the input list.
Auxiliary space: O(n) for storing the result list and heap.
