String

Sorting

Sorting character array/string using an integer array

You can use sort methods provided by the language or library but those will always be O(nlogn) time complexity.

Which may be fine for other kinds of sorting where you don't have much option, like in case of numbers. But characters are special. They are limited and can be represented by numbers, which provide us the ability to represent a character array by an integer array of limited length. This can in turn be used to sort the string or character array.

public String sortString(String str){
	int[] alpha = new int[26];
	String sorted = new String();
	
	System.out.println(str);

	for(char c: str.toCharArray()){
		int index = c - 'a';
		alpha[index]++;
	}

	for(int i=0; i<26; i++){
		while(alpha[i] > 0){
			int asc = alpha[i];
			char c = (char) (i+ 'a');
			sorted+=(c);
			alpha[i]--;
		}
	}
	
	return sorted;
}

The array size here is kept just for small case alphabets. You can increase the size depending upon the range of characters you want to consider.

• All characters in original ASCII: 128
• All characters in extended ASCII (includes some basic graphics/emojis): 256