Python | Sort list of list by specified index

We can sort the list of lists by using the conventional sort function. This sort the list by the specified index of lists. Let’s discuss certain ways in which this task can be performed using Python.

Method 1: Using the bubble sort algorithm

Bubble sort is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted.

Step-by-step approach:

• Initialize a variable n to the length of the input list.
• Loop through the list n times.
  • For each iteration, loop through the list from index 0 to index n-2.
    • For each pair of adjacent items, check if the second element of the left item is greater than the second element of the right item. If yes, swap the two items.
• After completing all iterations, return the sorted list.

Below is the implementation of the above approach:

The original list is : [['Rash', 4, 28], ['Varsha', 2, 20], ['Nikhil', 1, 20], ['Akshat', 3, 21]]
List after sorting by 2nd element of lists : [['Nikhil', 1, 20], ['Varsha', 2, 20], ['Akshat', 3, 21], ['Rash', 4, 28]]

Time complexity: O(n^2)
Auxiliary space: O(1). 

Method 2: Sort list of lists using sort() + lambda

The anonymous nature of Python Lambda Functions indicates that they lack a name. The Python sort() can be used to perform this variation of sort by passing a function. The list can be sorted using the sort function both ascendingly and descendingly. 

Follow the below steps to implement the above idea:

• Initialize a list named “test_list” with four nested lists, each containing a string and two integers.
• Print the original list using the print() function and concatenation of a string and the “test_list” variable.
• Sort the “test_list” using the sort() method with the key parameter set to a lambda function that returns the second element of each nested list, which is the integer at index 1.
• Print the sorted list using the print() function and concatenation of a string and the “test_list” variable.

Below is the implementation of the above approach:

The original list is : [['Rash', 4, 28], ['Varsha', 2, 20], ['Nikhil', 1, 20], ['Akshat', 3, 21]]
List after sorting by 2nd element of lists : [['Nikhil', 1, 20], ['Varsha', 2, 20], ['Akshat', 3, 21], ['Rash', 4, 28]]

Time complexity: O(n log n) due to the sorting operation, where n is the length of the input list. 
Auxiliary space: O(1) because the sorting is done in-place and no additional data structures are used.

Method 3: Sort a list of lists using sorted() + itemgetter() 

The Itemgetter can be used instead of the lambda function to achieve similar functionality. itemgetter() is used to get the index element by which the sort operation needs to be performed.  

Step-by-step approach:

• The program first imports the itemgetter function from the operator module.
• It initializes a list of lists test_list with four elements, each containing three values.
• It prints the original list using the print() function and string concatenation.
• It then uses the sorted() function to sort the list of lists test_list by the second element of each sublist using the itemgetter() function as the key.
• It assigns the sorted list to the variable res.
• Finally, it prints the sorted list using the print() function and string concatenation.

Below is the implementation of the above approach:

The original list is : [['Rash', 4, 28], ['Varsha', 2, 20], ['Nikhil', 1, 20], ['Akshat', 3, 21]]
List after sorting by 2nd element of lists : [['Nikhil', 1, 20], ['Varsha', 2, 20], ['Akshat', 3, 21], ['Rash', 4, 28]]

Time complexity: O(n log n), where n is the number of elements in the input list.
Auxiliary space: O(n), where n is the number of elements in the input list.

 Method 4: use the heapq module’s heapify() and heappop() functions.

This method uses the heapify() function to convert the list into a heap and then repeatedly uses the heappop() function to extract the smallest element from the heap until it’s empty. This ensures that the resulting list is sorted based on the second element of each sublist.

1. Import the heapq module which provides heap-based operations like heapify, heappop, etc.
2. Initialize a list of lists called test_list with the values [[‘Rash’, 4, 28], [‘Varsha’, 2, 20], [‘Nikhil’, 1, 20], [‘Akshat’, 3, 21]].
3. Print the original list test_list with a message saying “The original list is : “.
4. Use the heapify function from heapq to convert test_list into a min-heap based on the second element of each sublist.
5. Create an empty list called result_list.
6. While test_list is not empty, do the following:
   a. Use the heappop function from heapq to remove and return the smallest element from test_list.
   b. Append the element returned in the previous step to result_list.
7. Print the result list result_list with a message saying “List after sorting by 2nd element of lists : “.

The original list is : [['Rash', 4, 28], ['Varsha', 2, 20], ['Nikhil', 1, 20], ['Akshat', 3, 21]]
List after sorting by 2nd element of lists : [['Akshat', 3, 21], ['Nikhil', 1, 20], ['Rash', 4, 28], ['Varsha', 2, 20]]

Time complexity O(n), where n is the length of the input list. This operation rearranges the elements in the list to satisfy the heap property”
Auxiliary space: O(1) 

 Method 5:  Using a custom function

The below implementation uses a function sort_list_of_lists that takes a list of lists lst and an index index. The function uses the sorted function to sort the list based on the specified index, using a lambda function as the key function. Then call this function on the test_list and the second index (1) to get the sorted list.

List after sorting by 2nd element of lists : [['Nikhil', 1, 20], ['Varsha', 2, 20], ['Akshat', 3, 21], ['Rash', 4, 28]]

Time complexity: O(n log n), where n is the length of the list of lists lst. 
Auxiliary space: O(n), where n is the length of the list of lists lst.

Method 6 : using the numpy library. 

Here is the step-by-step approach using numpy:

1. Import numpy library.
2. Convert the list of lists to a numpy array using the numpy.array() method.
3. Use the numpy.argsort() method to get the indices that would sort the array based on the specified index.
4. Use the indices obtained from step 3 to sort the array using the numpy.take() method.
5. Convert the sorted numpy array back to a list of lists using the numpy.ndarray.tolist() method.

OUTPUT: 

List after sorting by 2nd element of lists : [['Nikhil', '1', '20'], ['Varsha', '2', '20'], ['Akshat', '3', '21'], ['Rash', '4', '28']]

Time complexity: The numpy.argsort() method has a time complexity of O(n log n), where n is the number of elements in the array. The numpy.take() method also has a time complexity of O(n log n). Therefore, the time complexity of this method is O(n log n).

Auxiliary space: The numpy.array() method and numpy.argsort() method both create new arrays, which require additional memory. Therefore, the auxiliary space complexity of this method is O(n).