CareerCup

Use Dutch Flag Algo:

1. left = 0, mid = 0, right = n
2. while mid < right
3. if arr[mid] == 0 swap arr[left] and arr[mid], then mid++;
4. if arr[i] == 1 mid++;
5. if arr[i] == 2 swap arr[mid] and arr[right], then right--;
geeksforgeeks will have more details.

You could try this:

arr = [0,2,2,0,2,1]

zeroFreq, oneFreq, twoFreq = 0, 0, 0
newList = []

for i in xrange(len(arr)):
  if arr[i] == 0: 
    zeroFreq += 1
  elif arr[i] == 1: 
    oneFreq += 1
  else: 
    twoFreq += 1

for i in xrange(zeroFreq):
  newList.append(0)
for i in xrange(oneFreq):
  newList.append(1)
for i in xrange(twoFreq):
  newList.append(2)

print newList

Dutch Flag Algorithm

Following-up question: Assume counting is not allowed, how to do it in O(n)?

1. Find number of '0', '1' and '2'
2. Create new array (or replace old) knowing how many '0's, '1's and '2's should be there.

scan full array and count 0 and 1 then print 0 and 1 counted number of times then print rest as 2.

crackprogramming.blogspot.com/2012/11/three-color-sort-sort-array-containing.html

Solution loops through the array once keeping track of the minimum index for 0,1,2. If the number at the previous index if greater than the current index number, then we swap the current index number with the minimum index of the number at previous index.

static void sort(int[] array) {
  if (array == null || array.length < 1)
   return;
  int[] lastIndex = new int[3];
  lastIndex[0] = -1;
  lastIndex[1] = -1;
  lastIndex[2] = -1;
  System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
 for (int i = 0; i < array.length; i++) {
  if (lastIndex[array[i]] == -1)
   lastIndex[array[i]] = i;
  if (i != 0) {
   int current = array[i];
   int prev = array[i - 1];
   if ((prev - current) > 0) {
    if ((prev - current) == 1 || lastIndex[1] == -1) {
     swap(i, lastIndex[prev], array);
     updateLastIndex(current, prev, i, lastIndex, array);
     System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
    } else {
     // swap 1 and 0
     swap(i, lastIndex[1], array);
     updateLastIndex(0, 1, i, lastIndex, array);
     System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
     // swap 2 and 1
     swap(i, lastIndex[prev], array);
     updateLastIndex(current, prev, i, lastIndex, array);
     System.out.println("lastIndex(" + Arrays.toString(lastIndex) + ") array("+ Arrays.toString(array) + ")");
     }
    }
   }
  }
 }
static void updateLastIndex(int current, int previous, int index, int[] lastIndex, int[] array) {
 if (lastIndex[current] > lastIndex[previous])
  lastIndex[current] = lastIndex[previous];
 if (array[lastIndex[previous] + 1] == previous)
  lastIndex[previous]++;
 else
  lastIndex[previous] = index;
}
static void swap(int i, int j, int[] array) {
 array[j] ^= array[i];
 array[i] ^= array[j];
 array[j] ^= array[i];
}

Just use binary sorting.

Just use buble sorting...

May be you can use counting sort.

public static int[] getSortedArray ( int[] inputArr ) {
		
		/*
		 * We already know that the unsorted Array has just 
		 * 0s, 1s, 2s. We can leverage this information. 
		 */
		
		if ( inputArr == null ) {
			return null;
		}
		int[] intermediateArr = new int[3];
		 
		int i;
		for ( i = 0 ; i < inputArr.length ; i++ ) {
			intermediateArr[inputArr[i]]++; 
		}
		
		int count = 0;
		for ( i = 0 ; i < intermediateArr.length; i++ ) {
			while ( intermediateArr[i] > 0 ) {
				inputArr[count] = i;
				count++;
				intermediateArr[i]--;
			}
		}
		
		return inputArr;
	}