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.
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"
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.
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
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; }
The sorted string as per ASCII values of the characters is: $%()7jkw
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.
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.
#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; }
The sorted string as per ASCII values of the characters is: $%()7jkw
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 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!