Python program to sort strings by substring range

Given a String List, sort by a range of substrings.

Input : test_list = [“neveropen”, “best”, “neveropen”, “preparation”, “interview”], i, j = 1, 3 
Output : [‘neveropen’, ‘neveropen’, ‘best’, ‘interview’, ‘preparation’]

Explanation : “eek” < “eek” < “est” < “nte” < “rep”.

Input : test_list = [“apple”, “orange”, “banana”], i, j = 2, 4 
Output : [‘orange’, ‘banana’, ‘apple’] 

Explanation : “ang” < “nan” < “ple”. 

Method #1 : Using sort() + slicing

In this, we perform the task of sorting using sort() and the task of extracting a range is done using slicing.

The original list is : ['neveropen', 'best', 'neveropen', 'preparation']
Strings after sorting : ['neveropen', 'neveropen', 'best', 'preparation']

Time Complexity: O(nlogn)

Auxiliary Space: O(n)

Method #2 : Using lambda function + sort() + slicing

In this, we perform slicing using lambda function rather than calling external function.

The original list is : ['neveropen', 'best', 'neveropen', 'preparation']
Strings after sorting : ['neveropen', 'neveropen', 'best', 'preparation']

Time Complexity: O(nlogn)

Auxiliary Space: O(n)

Method #3:  Using the functools.cmp_to_key() function and sorted()

Step-by-step algorithm:

1. Import the cmp_to_key function from the functools module.
2. Create a list of strings test_list.
3. Initialize i and j to 1 and 3 respectively.
4. Define a comparison function cmp that takes two strings a and b as input and compares the substring of a and b from index i to index j. If the substring of a is less than the substring of b, return -1. If the substring of a is greater than the substring of b, return 1. Otherwise, return 0.
5. Sort the list test_list using the sorted() function and the key argument set to cmp_to_key(cmp).
6. Print the sorted list.

The original list is : ['neveropen', 'best', 'neveropen', 'preparation']
['neveropen', 'neveropen', 'best', 'preparation']

Time complexity: O(n log n), where n is the length of the list test_list. This is because sorting using the sorted() function takes O(n log n) time.

Auxiliary Space: O(n), where n is the length of the list test_list. This is because we are creating a new list to store the sorted version of the input list.

Method #4:Using itemgetter() from operator module

• Importing the operator module to use itemgetter() function for sorting by substring range.
• Initializing a list test_list containing strings.
• Printing the original list.
• Initializing the range (start, end) for the substring.
• Sorting the list using the sorted() function and itemgetter() function from the operator module.
• The key argument takes operator.itemgetter(i, j) as a parameter. It sorts the list based on the substring from index i to index j.
• Printing the sorted list.

The original list is : ['neveropen', 'best', 'neveropen', 'preparation']
Strings after sorting : ['neveropen', 'neveropen', 'best', 'preparation']

Time Complexity: O(n log n), where n is the length of the list test_list.

Auxiliary Space: O(n), where n is the length of the list test_list. 

Method #6: Using list comprehension and sorted()

steps : 

We initialize a list test_list with some strings.
We print the original list test_list.
We initialize two variables i and j to represent the start and end indices of the substring range we want to sort on.
We sort the list test_list using the sorted() function and a lambda function as the key. The lambda function extracts the substring range of each string in the list using the variables i and j. The sorted() function returns a new sorted list.
We update the original list test_list with the sorted list.
We print the updated list test_list.

The original list is : ['neveropen', 'best', 'neveropen', 'preparation']
Strings after sorting : ['neveropen', 'neveropen', 'best', 'preparation']

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

Auxiliary space: O(n), where n is the length of the list.