Input: BDCAbaxz
OUTPUT: AaBbCDxz
My solution is straight forward and ugly:
Sort the input with quick sort, then we get "ABCDabxz"
Alloc a temp array with the same size as the original one, then take the appropriate element from two sub-array(ptr1-->A, ptr2--->a)
Copy the temp array back to the original one
Any faster algorithm on this problem?
Yes.
Define a comparator for qsort that gives you the ordering you want in the first place (so rather than using AB...YZab...yz as the sort order, have it enforce AaBb...YyZz).
stricmp sorts strings, not characters. And it considers 'A' and 'a' as identical, which wouldn't give the OP the desired behaviour.
If the input is long ( >> 255) you could make a counting sort.
char chars[256]; zeroed
while( *input) // zero termination
chars[*input++]++;
And extract it like
int pos = 0;
for(int i = 'A'; i<= 'Z'; i++)
{
while( chars[i]-- )
output(pos++] = (char)i;
while( chars[i+'a'-'A']-- )
output(pos++] = (char)i+'a'-'A';
}
O(N)
