Computers process strings in character-level operations and store them in memory, so any sorting algorithm must consider the flow of bytes within the string, as well as their numerical or alphabetical relations. This article will cover the steps to implement the most common sorting algorithms for C++ strings.
Sorting Characters of a C++ String
There are five methods to sort a string as given:
1: Selection Sort
Selection sort is a comparison-based sorting algorithm that works by dividing the input into two parts: a sublist of sorted characters and a sublist of unsorted characters. The algorithm then searches the unsorted sublist for the smallest element and places the smallest element in the sublist of sorted characters. It continues this process until the entire string is sorted.
To implement selection sort in C++ we will use the following steps.
Step 1: Create a for loop starting with character index i equal to 0. The loop will iterate through the string once.
Step 2: Set the minimum index to i.
Step 3: Create a nested for loop starting with character index j equal to i+1. The loop will iterate through the remaining characters in the string.
Step 4: Compare the character at index i with the character at index j. If the character at index j is less than the character at index i, we set the minimum index to j.
Step 5: After the nested for loop, we swap the character at minimum index with the character at index i.
Step 6: Repeat Steps 1-5 until we reach the end of the string.
The program for selection sort is given below:
#include <string>
using namespace std;
void selectionSort(string& s) {
int len = s.length();
for (int i = 0; i< len-1; i++) {
int minIndex = i;
for (int j = i+1; j <len; j++) {
if (s[j] < s[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
swap(s[i], s[minIndex]);
}
}
}
int main() {
string str = "this is a sorting algorithm";
cout<< "Original string was: " << str <<endl;
selectionSort(str);
cout<< "Sorted string is: " << str <<endl;
return 0;
}
In the above code, a string reference is sent into the selectionSort function, which sorts the string in-place. By iterating over the string from the current position to the end, the function first identifies the least element in the unsorted portion of the string. The element at the present place in the string is switched out for the minimal element after it has been determined. This procedure is repeated for each element of the string in the function’s outer loop until the entire string is arranged in non-decreasing order.
Output
2: Insertion Sort
Insertion sort is another comparison-based sorting algorithm and works by dividing the input into sorted and unsorted parts. The algorithm then iterates through the unsorted part of the input and adds the element into its correct position while shifting the larger elements towards the right. To do this, the following steps should be followed:
Step 1: Create a for loop starting with character index i equal to 1. The loop will iterate through the string once.
Step 2: Set the variable key equal to the character at index i.
Step 3: Create a nested while loop starting with character index j equal to i-1. The loop will iterate through the sorted part of the string.
Step 4: Compare the character at index j with the variable key. If the variable key is less than the character at index j, we swap the character at index j with the character at index j+1. Then, set the variable j equal to j-1.
Step 5: Repeat step 4 until j is greater than or equal to 0 or the variable key is greater than or equal to the character at index j.
Step 6: Repeat Steps 1-5 until we reach the end of the string.
#include <iostream>
using namespace std;
int main(){
string str;
cout<< "Original string was: " ;
getline(cin, str);
int length = str.length();
for (int i = 1; i= 0 && str[j] >temp){
str[j + 1] = str[j];
j--;
}
str[j + 1] = temp;
}
cout<< "\nSorted string is: " << str << " \n";
return 0;
}
We are splitting the array into sorted and unsorted sublists in this piece of code. The values in the unsorted component are then compared, and they are sorted before being added to the sorted sublist. The sorted array's initial member will be regarded as a sorted sublist. We compare every element in the unsorted sublist to every element in the sorted sublist. Then, all the larger components are moved to the right.
Output
3: Bubble Sort
Another straightforward sorting technique is the bubble sort, which continually switches nearby elements if they are in the wrong order. Nevertheless, you must first comprehend what bubble sort is and how it functions. When the following string is smaller (a[i] > a[i+1]), the neighboring strings (a[i] and a[i+1]) are switched in the bubble sort process. To sort a string using bubble sort in C++, follow these steps:
Step 1: Request user input for an array.
Step 2: Change the names of the strings using ‘strcpy’.
Step 3: A nested for loop is used to walk over and compare two strings.
Step 4: The values are switched if the ASCII value of y is larger than y+1 (the letters, digits, and characters allocated to the 8-bit codes).
Step 5: The swapping continues until the condition returns false.
The swapping continues in Step 5 until the condition returns false.
#include<string.h>
using namespace std;
int main() {
char Str[10][15], arr[10];
int x, y;
cout<< "Enter Strings: ";
for (x = 0; x > Str[x];
}
for (x = 1; x < 6; x++) {
for (y = 1; y 0) {
strcpy(arr, Str[y - 1]);
strcpy(Str[y - 1], Str[y]);
strcpy(Str[y], arr);
}
}
}
cout<< "\nAlphabetical order of Strings :\n";
for (x = 0; x < 6; x++)
cout<< Str[x] <<endl;
cout<<endl;
return 0;
}
The above Bubble Sort program we’ll utilize a character array that can hold 6 character strings as user input. The “strcpy” function has been used where the names of the strings are swapped in a nested function. In the if statement, two strings are compared using the “strcmp” function. And once all the strings are compared, the output is printed on the screen.
Output
4: Quick Sort
The divide and conquer method is used by quick sort’s recursive algorithm to arrange the items in a certain order. The method employs the approach to divide the same list into two with the help of the pivot value, which is thought to be the first member ideally, rather than using additional storage for the sublists. Any element can be picked, though. After calls to the quick sort, the list is divided using the partition point.
Step 1: First, enter a string.
Step 2: Declare the pivot variable and assign it to the string’s middle character.
Step 3: Establish the lower and higher boundaries of the string as the two variables low and high, respectively.
Step 4: Start splitting the list into two groups, one with characters larger than the pivot element and the other with smaller characters, by using a while loop and element swapping.
Step 5: Recursively run the algorithm on the original string’s two halves to create the sorted string.
#include <string>
#include <iostream>
using namespace std;
void quickSort(std::string & str, int s, int e) {
int st = s, end = e;
int pivot = str[(st + end) / 2];
do {
while (str[st] pivot)
end--;
if (st<= end) {
std::swap(str[st], str[end]);
st++;
end--;
}
} while (st<= end);
if (s < end) {
quickSort(str, s, end);
}
if (st< e) {
quickSort(str, st, e);
}
}
int main() {
std::string str;
cout<>str;
quickSort(str, 0, (int)str.size() - 1);
cout<< "The sorted string: " <<str;
}
In this code, we are declaring the start and end positions of two variables under ‘start’ and ‘end’ that will be declared relative to the character string. The array will be split in half in the quickSort() function, then using a do-while loop, the items will be switched, and the procedure will be repeated until the string is sorted. The quickSort() function will then be called from the main() function and the string entered by the user will be sorted and the output will be printed on the screen.
Output
5: C++ Library Function
The sort() function is accessible in C++ thanks to the built-in library function algorithm. We’ll make an array of name strings and use the built-in sort() method, which will sort the strings using the array’s name and size as arguments. The syntax of this function is:
where the string’s beginning and ending indices are, respectively, the first and last iterators.
Comparatively speaking, using this built-in function is quicker and easier to complete than developing your own code. Only non-spaced strings may be sorted using the sort() method as it also employs the quick sort algorithm to do so.
#include<algorithm>
using namespace std;
int main(){
string str;
cout<>str;
sort(str.begin(), str.end());
cout<< "The sorted string is: " <<str;
return 0;
}
In this code, we will first enter a string by the user, and then the string will be sorted using the sort() method and then printed on the screen.
Output
Conclusion
When sorting a character in a C++ string, the programmer must consider the type of sort algorithm appropriate to the task, as well as the size of the string. Depending on the size of the string, insertion, bubble, selection sort, quick sort or sort() function can be used to sort characters. It’s depends on the user’s choice, which method they want to choose.
