Case-specific Sorting of Strings

PROBLEM :

Given a string consisting of uppercase and lowercase characters, you need to sort uppercase and lowercase letters separately such that if the ith place in the original string had an Uppercase character then it should not have a lowercase character after being sorted and vice versa.

Input: The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows.

The first line of each test case contains a single integer N denoting the length of string.

The second line contains a string of length N, consisting of uppercase and lowercase characters.


Output: Print T lines consisting of a sorted strings for the particular test case.

Constraints:
1 = T = 50
1 = N = 1000

Example:

Input:
1
12
defRTSersUXI

Output:
deeIRSfrsTUX
     
--------------------------------------------------------------------------------
SIMPLE c++ IMPLEMENTATION :
--------------------------------------------------------------------------------

#include<iostream>
using namespace std;
#include<malloc.h>
void Case_specific_Sorting(char *,int) ;
void sort(char *,int ) ;
int main()
 {
int t,no ;
char *str ;
str=(char*)malloc(1000*sizeof(char)) ;
cin>>t ;
while(t--)
{
   cin>>no ;
   cin>>str ;
 
   Case_specific_Sorting(str,no) ;
   cout<<str<<endl ;
}
return 0;
}

void Case_specific_Sorting(char *str,int l)
{
    char *small,*cap ;
    small=(char*)malloc(1000*sizeof(char)) ;
    cap=(char*)malloc(1000*sizeof(char)) ;
   
    int i,x,y ;
    x=0 ;
    y=0 ;
   
    for(i=0;i<l;i++)
    {
        if(str[i]>='a'&&str[i]<='z')
        {
            small[x]=str[i] ;
            x++ ;
        }
        else
        {
            cap[y]=str[i] ;
            y++ ;
        }
    }
   
    small[x]='\0' ;
    cap[y]='\0' ;
   
    sort(small,x) ;
    sort(cap,y) ;
   
    x=0 ;
    y=0 ;
   
    for(i=0;i<l;i++)
    {
        if(str[i]>='a'&&str[i]<='z')
        {
            str[i]=small[x] ;
            x++ ;
        }
        else
        {
            str[i]=cap[y] ;
            y++ ;
        }
    }
    str[i]='\0' ;
}

void sort(char *str,int no)
{
    int i,j ;
    char temp ;
   
    for(i=0;i<no-1;i++)
    {
        for(j=0;j<no-i-1;j++)
        {
            if(str[j]>str[j+1])
            {
                temp=str[j] ;
                str[j]=str[j+1] ;
                str[j+1]=temp ;
            }
        }
    }
}

---------------------------------------------------------------------------------