Sort strings by character's ASCII value

ASCII value

ASCII (American Standard Code for Information Interchange) is the most common character encoding format for text data on computers and the Internet. In standard ASCII encoded data, 256 letters, numbers, or special additional characters and control codes have unique values.

Problem Statement

Now, in this problem, we need to find the sorted string in ascending order based on the ASCII value of the characters, where the string will be the input given to us by the user. Let's see how we should solve this problem.

Let us try to understand this problem with the help of some examples.

Input - s = "$%7wjk()"

Output - "$%()7jkw"

Description - The ASCII values ​​of the characters of the given string are as follows -

$ -> 36
% -> 37
( -> 40
) -> 41
7 -> 55
j -> 106
k -> 107
w -> 119

Thus, in increasing order of ASCII code values, the string will become "$%()7jkw"

Input - s = "#m 0f )nk"

Output - "#)0fkmn"

Description - The ASCII values ​​of the characters of the given string are as follows -

(space) -> 32
# -> 35
) -> 41
0 -> 48
f -> 102
k -> 107
m -> 109
n -> 110

Thus, in increasing order of ASCII code values, the string will become "#)0fkmn"

Explanation of the problem

Let's try to understand the problem and find a solution. We know that there are 256 characters in the ASCII table, where each character has a unique value or position. So our basic goal is to sort the characters accordingly. We can use the built-in sorting function by using external functions that can be used to achieve our goal. Another approach is to create a frequency vector and store the frequency of each character in that array. Using this frequency vector and the ASCII value, we can get the new string.

Solution 1 Use frequency vector

algorithm

• Create a frequency vector of size 256 because the total number of characters in the ASCII table is 256 and start the entire vector with zero

• Run a loop to store the frequency of each character of a given string

• Now define an output string that is initially empty

• Run another loop to iterate over the frequency vector, so we can get the output string by type casting the i-th position Frequency_vector[i]

• Return the output string as the final result

Example

The following is the C program implementation of the above method:

#include <bits/stdc++.h>
using namespace std;
// Function to Sort the string as per ASCII values of the characters
string Helper(string s){
    // Define the size of the given string
	int size = s.length();
	// Define a frequency vector of size 256, which is the same as the size of the characters as per the ASCII table, and initiate the value of the vector as 0
	vector<int> v(256, 0);
	// Run a loop to count the frequency of each character of the string
	for (int i = 0; i < size; i++) {
		v[s[i]]++;
	}	
	// Declare a string, initially empty, to find the final output
	string ans = "";
	// Run another loop to get the final output in accordance with the ASCII table
	for (int i = 0; i < 256; i++) {
		for (int j = 0; j < v[i]; j++)
		// Typecast the integer value to the character value to include it in the loop
			ans = ans + (char)i;
	}
	// Return the final output
	return ans;
}
int main(){
    // Give input as a string by the user
	string s = "$%7wjk()";
	// Call Helper function to perform the remaining tasks
	cout<< "The sorted string as per ASCII values of the characters is: " << Helper(s);
	return 0;
}

Output

The sorted string as per ASCII values of the characters is: $%()7jkw

Complexity of the above code

• Time complexity - O(n); where n is the size of the string. Here, the actual time complexity is O(n * 256), but we can consider it as O(n) because 256 can be considered as a constant like k, while O(k * n) is only considered as O(n ).

• Space complexity - O(256); because the only extra space occupied here is the space of the frequency array, whose size is 256.

Solution 2 Solution using built-in sorting function

algorithm

• Define an external comparison function, used in the sorting function to sort characters according to ASCII values, that is, return characters whose int type conversion value is smaller than other characters.

• Now use the built-in sort function in the helper function and use an extra parameter (comparison function) to get the order correctly.

• Call the helper function and get the final string output.

Example

#include "bits/stdc++.h"
using namespace std;
// Comparison Function to sort the string as per ASCII values of the characters
bool comparison(char ch1, char ch2){ 
    return int(ch1) <= int(ch2);
}
// Function to sort the string as per ASCII values of the characters
string Helper(string s){
	// Sort the string s with the help of the inbuilt function sort()
	sort(s.begin(), s.end(), comparison);
	// Return the final output string s
	return s;
}
int main(){
    // Give input as a string by the user
	string s = "$%7wjk()";
	// Call Helper function to perform the remaining tasks
	cout<< "The sorted string as per ASCII values of the characters is: " << Helper(s);
	return 0;
}

Output

The sorted string as per ASCII values of the characters is: $%()7jkw

Complexity of the above code

• Time complexity: O(log(n)); as we all know, the built-in sorting function requires O(n * log(n)) time to execute the code. In this method we are using the built-in sorting function by using an additional comparison function which will sort the characters based on that function.

• Space complexity: O(1); In the above code, we are not storing any variables in some data structure.

in conclusion

In this article, a sorted string is found in ascending order based on the ASCII value of the characters. We can solve this problem in two ways. First, we can make a frequency vector of size 256 (the same number of characters in the ASCII table) and store all the frequencies of each character, and then iterate from behind to get the desired string. Another way is to use the built-in sort function, with the help of extra parameters passed in the sort function.

The above is the detailed content of Sort strings by character's ASCII value. For more information, please follow other related articles on the PHP Chinese website!