Sort string of characters
Last Updated :
29 Feb, 2024
Given a string of lowercase characters from ‘a’ – ‘z’. We need to write a program to print the characters of this string in sorted order.
Examples:
Input : bbccdefbbaa
Output : aabbbbccdef
Input : geeksforgeeks
Output : eeeefggkkorss
A simple approach will be to use sorting algorithms like quick sort or merge sort and sort the input string and print it.
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
void sortString(string &str)
{
sort(str.begin(), str.end());
cout << str;
}
int main()
{
string s = "geeksforgeeks";
sortString(s);
return 0;
}
|
C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compare(const void *a, const void *b)
{
return (*(char *)a - *(char *)b);
}
void sortString(char *str)
{
int n = strlen(str);
qsort(str, n, sizeof(char), compare);
printf("%s", str);
}
int main()
{
char s[] = "geeksforgeeks";
sortString(s);
return 0;
}
|
Java
import java.util.Arrays;
class GFG {
static void sortString(String str) {
char []arr = str.toCharArray();
Arrays.sort(arr);
System.out.print(String.valueOf(arr));
}
public static void main(String[] args) {
String s = "geeksforgeeks";
sortString(s);
}
}
|
C#
using System;
public class GFG {
static void sortString(String str) {
char []arr = str.ToCharArray();
Array.Sort(arr);
Console.WriteLine(String.Join("",arr));
}
public static void Main() {
String s = "geeksforgeeks";
sortString(s);
}
}
|
Javascript
<script>
let MAX_CHAR = 26;
function sortString(str)
{
let charCount = new Array(MAX_CHAR);
charCount.fill(0);
for (let i = 0; i < str.length; i++)
charCount[str[i].charCodeAt()-'a'.charCodeAt()]++;
for (let i=0;i<MAX_CHAR;i++)
for (let j=0;j<charCount[i];j++)
document.write(String.fromCharCode('a'.charCodeAt()+i) );
}
let s = "geeksforgeeks";
sortString(s);
</script>
|
Python3
def sortString(str) :
str = ''.join(sorted(str))
print(str)
s = "geeksforgeeks"
sortString(s)
|
Time Complexity: O(n log n), where n is the length of string.
Auxiliary Space: O( 1 ).
An efficient approach will be to observe first that there can be a total of 26 unique characters only. So, we can store the count of occurrences of all the characters from ‘a’ to ‘z’ in a hashed array. The first index of the hashed array will represent character ‘a’, second will represent ‘b’ and so on. Finally, we will simply traverse the hashed array and print the characters from ‘a’ to ‘z’ the number of times they occurred in input string.
Below is the implementation of above idea:
Implementation:
C++
#include<bits/stdc++.h>
using namespace std;
const int MAX_CHAR = 26;
void sortString(string &str)
{
int charCount[MAX_CHAR] = {0};
for (int i=0; i<str.length(); i++)
charCount[str[i]-'a']++;
for (int i=0;i<MAX_CHAR;i++)
for (int j=0;j<charCount[i];j++)
cout << (char)('a'+i);
}
int main()
{
string s = "geeksforgeeks";
sortString(s);
return 0;
}
|
C
#include <stdio.h>
#include <string.h>
void swap(char* a, char* b)
{
char temp = *a;
*a = *b;
*b = temp;
}
int partition(char* str, int low, int high)
{
char pivot = str[high];
int i = low - 1;
for (int j = low; j <= high - 1; j++) {
if (str[j] <= pivot) {
i++;
swap(&str[i], &str[j]);
}
}
swap(&str[i + 1],
&str[high]);
return i + 1;
}
void quickSort(char* str, int low, int high)
{
if (low < high) {
int pivotIndex = partition(
str, low, high);
quickSort(str, low,
pivotIndex
- 1);
quickSort(str, pivotIndex + 1,
high);
}
}
int main()
{
char str[] = "geeksforgeeks";
int n = strlen(str);
quickSort(str, 0, n - 1);
printf("Sorted string: %s\n", str);
return 0;
}
|
Java
public class SortString{
static final int MAX_CHAR = 26;
static void sortString(String str) {
int letters[] = new int[MAX_CHAR];
for (char x : str.toCharArray()) {
letters[x - 'a']++;
}
for (int i = 0; i < MAX_CHAR; i++) {
for (int j = 0; j < letters[i]; j++) {
System.out.print((char) (i + 'a'));
}
}
}
public static void main(String[] args) {
sortString("geeksforgeeks");
}
}
|
C#
using System;
class GFG
{
public static string sortString(string inputString)
{
char[] tempArray = inputString.ToCharArray();
Array.Sort(tempArray);
return new string(tempArray);
}
public static void Main(string[] args)
{
string inputString = "geeksforgeeks";
Console.WriteLine(sortString(inputString));
}
}
|
Javascript
<script>
let MAX_CHAR = 26;
function sortString(str)
{
let letters=new Array(MAX_CHAR);
for(let i=0;i<MAX_CHAR;i++)
{
letters[i]=0;
}
for(let x=0;x<str.length;x++)
{
letters[str[x].charCodeAt(0) - 'a'.charCodeAt(0)]++;
}
for (let i = 0; i < MAX_CHAR; i++) {
for (let j = 0; j < letters[i]; j++) {
document.write(String.fromCharCode
(i + 'a'.charCodeAt(0)));
}
}
}
sortString("geeksforgeeks");
</script>
|
Python3
MAX_CHAR = 26
def sortString(str):
charCount = [0 for i in range(MAX_CHAR)]
for i in range(0, len(str), 1):
charCount[ord(str[i]) - ord('a')] += 1
for i in range(0, MAX_CHAR, 1):
for j in range(0, charCount[i], 1):
print(chr(ord('a') + i), end = "")
if __name__ == '__main__':
s = "geeksforgeeks"
sortString(s)
|
Time Complexity: O(Max_CHAR*n) which becomes O(n) as MAX_CHAR is constant,So Overall Time Complexity:- O(n) where n is the length of the string.
Auxiliary Space: O( 1 ).
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...