Given a list of lists, the task is to sort a list on the basis of size of sublists. Let’s discuss a few methods to do the same.
Method #1: Using sort
Python3
# Python code to demonstrate # sort list of list # on the basis of size of sublist ini_list = [[ 1 , 2 , 3 ], [ 1 , 2 ], [ 1 , 2 , 3 , 4 ], [ 1 , 2 , 3 , 4 , 5 ], [ 2 , 4 , 6 ]] # printing initial ini_list print ("initial list ", str (ini_list)) # sorting on basis of size of list ini_list.sort(key = len ) # printing final result print ("final list ", str (ini_list)) |
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method #2: Using lambda
Python3
# Python code to demonstrate # sort list of list # on the basis of size of sublist ini_list = [[ 1 , 2 , 3 ], [ 1 , 2 ], [ 1 , 2 , 3 , 4 ], [ 1 , 2 , 3 , 4 , 5 ], [ 2 , 4 , 6 ]] # printing initial ini_list print ("initial list ", str (ini_list)) # sorting on basis of size of list ini_list.sort(key = lambda x: len (x)) # printing final result print ("final list ", str (ini_list)) |
Method #3: Using sorted
Python3
# Python code to demonstrate # sort list of list # on the basis of size of sublist ini_list = [[ 1 , 2 , 3 ], [ 1 , 2 ], [ 1 , 2 , 3 , 4 ], [ 1 , 2 , 3 , 4 , 5 ], [ 2 , 4 , 6 ]] # printing initial ini_list print ("initial list ", str (ini_list)) # sorting on basis of size of list result = sorted (ini_list, key = len ) # printing final result print ("final list ", str (result)) |
Time Complexity: O(nlogn), where n is the length of the list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list
Method 4 : using the heapq module in Python.
Here are the steps to achieve this:
- Import the heapq module.
- Define a function that takes a list of lists and returns a list of tuples, where each tuple contains the length of a sublist and the sublist itself.
- Use the heapq module’s heapify function to convert the list of tuples into a heap.
- Use the heapq module’s heappop function to extract the tuples from the heap one by one and store them in a new list.
- Return the sorted list of sublists.
Python3
import heapq def sort_sublists(lst): # step 2 tuples = [( len (sublist), sublist) for sublist in lst] # step 3 heapq.heapify(tuples) # step 4 result = [heapq.heappop(tuples)[ 1 ] for i in range ( len (tuples))] # step 5 return result # test the function ini_list = [[ 1 , 2 , 3 ], [ 1 , 2 ], [ 1 , 2 , 3 , 4 ], [ 1 , 2 , 3 , 4 , 5 ], [ 2 , 4 , 6 ]] print ( "initial list:" , ini_list) result = sort_sublists(ini_list) print ( "final list:" , result) |
initial list: [[1, 2, 3], [1, 2], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 4, 6]] final list: [[1, 2], [1, 2, 3], [2, 4, 6], [1, 2, 3, 4], [1, 2, 3, 4, 5]]
The time complexity of this approach is O(n log n), where n is the length of the list of sublists.
The auxiliary space is O(n), since we’re creating a list of tuples with the same length as the input list.
Method #5: Using the bisect module:
- Import the bisect module.
- Initialize a list of lists called “ini_list”.
- Print the initial “ini_list”.
- Initialize an empty list called “res” to store the sorted result.
- Iterate over each sublist in “ini_list”.
- Use bisect.bisect() to find the position where the length of the current sublist should be inserted in the result list to keep it sorted.
- Insert the current sublist at the appropriate position in the result list.
Python3
import bisect # initializing list of lists ini_list = [[ 1 , 2 , 3 ], [ 1 , 2 ], [ 1 , 2 , 3 , 4 ], [ 1 , 2 , 3 , 4 , 5 ], [ 2 , 4 , 6 ]] # printing initial ini_list print ( "initial list: " , ini_list) # initializing result list res = [] # iterating over each sublist in the ini_list for l in ini_list: # finding the position where the length of the current sublist # should be inserted in the result list to keep it sorted pos = bisect.bisect([ len (x) for x in res], len (l)) # inserting the current sublist at the appropriate position res.insert(pos, l) # printing the sorted result list print ( "final list: " , res) |
initial list: [[1, 2, 3], [1, 2], [1, 2, 3, 4], [1, 2, 3, 4, 5], [2, 4, 6]] final list: [[1, 2], [1, 2, 3], [2, 4, 6], [1, 2, 3, 4], [1, 2, 3, 4, 5]]
The time complexity of this approach is O(n log n), where n is the length of the list of sublists.
The auxiliary space is O(n), since we’re creating a list of tuples with the same length as the input list.