4
\$\begingroup\$

Trying to learn shell sort, I kinda understood what wikipedia was trying to say, but I wanted a bit of confirmation, so I went on youtube, here, but this code does not work and does not look like what I read on wikipedia. I go to hi's website just in case I misspelled anything to copy+paste hi's code, nop not working either.

So here is my version, or rather what I understood of it. It does work (as in it gives me a correctly sorted array) but I'm not 100% sure this is even shell sort, or is it ? I don't know.

public int[] shellSort(int[] numbers, compare compare) {

    int firstPivot, secondPivot, temp;
    int interval = numbers.Length / 2;

    while (interval > 0) {

        System.Diagnostics.Debug.WriteLine(interval);


        // Start from interval, go all the way to the end
        for (secondPivot = interval; secondPivot < numbers.Length; secondPivot++) {

            firstPivot = secondPivot;
            temp = numbers[secondPivot];

            // Compare with predecesors from interval to interval
            while ((firstPivot - interval >= 0) && compare(temp, numbers[firstPivot - interval])) {

                numbers[firstPivot] = numbers[firstPivot - interval];
                firstPivot -= interval;

            }

            // At the end we find the almost correct position for our "secondPivot" number
            numbers[firstPivot] = temp;

        }

        // Decrease interval
        interval = interval / 2;
    } // Untill interval is "1" then we practically get an insertion sort that cleans up 
      // and have a properly sorted array

    return numbers;
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Just thought I'd mention your brackets are Java-style. Not to start any Holy Wars, but C#-style curly braces go on the next line ;) \$\endgroup\$ – Mathieu Guindon Apr 10 '14 at 19:44
  • \$\begingroup\$ @Mat'sMug that was the first thing I did when I got Visual studio: Went to formating options and change that ASAP. \$\endgroup\$ – Kalec Apr 10 '14 at 20:05
  • 4
    \$\begingroup\$ That's cool and all, @Kalec, but sticking to another language's standards isn't exactly good practice. I see you also name methods in lowercase. You'll notice that your code is, therefore, entirely unlike every object in the framework itself. While that's nice for you, if you ever consider doing non-solo projects, I'd suggest being a bit more flexible. Java and C# have a lot in common, but you shouldn't break the standards anymore than you should in LISP or some other entirely different language. \$\endgroup\$ – Magus Apr 10 '14 at 22:09
  • \$\begingroup\$ @Magus I get that, but the non-inline opening brackets just mess me up so bad. In my personal projects I'll keep it this way no doubt. But if I work with others, then yes ... of-course. \$\endgroup\$ – Kalec Apr 10 '14 at 22:52
  • \$\begingroup\$ Wow, I never considered brace placement--of which there are at least five variants across many languages--to be language-specific. Naming conventions I get, but I feel that whitespace should be left to the project owners. No biggie, just a surprise. :) \$\endgroup\$ – David Harkness Apr 11 '14 at 3:25
3
\$\begingroup\$

First, the good points: your code is quite cleanly written. Although some may argue over the naming convention(s) you've chosen, your names are reasonable, readable, and you do seem to have followed the naming convention fairly consistently.

At least if I'm reading it correctly, yes, this does implement a Shell sort. Unfortunately, however, it uses a sequence of gap values (powers of 2) that is known to be fairly inefficient. With the right sequence, Shell-sort can give around O(N1.2). There are a couple of fairly easy sequences to generate that give only somewhat worse than that (around N1.3 to N1.5). Although I don't believe a theoretical basis for it is known, the best sequences mostly follow ratios of around 2.2 to 2.25 or so.

Starting with N/2 doesn't seem to be the best choice either. At least in most cases, starting somewhere around N/3 (or smaller) tends to work better.

\$\endgroup\$
  • \$\begingroup\$ I was going to math it up a bit with the fractions but I am tired and I can't find the syntax.... \$\endgroup\$ – Malachi Apr 11 '14 at 5:18
  • 1
    \$\begingroup\$ @Malachi The answer and notation are fine as-is. \$\endgroup\$ – 200_success Apr 11 '14 at 6:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.