Given a Matrix, perform sort based upon the sum of rows.
Input : test_list = [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]
Output : [[2, 1], [4, 5], [4, 6, 1], [2, 5, 7]]
Explanation : 3 < 9 < 11 < 14. Sorted sum.Input : test_list = [[4, 5], [2, 5, 7], [4, 6, 1]]
Output : [[4, 5], [4, 6, 1], [2, 5, 7]]
Explanation : 9 < 11 < 14. Sorted sum.
Method #1 : Using sort() + sum()
In this, task of sorting is done using sort(), and computation of sum is done by sum(), and passed as key fnc. to sort().
Python3
# Python3 code to demonstrate working of # Sort Matrix by row sum# Using sort() + sum()# helper_fncdef sum_sort(row): # getting sum return sum(row)# initializing listtest_list = [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]# printing original listprint("The original list is : " + str(test_list))# using sort() to perform sorttest_list.sort(key = sum_sort)# printing result print("Sum sorted Matrix : " + str(test_list)) |
Output:
The original list is : [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]
Sum sorted Matrix : [[2, 1], [4, 5], [4, 6, 1], [2, 5, 7]]
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method #2 : Using sorted() + sum() + lambda
In this, the task of sorting is done using sorted() and lambda is used in place of the external function call for the key.
Python3
# Python3 code to demonstrate working of# Sort Matrix by row sum# Using sorted() + sum() + lambda# initializing listtest_list = [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]# printing original listprint("The original list is : " + str(test_list))# using lambda function preventing fnc. callres = sorted(test_list, key=lambda row: sum(row))# printing resultprint("Sum sorted Matrix : " + str(res)) |
Output:
The original list is : [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]
Sum sorted Matrix : [[2, 1], [4, 5], [4, 6, 1], [2, 5, 7]]
Time Complexity: O(n*nlogn) where n is the number of elements in the list “test_list”. sorted() + sum() + lambda performs n*nlogn number of operations.
Auxiliary Space: O(1), no extra space is required
Method #3 : Using the operator module and the sorted() function:
Algorithm:
1.Initialize a list of sub-lists named ‘test_list’.
2.Import the operator module.
3.Sort the ‘test_list’ using the sorted() function and the operator module.
4.Use the ‘key’ parameter in the sorted() function to pass in the ‘operator.methodcaller’ function.
5.The ‘getitem’ method of the operator module returns the values of the sub-lists in the ‘test_list’.
6.The ‘slice(None)’ argument passed to ‘getitem’ method returns all the values of the sub-lists.
7.Store the sorted list in a variable named ‘res’.
8.Print the sorted list.
Python3
# importing operator moduleimport operator# initializing listtest_list = [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]# printing original listprint("The original list is : " + str(test_list))# using the operator module and the sorted() functionres = sorted(test_list, key=operator.methodcaller('__getitem__', slice(None)))# printing resultprint("Sum sorted Matrix : " + str(res))#This code is contributed by Jyothi pinjala |
The original list is : [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]] Sum sorted Matrix : [[2, 1], [2, 5, 7], [4, 5], [4, 6, 1]]
Time complexity:
The time complexity of the sorted() function in the operator module is O(n log n), where ‘n’ is the number of sub-lists in the ‘test_list’.
Auxiliary Space:
The space complexity of this algorithm is O(n), where ‘n’ is the number of sub-lists in the ‘test_list’. This is because a new list is created to store the sorted list.
Method 4: Using the heapq module
- Import the heapq module.
- Initialize a list of sub-lists called test_list.
- Print the original list of sub-lists.
- Create an empty list called sorted_lists to store the sorted sub-lists.
- Iterate over the range of the length of the test_list.
- Use heapq.nsmallest() function to find the smallest sub-list based on the sum of its elements. This function takes two arguments, k and iterable. k is the number of smallest elements to return, and iterable is the list of sub-lists to search.
- Append the smallest sub-list to the sorted_lists list.
- Remove the smallest sub-list from the test_list.
- Print the sorted list of sub-lists.
Python3
import heapq# initializing listtest_list = [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]# printing original listprint("The original list is : " + str(test_list))# creating an empty list to store the sorted sub-listssorted_lists = []# iterating over the original list and finding the smallest sub-list based on the sum of its elementsfor _ in range(len(test_list)): smallest = heapq.nsmallest(1, test_list, key=sum) sorted_lists.append(smallest[0]) test_list.remove(smallest[0])# printing the sorted list of sub-listsprint("Sum sorted Matrix : " + str(sorted_lists)) |
The original list is : [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]] Sum sorted Matrix : [[2, 1], [4, 5], [4, 6, 1], [2, 5, 7]]
Time complexity: O(n log n), where n is the total number of elements in the original list.
Auxiliary space: O(n), where n is the length of the original list.
Method 5: Use the built-in function min() and a custom comparison function
- Initialize a 2D list called test_list with 4 sub-lists of varying lengths and values.
- Print the original list using the print() function and the string concatenation operator +.
- Create an empty list called sorted_lists that will be used to store the sorted sub-lists.
- Define a comparison function compare_lists() that takes two sub-lists as input and returns the difference between their sums.
- Start a while loop that continues until the test_list is empty.
- Use the min() function with a lambda function as the key argument to find the smallest sub-list in the test_list based on the sum of its elements.
- If a smallest sub-list is found (i.e., it is not None), append it to the sorted_lists list using the append() method and remove it from the test_list using the remove() method.
- Repeat steps 6-7 until the test_list is empty.
- Print the sorted list of sub-lists using the print() function and string concatenation.
Python3
# initializing listtest_list = [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]]# printing original listprint("The original list is : " + str(test_list))# creating an empty list to store the sorted sub-listssorted_lists = []# defining the comparison functiondef compare_lists(list1, list2): return sum(list1) - sum(list2)# iterating over the original list and finding the smallest sub-list based on the sum of its elementswhile test_list: smallest = min(test_list, key=lambda x: sum(x), default=None) if smallest: sorted_lists.append(smallest) test_list.remove(smallest)# printing the sorted list of sub-listsprint("Sum sorted Matrix : " + str(sorted_lists)) |
The original list is : [[4, 5], [2, 5, 7], [2, 1], [4, 6, 1]] Sum sorted Matrix : [[2, 1], [4, 5], [4, 6, 1], [2, 5, 7]]
Time complexity: O(n^2 log n), where n is the total number of elements in the original list.
Auxiliary space: O(n), since we need to store the sorted list of sub-lists.
