1. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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?  Reply With Quote

2. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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:

Java 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);
}
}
}```
Last edited by fam2315; 08-14-2011 at 11:59 PM.  Reply With Quote

3. ##  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.  Reply With Quote

4. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## Here is what I have

Java Code:
```public static void shell(int[] a, int[] sequence) {
int increment =sequence;
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.  Reply With Quote

5. ## 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.  Reply With Quote

6. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## 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.  Reply With Quote

7. ## It just takes a moment to think.
Java Code:
```public static void shell(int[] a, int[] sequence) {
int counter = 0;
int increment =sequence[counter++];
// loop
increment = sequence[counter++];
// end loop
}```  Reply With Quote

8. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## Am I missing something?

Java 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++];
}```  Reply With Quote

9. ##  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  Reply With Quote

10. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## Well, when I print out the integer array after the sort, its all kinds of weird characters. No errors though.  Reply With Quote

11. Member Join Date
Feb 2011
Posts
78
Rep Power
0

## I am trying to now modify this sort. To take in as an argument the gap sequence as opposed to calculating it:

Java 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 There has to be an easier way to pass in a gap sequence.
Java 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++];
}
}```  Reply With Quote

12. ## Java 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.
Java 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.  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•