**A FLEXIBLE SHELLSORT**

Write a version of ** Shellsort**,

**shellSortX()**, that takes, as input, a

**. Use an**

*gap sequence***int**array for the

**.**

*gap sequence*Here is how the client might use the **shellSortX()**:

final int ARRAY_SIZE = 10000;

Integer[] arrayOfInts1 = new Integer[ARRAY_SIZE];

Integer[] arrayOfInts2 = new Integer[ARRAY_SIZE];

int[] gapArray = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,

2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,

1048576};

int[] sedgewickArray = new int[30]; // to be computed using formulas

// … other gap arrays …

// fill distinct arrays with identical random values so we can compare gaps

…

shellSortX(arrayOfInts1, gapArray); // time this

…

shellSortX(arrayOfInts2, sedgewickArray); // time this

…

Client Requirements

- Write your generic above
**main()**so we can see it along with the client in a single file. - Investigate at least four different
*gap sequences*- Shell’s implied
which is computed in*gap sequence***shellSort1()**. - Shell’s explicit
shown above (passed explicitly to*gap sequence***shellSortX()**) *Sedgewick’s*– use the computational definition in the text, and find a way turn that into a sequence in your client using loops, print it out to be sure you are getting a good sequence, and then use it in*gap sequence***shellSortX()**.- The best
you can come up with. I don’t care if it’s trial-and-error or based on something you found. If you can’t find anything better than*gap sequence*, then show me the best you found that isn’t one of the three above.*Sedgewick*

- Shell’s implied
- Run each gap sequence on six sizes of
**int**arrays ranging from 10,000 to 200,000. If you want to go smaller than 10,000 or larger than 200,000, you may, but at least cover that range. Create a table of the four sequences and six array sizes. **Answer these questions at the end of your file:**Why does Shell’simplied by*gap sequence***shellSort1()**give a different timing result than the explicit array described above and passed to**shellSortX()**? Which is faster and why?- Optional – See if you can determine, estimate, guess, or fudge a theta time estimate for each sequence.

*Because this assignment is about your doing research, the instructor’s solution will only show **shellSortX()** and a sample run on one or two arrays, but not include any tabular results on all four gap sequences or six arrays.*

Last Updated on