Python | Integrity Sorting in two lists

Often during the problem solving we come across too many problems where we need to sort the list. But sometimes we would also want to sort the another list so that the elements of are automatically shifted and remain at same index as the first list even after first list get sorted. Let’s discuss certain ways in which this can be done. 
Method #1 : Using sorted() + zip() + itemgetter() Combining the three functions we can possibly achieve the task. The zip functions binds the two list together, sorted function sorts the list and itemgetter function is used to define the metrics against which we need second list to shift, in this case first list. 
 

The original list 1 is : [3, 4, 9, 1, 6]
The original list 2 is : [1, 5, 3, 6, 7]
The lists after integrity sort : [[1, 3, 4, 6, 9], [6, 1, 5, 7, 3]]

Time Complexity: O(n*nlogn), where n is the length of the list test_list 
Auxiliary Space: O(n*n) additional space of size n is created where n is the number of elements in the res list 

  Method #2 : Using sorted() + zip() + lambda function This method performs the similar task, each function performing the similar function, the difference is just the instead of itemgetter function, lambda function performs the task of assigning a base to sort the list, i.e the first list in this case. 

The original list 1 is : [3, 4, 9, 1, 6]
The original list 2 is : [1, 5, 3, 6, 7]
The lists after integrity sort : [[1, 3, 4, 6, 9], [6, 1, 5, 7, 3]]

  Method #3 : Using numpy:

1. Initialize two arrays, arr1 and arr2, with the values to be sorted.
2. Use np.argsort() to obtain the sorted indices of the first array, arr1.
3. Use the sorted indices to sort both arrays, arr1 and arr2, based on the values in arr1.
4. Return the sorted arrays, arr1_sorted and arr2_sorted.
5. And here is a brief description of what each line of code in the Python program is doing:
6. Initialize the two arrays, arr1 and arr2.
7. Use np.argsort() to obtain the sorted indices of the first array, arr1.
8. Use the sorted indices to sort both arrays, arr1 and arr2, based on the values in arr1.
9. Print the sorted arrays, arr1_sorted and arr2_sorted.

Output:
The original list 1 is : [3 4 9 1 6]
The original list 2 is : [1 5 3 6 7]
The arrays after integrity sort:
[1 3 4 6 9]
[6 1 5 7 3]

Time complexity:

The np.argsort() function has a time complexity of O(n log n) for an array of n elements.
The array indexing operation arr1[sorted_indices] has a time complexity of O(n).
The overall time complexity of the algorithm is O(n log n).
Auxiliary Space:

The algorithm uses extra memory for the sorted indices, sorted_indices, and the sorted arrays, arr1_sorted and arr2_sorted.
The space complexity is O(n) for these arrays.

manjeet_04

Follow

Improve