Like Tree8Likes
  • 2 Post By anduril462
  • 1 Post By Adak
  • 1 Post By TheBigH
  • 2 Post By iMalc
  • 1 Post By BIOS
  • 1 Post By Adak

Shell Sort

This is a discussion on Shell Sort within the C Programming forums, part of the General Programming Boards category; Today I studied the following shell sort code: Code: void shellsort(int v[], int n) { int gap, i, j, temp; ...

  1. #1
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55

    Shell Sort

    Today I studied the following shell sort code:

    Code:
    void shellsort(int v[], int n)
    {
    	int gap, i, j, temp;
    
    	for (gap = n/2; gap > 0; gap /= 2)
    		for(i = gap; i < n; i++) 
    			for (j=i-gap; j>= 0 && 
                                 v[j]>v[j + gap]; j-=gap){
    				temp = v[j];
    				v[j] = v[j + gap];
    				v[j+gap] = temp;
    			 }
    
    }
    I follow it all except for one part. In the innermost loop, the final loop expression:

    Code:
    j -= gap
    What is the point of this? Can you not just write this loop as:

    Code:
    for (j=i-gap; j>= 0 && v[j]>v[j + gap];)
    and have the second loop control the amount of times elements are compared?

    Cheers

    BIOS
    Last edited by BIOS; 09-15-2011 at 05:10 AM.

  2. #2
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    What loop do you mean with "second loop"? The one that increments "i"? How will that one influence what goes on inside the "j" loop?
    Code:
    while(!asleep) {
       sheep++;
    }

  3. #3
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Quote Originally Posted by TheBigH View Post
    What loop do you mean with "second loop"? The one that increments "i"?
    Yep. There are three loops in the code example. The second one contains the i increment.

    Quote Originally Posted by TheBigH View Post
    How will that one influence what goes on inside the "j" loop?
    Well it controls how often the j loop executes i.e. it will always ensure the j loop executes at least (n - gap) times on each iteration of the outermost loop.

  4. #4
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,288
    The point of a shell sort is to sort every gap-th element. You start with a wide gap, like N/2, then reduce that until the gap is 1. The changing of the gap size is your outer loop. The middle loop makes sure that you cover all the elements when your gap size is not 1. The inner loop steps through the data in increments of gap, sorting elements at 0*gap, 1*gap, 2*gap, etc. Not changing j would amount to only looking at, 0*gap and 1*gap. Sure, you could probably remove that and alter your i loop to "pick up the slack", but then you no longer have a shell sort. It would become something else.

    Read Shell sort - Wikipedia, the free encyclopedia, and look closely at the following diagram that article: File:Shellsort.svg - Wikipedia, the free encyclopedia.

    The different rows correspond to your outer loop, reducing gap until it's 1. In an individual row, the different colored numbers represent the iterations of the i loop. The numbers of one color (e.g. all red numbers) correspond to the numbers examined/swapped by the j loop. If you didn't do j -= gap, you would only examine one pair of numbers for each color, instead of the whole array.
    TheBigH and BIOS like this.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    What's ironic, is I wrote that Shell sort, from the description of it, on Wikipedia.

    My previous Shell sort was fubar'd from tinkering with it so much.

  6. #6
    Registered User whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    7,525
    Can I ask why you did a swap instead of a shift? The wiki code did a shift.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Well, I just posted my Shell sort example in BIOS's thread, so I thought this was my code, but it's NOT.

    I HATE Shell sort's with a swap, instead of a shift! There's a lot of Shell sort's out there that have this swap code in it, and it is entirely wrong.

    This is how it should be, imo:

    Code:
    //Shell sort Brand new, not optimized
    void shellSort(int a[], int hi) {
       int i, j, gap, temp;
    
       for(gap = hi/2; gap > 0; gap /= 2) { //original Shell divisor
          for(i = gap; i < hi; i++) {
             temp = a[i];
             j = i;
             while(j>= gap && a[j-gap] > temp) {
                a[j] = a[j - gap];
                j = j - gap;
             }
             a[j] = temp;
          }
       }
    }
    This is still unoptimized, but that is also, original Shell code, as I understand it.

    BIOS, why'd you change my Shell code, dammit?
    Last edited by Adak; 09-14-2011 at 08:20 PM.
    BIOS likes this.

  8. #8
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    Quote Originally Posted by Adak View Post
    Well, I just posted my Shell sort example in BIOS's thread, so I thought this was my code, but it's NOT.

    I HATE Shell sort's with a swap, instead of a shift! There's a lot of Shell sort's out there that have this swap code in it, and it is entirely wrong.

    This is how it should be, imo:

    Code:
    //Shell sort Brand new, not optimized
    void shellSort(int a[], int hi) {
       int i, j, gap, temp;
    
       for(gap = hi/2; gap > 0; gap /= 2) { //original Shell divisor
          for(i = gap; i < hi; i++) {
             temp = a[i];
             j = i;
             while(j>= gap && a[j-gap] > temp) {
                a[j] = a[j - gap];
                j = j - gap;
             }
             a[j] = temp;
          }
       }
    }
    This is still unoptimized, but that is also, original Shell code, as I understand it.

    BIOS, why'd you change my Shell code, dammit?
    Sure, you can optimize that further by replacing Shell's original increment sequence with a non-suckful one. Another, minor, improvement you can make is to swap the order of the two things in the while statement, since a[j-gap]>temp is less likely to be true than j>=test for any given test.
    Adak likes this.
    Code:
    while(!asleep) {
       sheep++;
    }

  9. #9
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,261
    Agreed on the shift rather than swap. I take it one step further and don't do either if the first comparison indicates it wont need to move at all.

    Here's the one off my website. This is using one of the best, if not the best, known gap sequences:
    Code:
    template <class T>
    void ShellSort(T a[], int n) {
        //Incerpj-Sedgewick 1985
        const int incs[] = {
            1, 3, 7, 21, 48, 112,
            336, 861, 1968, 4592, 13776,
            33936, 86961, 198768, 463792, 1391376,
            3402672, 8382192, 21479367, 49095696, 114556624,
            343669872, 52913488, 2085837936};
        for (int l = sizeof(incs)/sizeof(incs[0]); l > 0;) {
            const int m = incs[--l];
            for (int i = m; i < n; ++i) {
                int j = i - m;
                if (a[i] < a[j]) { //check if the item needs inserting first (eliminates redundant copying)
                    const T tempItem = a[i];
                    do {
                        a[j+m] = a[j];
                        j-=m;
                    } while ((j >= 0) && (tempItem < a[j]));
                    a[j+m] = tempItem;
                }
            }
        }
    }
    Well it's C++, but I'm sure that doesn't really change anything here.
    The extra 'if' makes it faster for when the type being sorted isn't as small or trivial as an int.

    I find that it's much easier to understand if you compare it to an insertion sort implementation.
    Here's mine which is obviously implemented in the same style:
    Code:
    template <class T>
    void InsertionSort(T a[], int n) {
        for (int i = 1; i < n; ++i) {
            //check if the item needs inserting first (eliminates redundant copying)
            if (a[i] < a[i - 1]) {
                int j = i - 1;
                const T tempItem = a[i];
                //move items along while looking for the correct place
                do {
                    a[j + 1] = a[j];
                    --j;
                } while ((j >= 0) && (tempItem < a[j]));
                //copy item into position
                a[j + 1] = tempItem;
            }
        }
    }
    If you can understand the later then you should be able to understand the former.
    Last edited by iMalc; 09-15-2011 at 02:19 AM.
    BIOS and Adak like 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"

  10. #10
    Registered User
    Join Date
    Sep 2011
    Location
    Dublin
    Posts
    55
    Quote Originally Posted by Adak View Post
    BIOS, why'd you change my Shell code, dammit?
    Haha. Blame Kernighan and Ritchie. It's their code! :P

    @Anduril462 thanks for the explanation.

    Re: use of swap. It's taken from the C programming language 2nd ed. Nothing intentional on my part. Can I ask what the difference is between a swap and a shift?
    Adak likes this.

  11. #11
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Shift vs. swap in Shell sort:

    1) Historical accuracy. Shell sort *is* Insertion sort, with the extra gap feature. Insertion sort uses shifts, not swaps.

    2) Shifts should be slightly faster, although I haven't actually tested that, since reason #1 was enough for me to prefer shifts.

    An example of a shift:

    Code:
    value: 8 at set[1], is being placed
    in set: {5,8,2,4,1,3,7,9}
    
    8 is pulled out to a variable
    set is ready to be shifted: {5,_,2,4,1,3,7,9}
    2->[1], 4->[2], 1->[3], 3->[4], 7->[5] (all shifted to the left 1 place)
    Since 8 is < 9, 8 is "dropped" into set[6], and 9 is not moved. One shift loop has ended.

    No wonder Shell sort is so often seen with swaps instead of shifts! I'm sure I've used K&R's version of Shell sort before, since it's right next to me when I program -- ACK!

    Thanks for an optimized version, iMalc, and the tips, TheBigH.
    Last edited by Adak; 09-15-2011 at 06:18 AM.
    BIOS likes this.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. damn shell sort
    By h_dog in forum C Programming
    Replies: 14
    Last Post: 06-09-2011, 07:19 AM
  2. Shell sort
    By slippy in forum C++ Programming
    Replies: 3
    Last Post: 12-21-2007, 12:07 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