Given a Matrix, sort by median of each row.
Input : test_list = [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]]
Output : [[1, 7, 2], [3, 4, 7], [10, 2, 4], [8, 6, 5]]
Explanation : 2 < 3 < 4 < 6, sorted increasingly by median element.Input : test_list = [[3, 4, 7], [1, 7, 2], [8, 6, 5]]
Output : [[1, 7, 2], [3, 4, 7], [8, 6, 5]]
Explanation : 2 < 3 < 6, sorted increasingly by median element.
Method #1 : Using sort() + median()
In this, we perform sort using sort() and median is computed using statistics function of computing median, median().
Python3
# Python3 code to demonstrate working of # Sort Matrix by Row Median# Using sort() + median()from statistics import mediandef med_comp(row): # computing median return median(row)# initializing listtest_list = [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]]# printing original listprint("The original list is : " + str(test_list))# inplace sorting using sort()test_list.sort(key = med_comp)# printing result print("Sorted Matrix : " + str(test_list)) |
The original list is : [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]] Sorted Matrix : [[1, 7, 2], [3, 4, 7], [10, 2, 4], [8, 6, 5]]
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method #2 : Using sorted() + lambda + median()
In this, we perform task of perform sort using sorted(), and lambda function is used as key function rather than external function.
Python3
# Python3 code to demonstrate working of # Sort Matrix by Row Median# Using sorted() + lambda + median()from statistics import median# initializing listtest_list = [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]]# printing original listprint("The original list is : " + str(test_list))# inplace sorting using sort()res = sorted(test_list, key = lambda row : median(row))# printing result print("Sorted Matrix : " + str(res)) |
The original list is : [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]] Sorted Matrix : [[1, 7, 2], [3, 4, 7], [10, 2, 4], [8, 6, 5]]
Time Complexity: O(n*nlogn) where n is the number of elements in the list “test_list”. sorted() + lambda + median() performs n*nlogn number of operations.
Auxiliary Space: O(n), extra space is required where n is the number of elements in the list
Method #3 : Using heapq.nsmallest() and statistics.median() function:
Algorithm:
1.Import the necessary modules heapq and statistics.
2.Initialize the input list.
3.For each row in the input list, calculate the median of the row using the median() function from the statistics module.
4.Sort the input list using heapq.nsmallest() function and pass the length of the input list, the input list and a lambda function that returns the 5.median of each row as the key to sort.
6.The sorted matrix is returned as output.
Python3
import heapqfrom statistics import median# initializing listtest_list = [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]]# printing original listprint("The original list is : " + str(test_list))# get the row median and use heapq.nsmallest() to sortres = heapq.nsmallest(len(test_list), test_list, key=lambda row: median(row))# printing resultprint("Sorted Matrix : " + str(res))#This code is contributed by Jyothi pinjala. |
The original list is : [[3, 4, 7], [1, 7, 2], [10, 2, 4], [8, 6, 5]] Sorted Matrix : [[1, 7, 2], [3, 4, 7], [10, 2, 4], [8, 6, 5]]
Time Complexity:
The time complexity of the program is O(n * m log m) where n is the number of rows and m is the number of columns in the matrix. The median() function takes O(m log m) time to sort each row, and the nsmallest() function takes O(n * m log m) time to sort the entire matrix.
Auxiliary Space:
The space complexity of the program is O(n * m) as we are creating a new sorted matrix.
