Sorting has always been quite a popular utility with lots of applications everywhere, where Python language opts. Python in its language offers a sort function to perform this task. But because not all the Python containers are mutable, such as string, the sort function doesn’t work as it is in place trying to sort and immutability stops this. Let’s discuss specific ways in which a string can be sorted.
Example
Input: geekforLazyroar
Output: eeeefggkkors
Explaination:The Sorting the characters in ascending order gives us "eeeefggkkors".
Program to Sort a String in Python
Below are the lists of methods that we will cover:
- Using join() and sorted()
- Using the Native Method
- Using the sorted function with reduce() and lambda
- Using Bubble sort
- Using the merge sort method
- Using a dictionary
Program to sort a string using join() and sorted()
The combination of the above functions can potentially solve this particular problem. This task is performed in 2nd step in which the first step we get the sorted list of characters and then we join the result to get the resultant sorted string.
Python3
test_string = "geekforLazyroar"# printing original stringprint("The original string : " + str(test_string))# using join() + sorted()# Sorting a stringres = ''.join(sorted(test_string)) # print resultprint("String after sorting : " + str(res)) |
The original string : geekforLazyroar String after sorting : eeeefggkkors
Time Complexity: The time complexity of the code is O(n log n).
Space Complexity: The space complexity of the given code is O(n).
Sort a Python String using the Native Method
To sort a given string with user input using the inbuilt Python sort method.
Python3
String = "geekforLazyroar"print('Original String: ', String)lst = list(String)lst.sort()print('Sorted String: ')for i in lst: print(i, end = "") |
Output:
Original String: geekforLazyroar
Sorted String:
eeeefggkkors
Time Complexity: The time complexity of the code is O(n log n).
Space Complexity: The space complexity of the given code is O(n).
Sort a Python String using reduce() and lambda
This particular task can also be performed using a combination of the above functions. Here we join the resultant sorted list of characters using the lambda function joined by the reduce function. Works only for Python2
Python
test_string = "geekforLazyroar"# printing original stringprint("The original string : " + str(test_string))# using sorted() + reduce() + lambdares = reduce(lambda x, y: x + y, sorted(test_string)) # print resultprint("String after sorting : " + str(res)) |
The original string : geekforLazyroar String after sorting : eeeefggkkors
Time Complexity: The time complexity of the code is O(n log n).
Space Complexity: The space complexity of the given code is O(n).
Sort a string in Python using Bubble Sort
Convert the string into a list of characters then use the bubble sort algorithm to sort the list now join the sorted list to form a string.
Python3
def sort_string(s): chars = list(s) n = len(chars) for i in range(n): for j in range(0, n-i-1): if chars[j] > chars[j+1]: chars[j], chars[j+1] = chars[j+1], chars[j] return ''.join(chars)s = "geekforLazyroar"print("Original string:", s)print("String after sorting:", sort_string(s)) |
Original string: geekforLazyroar String after sorting: eeeefggkkors
Time complexity: O(n^2) because we use the bubble sort algorithm which has a time complexity of O(n^2).
Auxiliary Space: O(n) because we create a new list of characters from the original string.
Program to sort a string using the Merge Sort
This approach uses the merge sort algorithm to sort the characters in the string. It first converts the string into a list of characters, and then recursively divides the list in half until the base case of a single element is reached. The two halves are then merged back together in sorted order using the merge() function. The sorted list is then converted back into a string.
Python3
# Define a function called "merge_sort"def merge_sort(s): if len(s) <= 1: return s # find the middle index of the string "s" mid = len(s) // 2 # split the string into two halves, left and right left = merge_sort(s[:mid]) right = merge_sort(s[mid:]) #Recursively apply the merge_sort function on the left and right halves. return merge(left, right) # Merge the left and right halves using the merge function.def merge(left, right):#Initialize an empty list called "result" and two indices, "i" and "j", both set to 0. result = [] i = j = 0 while i < len(left) and j < len(right): if left[i] < right[j]: result.append(left[i]) #Increment the index of the array i += 1 else: result.append(right[j]) #Increment the index of the array j += 1 result += left[i:] result += right[j:] return results = 'geekforLazyroar'#Convert the sorted list to a string and print the result.sorted_s = ''.join(merge_sort(list(s)))print("String after sorting:", sorted_s) |
String after sorting: eeeefggkkors
Time Complexity: O(n log n) where n is the length of the input string “s”.
Space Complexity: O(n) where n is the length of the input string “s”.
Sort a String in a Python Program using a Dictionary
This program sorts a given input string in ascending order based on the characters present in it. It uses a dictionary to count the frequency of each character and then sorts them based on the ASCII value of the character.
Python3
input_string = "geekforLazyroar"#Initialize an empty dictionary to store the countchar_count = {}#Loop through each character in the input string and update the count of that characterfor char in input_string: if char in char_count: char_count[char] += 1 else: char_count[char] = 1 #Create an empty string to store the sorted string.sorted_string = ""#Loop through each character in the sorted list of keys of the dictionary#Add that character multiplied by its count in the input string to the sorted string.for char in sorted(char_count.keys()): sorted_string += char * char_count[char]#Print the original string and the sorted string.print("Original string: {}".format(input_string))print("String after sorting: {}".format(sorted_string)) |
Original string: geekforLazyroar String after sorting: eeeefggkkors
Time Complexity: The time complexity of this algorithm is O(nlogn) due to the use of the sorted() function.
Space Complexity: The space complexity of this algorithm is O(n) due to the use of the dictionary to store the count of each character.
