CareerCup

If you assume a small set of possible characters, then counting sort will do it.

public static void sortString(String unsortedString) {
		char[] unsortedStringLetters = unsortedString.toCharArray();

		int i;
		for ( i = 0 ; i < stringToBeSorted.length() ; i++ ) {
			chars[stringToBeSortedLetters[i]]++;
		}

		int j = 0;
		for (i = 0 ; i < 256 ; i++ ) {
			int count = chars[i];
			while ( count > 0 ) {
				
				stringToBeSortedLetters[j] = (char) i;
				j++;
				count--;
			}
		}

		System.out.println(stringToBeSorted + " : " + String.valueOf(stringToBeSortedLetters));
}

public static void sortString(String stringToBeSorted) {
		char[] stringToBeSortedLetters = stringToBeSorted.toCharArray();


int i;
		for ( i = 0 ; i < stringToBeSorted.length() ; i++ ) {
			chars[stringToBeSortedLetters[i]]++;
		}



int j = 0;
		for (i = 0 ; i < 256 ; i++ ) {
			int count = chars[i];
			while ( count > 0 ) {
				
				stringToBeSortedLetters[j] = (char) i;
				j++;
				count--;
			}
		}



System.out.println(stringToBeSorted + " : " + String.valueOf(stringToBeSortedLetters));
}

Couting sort and bucket sort can be used.

void CountingSort(int *a, int n, int range) {
	using namespace std;

	int *b = new int(n);

	for (int j =0; j<n; ++j)
		b[j] =0;

	int *count = new int (range+1);
	int i;
	for (i =0; i<=range; ++i)
		count[i] = 0;

	for (i =0; i<n; ++i)
		count[a[i]] = count[a[i]] +1;

	for (i =1; i<=range; i++)
		count[i] = count[i] + count[i-1];

	for (i =n-1; i>=0; i--) {
		b[count[a[i]]-1] = a[i];
		count[a[i]] = count[a[i]]- 1;
	}

	for (i =0; i<n; ++i)
		cout<<b[i]<<" ";
	cout<<endl;

}

int main () {
	int a[] = {3,2,1,4,2,3,2,2,2,1,4,3,2};
	int size = sizeof (a)/ sizeof(*a);
	CountingSort(a,size,4);
	return 0;
}

void sortCharArray(char a[])
{
   int b[256];
    int n = 5;
    for(int i =0; i<256; i++)
        b[i] = 0;
    for(int j = 0; j<n; j++)
    {
            b[a[j]]++;
    }
    for(int i = 0; i<256; i++)
    {
            int c = b[i];
            for(int j=0; j<c; j++)
            {
                    char ch = i;
                    cout<<ch;
            }
    }  
}

Answer: is not possible if we want to use linear space. If the space is not an issue we can use Counting sort, if the space is indeed an issue then a well optimized QuickSort can get nlogn time, which is almost linear.

Non comparison solutions like Counting and Bucket sort are the only kinds of sort that can guaranty linear time (with a small amount of possible elements), still is not linear space since you need to create a big indexed table, and that will take at the best case 2N of space.

I used radix sort. Here is the python code.

def radixsort (str):
m = 10
n = 1
d = 2

for i in xrange(d):
v = [None] * 10

for c in str:
index = (ord(c) % m) / n

if (v[index] == None):
v[index] = []

v[index].append(c)

k = 0

for e in v:
if (e != None):
for item in e:
str[k] = item
k = k + 1

m = m * 10
n = n * 10

return str

print radixsort(['A','N','F','J','D','H','C','G','Z','E','X','Q'])


Output is ['A', 'C', 'D', 'E', 'F', 'G', 'H', 'J', 'N', 'Q', 'X', 'Z']

Counting sort can be used only for Int and with a given range and here it is Char.

import java.util.Arrays;

public class SortCharArray {
	
	public static void main( String args[] ) {
		
		char[] a = { 'b', 'f', 'c', 'z', 'a', 'd', 'x', 'h' };
		
		char[] b = charCountingSort( a );
		
		for( int i = 0; i < b.length; i++ ) {
			System.out.print( b[i] + " " );
		}
		
	}

	private static char[] charCountingSort(char[] a) {
		
		int[] count = new int[26];
		char[] b = new char[a.length];
		
		for( int i = 0; i < count.length; i++ ) {
			count[i] = 0;
		}
		
		for( char c : a ) {
			count[c - 'a']++;
		}
		
		int current = 0;
		
		for( int i = 0; i < count.length; i++ ) {
			if( count[i] != 0 ) {
				Arrays.fill( b, current, current + count[i], (char)(i + 'a') );
				current++;
			}
		}
		
		return b;
	}
}

It's counting sort. The time complexity is (O(n)), given that ACSII ranges from 0 to 255.

public class CountingSort {
  public static final int k = 256;
  public static String countingSort(String s) {
    if (s == null) {
      return null;
    }
    
    int[] c = new int[k];
    char[] b = new char[s.length()];

    for (int i = 0; i < c.length; i++) {
      c[i] = 0;
    }

    for (int i = 0; i < s.length(); i++) {
      c[s.charAt(i)]++;
    }

    for (int i = 1; i < k; i++) {
      c[i] = c[i] + c[i - 1];
    }

    for (int i = 0; i < s.length(); i++) {
      b[c[s.charAt(i)] - 1] = s.charAt(i);
      c[s.charAt(i)]--;
    }
    return new String(b);
  }

  public static void main(String[] args) {
    System.out.println(countingSort(""));
  }
}