# damn shell sort

This is a discussion on damn shell sort within the C Programming forums, part of the General Programming Boards category; Hi. guys. I am trying to implement shell sort which is, to my understanding, just a bubble sort with gaps. ...

1. ## damn shell sort

Hi. guys.
I am trying to implement shell sort which is, to my understanding, just a bubble sort with gaps. This is what I wrote :

Code:
```int shellSort(int *arr, int n){
int i=0, j;
printf("\nstarting shell sort", n);
j=(n%2)?n-2:n-3; // Make shore j is odd and less then n.
while(j>0){
while(n-(i+j)){ // Like buble sort but with gaps.
if(arr[i]>arr[i+j]){
arr[i+j]+=arr[i]; // Swap the two members of the array
arr[i]=arr[i+j]-arr[i];// if nesesry.
arr[i+j]=arr[i+j]-arr[i];
}
i++;
}
j-=2; // Continue im steps of 2
i=0;
}
return 0;
}```
output of random array:

sorting array:
1, 36, 27, 30, 15, 29, 32, 42, 4, 9, 20, 18, 21, 20, 46, 34,
starting shell sort
1, 4, 9, 15, 20, 18, 21, 27, 20, 30, 29, 32, 34, 36, 42, 46,
and
sorting array:
33, 2, 34, 22, 3, 18, 12,
starting shell sort
2, 18, 12, 3, 33, 22, 34,
as you can see I am not quite there yet, it is almost sorted but not completely.
What am I doing wrong? maybe someone can explain shell sort better to me?

thanks

2. Code:
`arr[i+j]+=arr[i]; // Swap the two members of the array`
I think you want an = there, not a +=. Try putting a little more space around your operators, comparators, assignments, etc. It makes code easier to read, which means fewer errors, and easier to find when you do make them.

EDIT: Strike that. You're doing the silly swap with no temp.

3. Hmm...I think maybe you need to review what exactly shell sort is and how it works. All the info I found seems to suggest it's a modified insertion sort, and that there should be three nested loops, not just the two you have. Here's the wikipedia article to get you started: Shell sort - Wikipedia, the free encyclopedia.

4. Ditto what anduril462 said - ditch the silly swapping of 2 variables without a temp.

5. ## hi

thanks for answering so quickly. the wiki article is not so clear and it is hard to understand their pseudo code. In fact surprisingly, a Google search on the subject did not yield anything helpful, can anyone explain this better or does any one has a link to something helpful?

And just so I'd know, why shouldn't I use the silly var swap?

thanks

6. > And just so I'd know, why shouldn't I use the silly var swap?
Because integer overflow is unspecified behaviour. Mostly it just wraps round, but it could also cause a machine exception.

And if you tried it with floats or doubles, then rounding errors would screw up your data.

And for any other data type except the unsigned (char,short,int,long), it doesn't work at all.

7. oh, that's no problem it is meant to work with positive integers < 100

8. Originally Posted by h_dog
the wiki article is not so clear and it is hard to understand their pseudo code. In fact surprisingly, a Google search on the subject did not yield anything helpful, can anyone explain this better or does any one has a link to something helpful?
What did you search for? A simple google search for "shell sort" turned up dozens of sites with explanations, diagrams, animations and sample source code. I'm not sure anybody here can do better than that. It might help if you first make sure you have a very thorough understanding of insertion sort, since it is the foundation of shell sort.

And just so I'd know, why shouldn't I use the silly var swap?
You should always strive for the simplest, clearest, easiest to understand code. Even if this comes at the cost of some speed or memory/resource usage. That means there's less chance you will make a mistake, more of a chance you or someone else will find it if there is one, and more of a chance that somebody else can understand your code, take over maintenance, etc. Besides, resources (memory and speed) are so abundant now, that saving those 4 bytes for the sake of reduced memory usage is pointless. Swapping without a temp, while reasonably well known, is just not as clear or simple as the standard:
temp = a
a = b
b = temp

9. So what's your point then?

Do you want to learn techniques which will always work, or are you more interested in "I'll use this dumb technique because I know 'x' is true about this particular problem"?

Because the latter is a big problem when 'x' stops being true without you realising it (say someone takes your code and uses it for something else).

10. Originally Posted by Salem
My point is: if the reason for not using this method is because of what you said, then I am explaining to you that I am aware of that. And the only reason I used it is because this is a special case where I need to sort arrays of positive integers < 100. seeing how it annoys you all to see this I will never use this method in this forum.

Originally Posted by anduril462
What did you search for? A simple google search for "shell sort" turned up dozens of sites with explanations, diagrams, animations and sample source code. I'm not sure anybody here can do better than that. It might help if you first make sure you have a very thorough understanding of insertion sort, since it is the foundation of shell sort.
Yep, I did a Google search before writing this post and although it seams like allot of results the content is pretty much the same and not very clear, and the animations don't work on my pc. the dance routine anduril462 brought was actually the best thing on the subject I saw.

I just hoped that maybe someone like me had trouble with this shell sort and can give me some insight on the matter or a link to a good article.

11. Originally Posted by h_dog
I am trying to implement shell sort which is, to my understanding, just a bubble sort with gaps.
No, that's Comb Sort. Shell Sort is based on Insertion Sort, but with decreasing gaps.

Would a PC app that animates a whole lot of algorithms, including Shell Sort with a few different gap tables be useful to you?

12. Yes, of course any help is appreciated, although the java on my pc is not working properly so I am not sure whether it will work
but ye, thanks

13. It's not Java, it's a C++ application, and the zip file of it can be downloaded from here.

14. thanks