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

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.

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

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

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

YouTube - &#x202a;Shell-sort with Hungarian (Székely) folk dance&#x202c;&rlm;

Originally Posted by Salem

So what's your point then?

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.

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

thanks