Sort string in C++
Written by
Organizing or arranging a group of characters in a definite order i.e, ascending or descending based on their ASCII values is known as sorting a string. The output of a sorting program produces a reordered input or its permutation.
For instance,
Input: orange,
Output: aegnor,
another example:
Input: aPPLE,
Output: ELPPa
Here, the output has ‘a’ in the end as its ASCII value is greater than that of the others.
Hence, to sort a string in alphabetical order, make sure that all characters entered are either uppercase or lowercase letters entirely.
As we know, strings are defined as a one-dimensional array of characters in C++ and are used to store text in general. Remember, that the text stored in a variable belonging to the string data type must be enclosed within double quotes “ “
For example: string a[ ] = “ Welcome to StudyMite!” ;
Each character of a string has an ASCII ( American Standard Code for Information Interchange) value which basically encodes characters into an integer ranging from 0 to 127. Example: ASCII value of A is 65, and of small A is 97. You can display the ASCII value of a character by typecasting the character variable to int data type.
Methods to sort a string
Using sorting techniques
There are several sorting techniques one can use to arrange a string in a definite order. Some of them are:
By Bubble Sort:
The simplest sorting algorithm, the bubble sort, compares each pair of adjacent characters and swaps them if they are in the incorrect order until the entire string is sorted. Basically, it pushes the character with the greater ASCII value to the end of the list.
Algorithm:
Step 1: Input a string.
Step 2: Declare a temporary variable for swapping the characters
Step 3: Use a nested for loop to compare the characters and traverse through the string
Step 4: If a variable ‘j’ represents the character in question then if the ASCII value of j is greater than that of j+1, then the characters are swapped using the temporary variable.
Step 5: Continue swapping until both the iterations are complete and the outer loop’s condition evaluates to false. Hence, the string is sorted.
Implementation:
#include <iostream>
#include <string> //To avail string functions
using namespace std;
int main(){
string str;
char temp;
cout << "Enter the string to be sorted: ";
getline(cin, str);
int len = str.length();
cout << "\n String before sorting: " << str << " \n";
for (int i = 0; i < len; i++){
for (int j = 0; j < len - 1; j++){
if (str[j] > str[j + 1]){ //if j has larger ascii value than the next,
//swapping the prev and next characters
temp = str[j];
str[j] = str[j + 1];
str[j + 1] = temp;
}
}
}
cout << "\n String after sorting: " << str << " \n";
return 0;
}
Output:
Case 1:
Enter the string to be sorted: Alphabet
String before sorting: Alphabet
String after sorting: Aabehlpt
Case 2: A string of words:
Enter the string to be sorted: a good coder
String before sorting: a good coder
String after sorting: acddegooor
By Insertion Sort:
This simple sort algorithm picks the characters one by one and places them in the right position. In this algorithm, each iteration removes a character from the input list and places it in the sorted sub-string.
While sorting alphabetically, the algorithm takes the character and places it in the correct position based on the ASCII value.
Algorithm:
Step 1: Input a string.
Step 2: Use a for loop to traverse through the string.
Step 3: Consider the first element to be a sorted sublist.
Step 4: Compare each element with the elements of the sorted sublist
Step 5: Shift all the greater elements to the right.
Step 6: Follow step 4-5 until the end of the string to obtain a sorted one.
Implementation:
#include <iostream>
#include <string>
using namespace std;
int main(){
string str;
cout << "Enter the string to be sorted: ";
getline(cin, str);
int len = str.length();
cout << "\n String before sorting: " << str << " \n";
for (int i = 1; i < len; i++){
char temp = str[i];
// Insert s[j] at its correct position
int j = i - 1;
while (j >= 0 && str[j] > temp){
str[j + 1] = str[j];
j--;
}
str[j + 1] = temp;
}
cout << "\n String after sorting: " << str << " \n";
return 0;
}
Output:
Enter the string to be sorted: seven seas
String before sorting: seven seas
String after sorting: aeeensssv
By Quick Sort:
Similar to merge sort, quick sort has a recursive algorithm that uses the divide and conquer technique to arrange the elements in a certain order.
The algorithm does not use extra storage for the sublists and instead uses the technique to split the same list into two with the assistance of the pivot value which is considered to be the first element ideally. However, any element can be chosen.
The partition point is then used to divide the list for subsequent calls to the quick sort.
Algorithm:
Step 1: Input a string.
Step 2: Declare the pivot variable and assign it to the middlemost character of the string.
Step 3: Declare two variables low and high as the lower and upper bounds of the string respectively.
Step 4: Begin the partitioning process using the while loop and swapping elements to split the list into two parts- one with characters larger than the pivot element and the other, smaller.
Step 5: Recursively repeat the algorithm for both halves of the original string to obtain the sorted string.
Implementation:
#include <stdio.h>
#include <string>
#include <iostream>
using namespace std;
void quickSort(std::string &str, int lb, int ub) {
int low = lb, high = ub;
int pivot = str[(low + high) / 2];
/* partition */
do {
while (str[low] < pivot) low++;
while (str[high] > pivot) high--;
if (low <= high) {
std::swap(str[low], str[high]);
low++; high--;
}
}while (low <= high);
/* recursion */
if (lb < high) quickSort(str, lb, high);
if (low < ub) quickSort(str, low, ub);
}
int main(){
std::string str;
cout<<"Enter a string : ";
cin >> str;
quickSort(str, 0, str.size()-1);
cout << "The resultant string is: "<<str;
}
Output:
Enter a string: Atmosphere
The resultant string is: Aeehmoprst
Note: The quick sort and merge sort algorithms can only sort non-spaced strings.
Hence, use the bubble, insertion sort algorithms to sort sentences. Or, you can try the next method:
Using Library Function:
You can use the sort function from the Standard template library of C++ by including the
Syntax: sort(first iterator, last iterator),
where the first and last iterators are the starting and ending index of the string respectively.
Using this in-built function is fairly easier and faster to perform as compared to writing your own code.
However, since the provided sort( ) function also uses the quick sort algorithm to sort the string, only non-spaced strings can be sorted using this function.
Implementation:
#include <iostream>
#include<algorithm>
using namespace std;
int main(){
string s;
cout << "Enter a string: ";
cin >> s;
sort(s.begin(), s.end()); // sort function included in <algorithm>
cout << "The sorted string is: " << s;
return 0;
}
Output:
Enter a string: August
The sorted string is: Agstuu
If we input a string containing a set of words, look what happens:
Enter a string: second august
The sorted string is: cdenos
As you can see, the program only sorts the first word and ends execution once a ‘null’ character is encountered, hence leaving the second word entirely. Simply put, the quicksort algorithm does not sort a string of words in alphabetical order.
So, above were some methods to sort a string in alphabetical order. Note that you can always create your own functions to carry out operations but a thorough and strong understanding of the basic sorting algorithms can elevate your code to the next level in terms of optimization.
