# shell sort

• 08-14-2011, 09:10 PM
fam2315
shell sort
I have been given an assignment to do an analysis on the runtimes of various sorting routines, one of which being the shell sort. We were given 4 sets of increments for the shell sort, but I can't find a shell sort algorithm that takes the increments in as an argument, or is that not the way the increment is used?
• 08-14-2011, 09:51 PM
fam2315
here is one that I found that seems to only use 1 value as an increment, I have 6 values that I need to pass in as a sequence:

Code:

```public static void shell(int[] a) {         int increment = a.length / 2;         while (increment > 0) {                 for (int i = increment; i < a.length; i++) {                         int j = i;                         int temp = a[i];                         while (j >= increment && a[j - increment] > temp) {                                 a[j] = a[j - increment];                                 j = j - increment;                         }                         a[j] = temp;                 }                 if (increment == 2) {                         increment = 1;                 } else {                         increment *= (5.0 / 11);                 }         } }```
• 08-15-2011, 01:44 AM
Junky
Quote:

Originally Posted by fam2315
but I can't find a shell sort algorithm that takes the increments in as an argument

So pass the increments in as a second parameter. Do you understand the code you posted? It calculates the next increment each time around the loop. Instead of doing that you just grab the next increment from the list of increments passed in as a parameter.
• 08-23-2011, 04:37 AM
fam2315
Here is what I have

Code:

```public static void shell(int[] a, int[] sequence) {         int increment =sequence[0];         while (increment > 0) {                 for (int i = increment; i < a.length; i++) {                         int j = i;                         int temp = a[i];                         while (j >= increment && a[j - increment] > temp) {                                 a[j] = a[j - increment];                                 j = j - increment;                         }                         a[j] = temp;                 }                 if (increment == 2) {                         increment = 1;                 } else {                         increment *= sequence[i];                 }         } }```
This wont work though, because i is inside the for loop.
• 08-23-2011, 05:37 AM
Junky
I may be on the wrong track but I imagine the increments passed into the method would be something like {6,4,2,1,0}. Then at the end of your loop where you get the next increment you don't need the if statement. Just assign the next increment in the array to the variable.
• 08-23-2011, 05:55 AM
fam2315
that sounds right to me just about. My sequence ends with a 1, so I guess that while loop should be >=1?

I just cant put it all together.
• 08-23-2011, 06:02 AM
Junky
It just takes a moment to think.
Code:

```public static void shell(int[] a, int[] sequence) {     int counter = 0;     int increment =sequence[counter++];     // loop         increment = sequence[counter++];     // end loop }```
• 08-23-2011, 06:08 AM
fam2315
Am I missing something?

Code:

```    public static void shellsort(int[] a, int[] sequence) {         int counter = 0;         int increment = sequence[counter++];         for (int i = increment; i < a.length; i++) {             int j = i;             int temp = a[i];             while (j >= increment && a[j - increment] > temp) {                 a[j] = a[j - increment];                 j = j - increment;             }             a[j] = temp;         }         increment = sequence[counter++];     }```
• 08-23-2011, 06:22 AM
Junky
Quote:

Originally Posted by fam2315
Am I missing something?

I don't know, are you? It would help if you explained things. Errors? Incorrect behaviour? Exploding mice?

Just to reiterate:
// loop
increment = sequence[counter++];
// end loop
• 08-23-2011, 06:23 AM
fam2315
Well, when I print out the integer array after the sort, its all kinds of weird characters. No errors though.
• 08-23-2011, 05:36 PM
fam2315
I am trying to now modify this sort. To take in as an argument the gap sequence as opposed to calculating it:

Code:

```  public static void shellsort( Comparable [ ] a )     {         for( int gap = a.length / 2; gap > 0;                     gap = gap == 2 ? 1 : (int) ( gap / 2.2 ) )             for( int i = gap; i < a.length; i++ )             {                 Comparable tmp = a[ i ];                 int j = i;                 for( ; j >= gap && tmp.compareTo( a[ j - gap ] ) < 0; j -= gap )                     a[ j ] = a[ j - gap ];                 a[ j ] = tmp;             }     }```
Here is what I have but it keeps blowing up with an indexOutofBoundsException on the last line :frusty:

There has to be an easier way to pass in a gap sequence.
Code:

```    public static void shellSort(Comparable[] data, int[] gs) {         int counter = 0;         for (int gap = gs[counter]; gap < data.length;) {             for (int i = gap; i < data.length; i++) {                 Comparable tmp = data[ i];                 int c = i;                 for (; c >= gap && tmp.compareTo(data[ c - gap]) < 0; c -= gap) {                     data[ c] = data[ c - gap];                     gap = gs[counter++];                 }                 data[ c] = tmp;             }           gap = gs[counter++];         }     }```
• 08-24-2011, 01:32 AM
Junky
Code:

`for (int gap = gs[counter]; gap < data.length;) {`
What happens if the first gap value is 10 and you are trying to sort 3 items? 10 is not less than 3 so it never enters the loop. This is another problem besides your AIOOBE.

Why are you making this much harder than it needs to be? Below is the original code you posted above with comments on the simple changes you need to make.
Code:

```public static void shell(int[] a) { // add second parameter for gap values     // declare counter variable     int increment = a.length / 2; // assign first gap value to increment     while (increment > 0) { // see note below         for (int i = increment; i < a.length; i++) {                     int j = i;                     int temp = a[i];                     while (j >= increment && a[j - increment] > temp) {                 a[j] = a[j - increment];                 j = j - increment;             }             a[j] = temp;         }         // replace below if statement with a single statement         // which assigns the next gap value to increment         if (increment == 2) {             increment = 1;         } else {             increment *= (5.0 / 11);         }     } }```
NOTE: The current while loop will still work if the last gap value was 0 but you mentioned that it will be 1. Therefore you will need to change the condition. You could use a boolean flag and add an if statement to control it. Or you could just use the counter in the while condition.