# Analyzing Shellsort Gap sequences Project – timelynursingwriters.com

Programming – timelynursingwriters.com

Analyzing Shellsort Gap sequences Project – timelynursingwriters.com

#### 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;_x000D_ _x000D_ Integer[] arrayOfInts1 = new Integer[ARRAY_SIZE];_x000D_ Integer[] arrayOfInts2 = new Integer[ARRAY_SIZE];_x000D_ _x000D_ int[] gapArray = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024,_x000D_ 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288,_x000D_ 1048576};_x000D_ int[] sedgewickArray = new int[30]; // to be computed using formulas_x000D_ // ... other gap arrays ..._x000D_ _x000D_ // fill distinct arrays with identical random values so we can compare gaps_x000D_ _x000D_ _x000D_ ..._x000D_ _x000D_ shellSortX(arrayOfInts1, gapArray); // time this_x000D_ _x000D_ ..._x000D_ _x000D_ shellSortX(arrayOfInts2, sedgewickArray); // time this_x000D_ _x000D_ ..._x000D_ _x000D_

##### 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.*