CC-8 : Implement Quick Sort Algorithm.

Description:

Quick Sort (also known as Partition-Exchange sort) works by partitioning the input array into two separate partitions separated by a pivot element. One of the partitions will have elements lesser than pivot and other partition will have elements greater than the pivot. This partitioning and re-organization of elements in the lesser and greater element partitions is done recursively. Given an input array, sort its elements using Quick Sort.

Test cases and expected outputs:

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

Pseudocode:

QuickSort(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 using for loop with jidx as iteration variable and values of iidx ranging from startIdx to endIdx-1:

If nums[jidx]<=pivot 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:

public int[] quickSort(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 (nums[jidx] <= pivot) {
				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;
		quickSort(nums, startIdx, partitionIdx-1);
		quickSort(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 int[] quickSort(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 (nums[jidx] <= pivot) {
				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;
		quickSort(nums, startIdx, partitionIdx-1);
		quickSort(nums, partitionIdx+1,endIdx);
	}
	return nums;
}

public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 *********************/
	int[] retVal;
	try {
	SortQuickSort sort=new SortQuickSort();
	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.quickSort(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();
	}
		
}
}