CC-15 : Sort Even and odd numbers.

Description:

Given an input array, sort its odd elements in descending order and even elements in ascending order.

Test cases and expected outputs:

Input Parameters	Expected outputs
Array: 33, 3, 4, 97, 62, 122, 124, 20, 1,	Sorted Array: 97, 33, 3, 1, 4, 20, 62, 122, 124,

Pseudocode:

compare(n1, n2):

If n1 and n2 are even, then method should return 1 if n1>n2, or return 0 if both are equal, or return -1 if n1

Else If n1 and n2 are odd, then method should return 1 if n2>n1, or return 0 if both are equal, or return -1 if n2

• Else If n1 is odd, return -1 else return 1.

QuickSortEvenOdd(nums[], startIdx, endIdx):

• Integer array named nums, start index startIdx and end index endIdx of nums are received as input parameters.

If (startIdx < endIdx) then execute following steps:

Initialize and integer variable pivot with value nums[endIdx]. We will use this variable to partition the elements into two partitions.

Initialize and integer variable iidx with value startIdx-1. We will use this variable to track and swap elements less than pivot to partition containing elemnts lesser than the pivot.

Iterate through nums using for loop with jidx as iteration variable and values of iidx ranging from startIdx to endIdx-1:

If compare(nums[jidx],pivot) ==-1 then:

Increment iidx by 1.

Swap elements at position iidx and jidx.

Swap elements at index iidx+1 and endIdx.

Set integer variable partitionIdx to iidx+1.

Call method quicksort(nums, startIdx, partitionIdx-1) to sort the partition with lesser elements than pivot element.

Call method quicksort(nums, partitionIdx+1, endIdx,) to sort the partition with greater elements than pivot element.

The element of nums array have been sorted now using Quick Sort, so return nums array from the method.

Code:

private int compare(int n1, int n2) {
	if ((n1%2==0)&&(n2%2==0)){
		if (n1>n2) {
			return 1;
		}else if (n1==n2) {
			return 0;
		} else {
			return -1;
		}
	}
	if ((n1%2==1)&&(n2%2==1)){
		if (n2>n1) {
			return 1;
		}else if (n2==n1) {
			return 0;
		} else {
			return -1;
		}
	}
	
	if (n1%2==1) {
		return -1;
	}else {
		return 1;
	}
}

public int[] quickSortEvenOdd(int[] nums,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		int pivot=nums[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (compare(nums[jidx],pivot)==-1) {
				iidx++;		
				int swap=nums[iidx];
				nums[iidx]=nums[jidx];
				nums[jidx]=swap;
			}
		}
		int swap=nums[iidx+1];
		nums[iidx+1]=nums[endIdx];
		nums[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSortEvenOdd(nums, startIdx, partitionIdx-1);
		quickSortEvenOdd(nums, partitionIdx+1,endIdx);
	}
	return nums;
}

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.

public class SortEvenOdd {

private int compare(int n1, int n2) {
	if ((n1%2==0)&&(n2%2==0)){
		if (n1>n2) {
			return 1;
		}else if (n1==n2) {
			return 0;
		} else {
			return -1;
		}
	}
	if ((n1%2==1)&&(n2%2==1)){
		if (n2>n1) {
			return 1;
		}else if (n2==n1) {
			return 0;
		} else {
			return -1;
		}
	}
	
	if (n1%2==1) {
		return -1;
	}else {
		return 1;
	}
}

public int[] quickSortEvenOdd(int[] nums,int startIdx, int endIdx) {
	if(startIdx < endIdx) {
		int pivot=nums[endIdx];
		int iidx=startIdx-1;
		for (int jidx=startIdx; jidx < endIdx;jidx++) {
			if (compare(nums[jidx],pivot)==-1) {
				iidx++;		
				int swap=nums[iidx];
				nums[iidx]=nums[jidx];
				nums[jidx]=swap;
			}
		}
		int swap=nums[iidx+1];
		nums[iidx+1]=nums[endIdx];
		nums[endIdx]=swap;
		
		int partitionIdx=iidx+1;
		quickSortEvenOdd(nums, startIdx, partitionIdx-1);
		quickSortEvenOdd(nums, partitionIdx+1,endIdx);
	}
	return nums;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	SortEvenOdd sort=new SortEvenOdd();
	int[] nums= { 33,3,4,97,62,122, 124, 20,1};
	System.out.println("\nArray:");
	int arrayIndex=0;
	for (arrayIndex=0; arrayIndex < nums.length; arrayIndex++) {
		System.out.print(nums[arrayIndex]+", ");		
	} 
	System.out.println("\nSorted Array:");
	retVal=sort.quickSortEvenOdd(nums,0,nums.length-1);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
			
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}
}