CC-12 : Sort Array consisting of 0s 1s 2s.

Description:

Given an input array containing only 0s, 1s, 2s, sort its elements.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 0, 0, 1, 0, 2, 1, 0, 2, 0, 1,	Sorted Array: 0, 0, 0, 0, 0, 1, 1, 1, 2, 2,

Pseudocode:

mergeSortRecursive(nums[]):

Integer array named nums is received as input parameter.

If nums.length<=1, return nums.

Set variable midIdx to nums.length/2.

Initialize int array variable named leftArr by creating a subarray of nums with elements from index 0 to midIdx.

Initialize int array variable named rightArr by creating a subarray of nums with elements from index midIdx to nums.length.

Initialize int array variable named leftArrRet to return value from recursive call to mergeSortRecursive(leftArr).

Initialize int array variable named rightArrRet to return value from recursive call to mergeSortRecursive(rightArr).

Return int array return by call to megrSort(leftArrRet, rightArrRet).

mergeSort(leftArrRet, rightArrRet):

Integer arrays named leftArr and rightArr are received as input parameters.

Initialize an int array named sorted with length leftArr.length + rightArr.length.

Initialize int variables leftIdx, rightIdx, sorteIdx to 0.

While leftIdx < leftArr.length and rightIdx < rightArr.length:

If (leftArr[leftIdx] < rightArr[rightIdx] :

Set sorted[sortedIdx]=leftArr[leftIdx].

Increment sortedIdx by 1.

Increment leftIdx by 1.

Else:

Set sorted[sortedIdx]=rightArr[rightIdx].

Increment sortedIdx by 1.

Increment rightIdx by 1.

While leftIdx < leftArr.length:

Set sorted[sortedIdx]=leftArr[leftIdx].

Increment sortedIdx by 1.

Increment leftIdx by 1.

While rightIdx < rightArr.length:

Set sorted[sortedIdx]=rightArr[rightIdx].

Increment sortedIdx by 1.

Increment rightIdx by 1.

Return sorted.

Code:

public int[] mergeSortRecursive(int[] nums){
	int midIdx=nums.length/2;
	if (nums.length <=1) {
		return nums;
	}
	int[] leftArr=Arrays.copyOfRange(nums, 0, midIdx);
	int[] rightArr=Arrays.copyOfRange(nums, midIdx, nums.length);
	int[] leftArrRet=mergeSortRecursive(leftArr);
	int[] rightArrRet=mergeSortRecursive(rightArr);
	 return mergeSort(leftArrRet,rightArrRet);
}

public int[] mergeSort(int[] leftArr, int[] rightArr) {
	int[] sorted=new int[leftArr.length+rightArr.length];
	int leftIdx=0; int rightIdx=0; int sortedIdx=0;
	while ((leftIdx < leftArr.length)&&(rightIdx < rightArr.length)) {
		if (leftArr[leftIdx] < rightArr[rightIdx]) {
			sorted[sortedIdx]=leftArr[leftIdx];
			sortedIdx++;
			leftIdx++;
		}else {
			sorted[sortedIdx]=rightArr[rightIdx];
			sortedIdx++;
			rightIdx++;
		}
	}
	while (leftIdx < leftArr.length){
		sorted[sortedIdx]=leftArr[leftIdx];
		sortedIdx++;
		leftIdx++;
	}
	while (rightIdx < rightArr.length){
		sorted[sortedIdx]=rightArr[rightIdx];
		sortedIdx++;
		rightIdx++;
	}
	return sorted;			
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

import java.util.Arrays;

public class Sort0s1s2s {


public int[] mergeSortRecursive(int[] nums){
	int midIdx=nums.length/2;
	if (nums.length <=1) {
		return nums;
	}
	int[] leftArr=Arrays.copyOfRange(nums, 0, midIdx);
	int[] rightArr=Arrays.copyOfRange(nums, midIdx, nums.length);
	int[] leftArrRet=mergeSortRecursive(leftArr);
	int[] rightArrRet=mergeSortRecursive(rightArr);
	 return mergeSort(leftArrRet,rightArrRet);
}

public int[] mergeSort(int[] leftArr, int[] rightArr) {
	int[] sorted=new int[leftArr.length+rightArr.length];
	int leftIdx=0; int rightIdx=0; int sortedIdx=0;
	while ((leftIdx < leftArr.length)&&(rightIdx < rightArr.length)) {
		if (leftArr[leftIdx] < rightArr[rightIdx]) {
			sorted[sortedIdx]=leftArr[leftIdx];
			sortedIdx++;
			leftIdx++;
		}else {
			sorted[sortedIdx]=rightArr[rightIdx];
			sortedIdx++;
			rightIdx++;
		}
	}
	while (leftIdx < leftArr.length){
		sorted[sortedIdx]=leftArr[leftIdx];
		sortedIdx++;
		leftIdx++;
	}
	while (rightIdx < rightArr.length){
		sorted[sortedIdx]=rightArr[rightIdx];
		sortedIdx++;
		rightIdx++;
	}
	return sorted;			
}


public static void main(String[] args) {

int[] retVal;
try {
	
	Sort0s1s2s sort=new Sort0s1s2s();
	int[] nums= { 0,0,1,0,2,1,0,2,0,1};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	
	System.out.println("\n\n Sorted Array:");
	retVal=sort.mergeSortRecursive(nums);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
}
		
}



}