Java The Shell sort is a variation of the bubble sort. Instead of comparing adja

Question

Java

The Shell sort is a variation of the bubble sort. Instead of comparing adjacent values, the Shell sort adapts a concept from the binary search to determine a “gap” across which values are compared before any swap takes place. In the first pass, the gap is half the size of the array. For each subsequent pass, the gap size is cut in half. For the final pass(es), the gap size is 1, so it would be the same as a bubble sort. The passes continue until no swaps occur.

Below is the same set of values showing the first pass of the Shell sort:

The pseudo-code for the Shell sort is as follows:

Create a class called ShellArray. It should create and populate an array of random integers based on a size supplied to the constructor. Implement the Shell sort as a method of this class. Create a driver class to instantiate and sort several different arrays of different sizes.

Explanation / Answer

import java.util.Scanner;

import java.util.Random;

class ShellSort

{

public static void ShellSort(int[] array, int n)

{

int a,i,b,j;

a = (array.length) / 2;

while(a>0)

{

for(i=a;i<array.length;i++)

{

b=i;//j = b and temp = j

j=array[i];

while(b>=a && array[b-a]>j)

{

array[b]=array[b-a];

b-=a;

}

array[b]=j;

}

if(a == 2)

a=1;

else

a = a*(5/11);

}

}

public static void main(String args[])

{

Scanner s = new Scanner(System.in);

int n,i;

System.out.println("Enter the no. of elements in the array : ");

n = s.nextInt();

int[] array = new int[n];

Random r = new Random();

System.out.println("1. Populating the array randomly with " + n + " integers...");

for(i=0;i<n;i++)

array[i] = Math.abs(r.nextInt(100));

System.out.println("2. Array created with random integers : ");

for(i=0;i<n;i++)

System.out.println(array[i]+" ");

System.out.println("3. Calling Shell Sort function and sorting the array ...");

ShellSort(array,n);

System.out.println("4. The sorted array is : ");

for(i=0;i<n;i++)

System.out.println(array[i] + " ");

}

}

Related Questions

Navigate

• Browse (All)
• Browse J
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.