1
\$\begingroup\$

I need to analyze shell-sort. Currently I am working with it having an increment of N/2. I will then go on to try more efficient increments.

However, my count for comparisons/exchanges seems too low for an array of 2000 elements. I've tried changing it around some but still everything seems too low. Could someone look over my code and see if my counters are in the right places?

public class Sort {
    static int exchanges= 0;
    static int comparisons= 0;

    public static void SegmentedInsertionSort (AnyType[] array, int N, int gap)
    {
        for (int index = gap ; index < N ; index++)
        {
            AnyType temp;
            int j = index - gap;
            while (j >= 0)
            {
                  comparisons++;
                  if (array[j].isBetterThan(array[j+gap]))
                  {
                       temp = array[j];
                       array[j] = array[j + gap];
                       array[j + gap] = temp;
                       j = j - gap;
                       exchanges++;
                  }
                  else j = -1;
            }
        }
    }

    public static void shellSort (AnyType[] array)
    {
        int N = 2000;
        int gap = N/2;
        while (gap > 0)
        {
            SegmentedInsertionSort(array, N, gap);
            gap = gap / 2;
        }
    }
}

Also, I know there are other ways to code this, but the pseudo-code template I was given by my professor looked like this.

\$\endgroup\$
  • 1
    \$\begingroup\$ Hi. Welcome to Code Review! I'm having a bit of trouble analyzing this. For example, I can't run it, as you don't include unit tests or a main method. You also don't include the definition for AnyType, particularly isBetterThan. You may want to try this with smaller arrays that are sorted, sorted in reverse order, and randomly ordered to see what happens. You may also want to post what you get for comparisons and exchanges. And what you expected. Maybe your code is right and your expectations are wrong. \$\endgroup\$ – mdfst13 Feb 19 '16 at 7:25
1
\$\begingroup\$

Your counting code seems correct. comparison increments on each compare operation, exchanges increments only on exchange.

On reversed array of 2000 elements I have got: comparison = 26416 and exchanges = 10400

\$log_{2000} {26416} \approx 1.34\$
So you have \$O(n^{1.34})\$ complexity.
Which is between \$O(n^{3/2}) = O(n^{1.5})\$ and \$O(n^{5/4}) = O(n^{1.25})\$
So according to wiki it's okay for usual gap sequence.
exchanges = 10400 is less then average move count \$0.41N\ln N (\ln \ln N + 1/6)\$ which in case of N = 2000 is approximately 13500, but it depends on gap sequence. E.g if you start with gap = N / 8 it will be equal to 14400.

\$\endgroup\$

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.