Sort a String in Python

Introduction

Sorting a string in Python is the process of placing a group of characters in a particular order, that can be ascending or descending based on their ASCII values.

The result we get after sorting a string is in a definite order.

Above given is an example of sorting a string. When we sort the string, they are arranged in an alphabetical order, which our python code decides on the basis of their ASCII values. The character which comes first in alphabetical order has a smaller ASCII value than the character that comes later and vice versa.

After having learned about what is sorting in Python, let's see the various ways to sort a string in Python.

Using Python Inbuilt Sorted() and Join() Method

The sorted() function in Python returns a "sorted list" of the given iterable (list,tuple,set,etc.) object. We can also specify ascending or descending order in our function.

The join() method takes all items in an iterable (list,tuple,set,etc.) and joins them into one string. It joins the string on the basis of the separator provided. Separator means the value which will be used to join the string, suppose a space(" "), or a dash("-"), etc. Based on the separator provided, our join method joins the string with it.

Hence, we can use the combination of sorted() and join() method to sort our string. The sorted() will return a sorted list, and the join() will join the sorted list into a string.

Code:

Output:

Explanation:

• We pass our string to sorted() and it returns a sorted list of characters. We store the result in our variable ls.
• We finally pass our list to join() method and join it using the separator ''. Finally, we return our answer.

Time Complexity: $O(nLogn)$

• Since we are using sorted() function, which in the worst case takes $O(nLogn)$ to sort, the time complexity becomes $O(nLogn)$.

Space Complexity: $O(1)$

• In the above code we are using a list to store the sorted list result, so the space complexity is O(N), where N is the length of the list. However, in the best case we may avoid assigning it to a list and directly pass the sorted result to join. In that case our Space Complexity will be O(1).

Using Sorted() + Reduce() + lambda

The reduce(fun,seq) function is used to apply a particular function passed in its argument to all of the list elements mentioned in the sequence passed to it. This function is defined in functools module.

In Python, anonymous functions(functions without name) are defined using the lambda keyword. Lambda functions can have any number of arguments but only one expression. The expression is evaluated and returned.

Now, let us see how can we use sorted() + reduce() + lambda to sort our string in Python.

Code:

Output:

Explanation:

• First we sort our string using sorted and store its result in 's'.
• lambda x, y: x + y concatenates the list. The reduce method applies this lambda function to all the elements of the list.
• Here we join the resultant sorted list of characters using the lambda function and the reduce() function.

Using While loop in Python

We can also use the regular while loop method to sort our string in Python. However, it is not at all a suggested method. You can just understand this for the sake of knowledge.

Code:

Output:

Explanation:

• We pass our list of string to our sort_string method. Here, we loop over our list and append the minimum string according to the ASCII value of the first and leading characters of the string.
• Once we append that string to our list, we remove that string from our original string provided.
• Finally we return our list once it exits the while loop.

Time Complexity: $O(n^2)$

• The while loop would iterate over all the list elements hence take a complexity of $O(N)$, for list of size N. The min and max operations almost takes constant time for a list of constant size.

Space Complexity: $O(n)$

• The space complexity for the above code is $O(n)$. Because we are using a list of length 'n' to store our result and for computation.

Using For loop in Python(Bubble Sort)

We can use bubble sort to sort our string in Python. Let us see the code for how it works.

Code:

Output:

Explanation:

• First, i iterates through the length of the string, and j iterates through (length - i), because with every pass, the largest string will find it's position.
• Whenever we encounter a larger character in a string than the string after it, we simply swap them.
• Finally we return our sorted string.

Time Complexity: $O(n^2)$

• Since bubble sort uses $O(n^2)$ to sort any iterable, it's worst case time complexity will be $O(n^2)$. The best and average case for bubble sort is also $O(n^2)$.

Space Complexity: $O(1)$

• Since bubble sort uses constant space the Space Complexity would be $O(1)$. Also, we are not using any other data structure to perform our operation.

Read More:

• Python Strings.
• Selection sort in Python.
• Sort Array in Python.
• Sort Dictionary by Key in Python.
• Sort Dictionary by Value in Python.