Like Tree7Likes
  • 1 Post By anduril462
  • 1 Post By anduril462
  • 1 Post By Salem
  • 1 Post By anduril462
  • 2 Post By anduril462
  • 1 Post By iMalc

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. #1
    Registered User
    Join Date
    Jun 2011
    Posts
    10

    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. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    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.
    Last edited by anduril462; 06-08-2011 at 10:37 AM.
    Salem likes this.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    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.
    stahta01 likes this.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    Ditto what anduril462 said - ditch the silly swapping of 2 variables without a temp.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Jun 2011
    Posts
    10

    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. #6
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    > 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.
    anduril462 likes this.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  7. #7
    Registered User
    Join Date
    Jun 2011
    Posts
    10
    oh, that's no problem it is meant to work with positive integers < 100

  8. #8
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    Quote Originally Posted by h_dog View Post
    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
    stahta01 likes this.

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,417
    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).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,425
    Salem and whiteflags like this.

  11. #11
    Registered User
    Join Date
    Jun 2011
    Posts
    10
    Quote Originally Posted by Salem View Post
    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.

    Quote Originally Posted by anduril462 View Post
    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.

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    Quote Originally Posted by h_dog View Post
    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?
    stahta01 likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  13. #13
    Registered User
    Join Date
    Jun 2011
    Posts
    10
    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

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    It's not Java, it's a C++ application, and the zip file of it can be downloaded from here.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Jun 2011
    Posts
    10
    thanks

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Shell sort
    By slippy in forum C++ Programming
    Replies: 3
    Last Post: 12-21-2007, 12:07 PM
  2. Shell Sort with Vectors Problem
    By TheSpoiledMilk in forum C++ Programming
    Replies: 4
    Last Post: 11-22-2005, 02:05 PM
  3. shell sort
    By axon in forum C++ Programming
    Replies: 1
    Last Post: 04-27-2004, 07:18 PM
  4. Shell, Heap and Quick Sort
    By GaPe in forum C Programming
    Replies: 1
    Last Post: 08-19-2003, 01:04 PM
  5. Shell Sort vs Heap Sort vs Quick Sort
    By mackol in forum C Programming
    Replies: 6
    Last Post: 11-22-2002, 07:05 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21