A FLEXIBLE SHELLSORT
Write a version of Shellsort, shellSortX(), that takes, as input, a gap sequence. Use an intarray 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 gap sequence which is computed in shellSort1().
- Shell’s explicit gap sequence shown above (passed explicitly to shellSortX())
- Sedgewick’s gap sequence – 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 shellSortX().
- The best gap sequence 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 Sedgewick, then show me the best you found that isn’t one of the three above.
- 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’s gap sequenceimplied by 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.
