CC-4 : Implement Shell Sort Algorithm.

Description:

Shell Sort is an optimization of insertion sort. This algorithm avoids large shifts of elements. It works with gaps of h elements of the input array. The gaps of h elements are sorted using insertion sort. Then the value of gap is reduced and above steps are repeated till array is sorted. Given an input array, sort its elements using Shell 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:

ShellSort(nums[]):

Integer array named nums is received as input parameter.

Integer variable len is initialized and set to nums.length.

Iterate through nums using for loop with gap as iteration variable and values of gap ranging from len/2 to gap > 0 and decrement gap by half after each iteration:

Iterate through nums using for loop with jidx as iteration variable and values of jidx ranging from gap to nums.length-1 and increment jidx by 1 in every iteration:

Iterate through nums using for loop with kidx as iteration variable and values of kidx ranging from jidx-gap to while kidx>=0 and deccrement kidx by gap in every iteration:

If nums[kidx+gap] > nums[kid] exit the current loop.

Else swap nums[kidx+gap] and nums[kidx].

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

Code:

public int[] shellSort(int[] nums){
	int len=nums.length;
	for (int gap=len/2; gap>0 ; gap/=2) {
		for(int jidx = gap; jidx < nums.length; jidx++) {
            for(int kidx = jidx-gap; kidx>=0; kidx -= gap) {
               if(nums[kidx+gap] >= nums[kidx])
                  break;
               else {
                  int temp;
                  temp = nums[kidx+gap];
                  nums[kidx+gap] = nums[kidx];
                  nums[kidx] = temp;
               }
            }
         }		
	}
	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 SortShellSort {

public int[] shellSort(int[] nums){
	int len=nums.length;
	for (int gap=len/2; gap>0 ; gap/=2) {
		for(int jidx = gap; jidx < nums.length; jidx++) {
            for(int kidx = jidx-gap; kidx>=0; kidx -= gap) {
               if(nums[kidx+gap] >= nums[kidx])
                  break;
               else {
                  int temp;
                  temp = nums[kidx+gap];
                  nums[kidx+gap] = nums[kidx];
                  nums[kidx] = temp;
               }
            }
         }		
	}
	return nums;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int[] retVal;
	try {
	
	SortShellSort sort=new SortShellSort();
	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.shellSort(nums);
	for (arrayIndex=0; arrayIndex < retVal.length; arrayIndex++) {
		System.out.print(retVal[arrayIndex]+", ");		
	} 
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}

}