CODEWITHSUNDEEP
algorithmsortingtime-complexity
Gabriella Alice Karin
Gabriella Alice Karin

Reputation: 31

Shell sort running time on pre-sorted list (best case)

I'm confused on the running time of shell sort if the list is pre-sorted (best case). Is it O(n) or O(n log n)?

    for(k=n/2; k>0; k/=2)
       for(i=k; i<n; i++)
           for(j=i;j>k; j-=k)
              if(a[j-k]>a[j]) swap
              else break;

Shell sort is based on insertion sort, and insertion sort has O(n) running time for pre-sorted list, however, by introducing gaps (outermost loop), I don't know if it makes the running time of shell sort O(n log n) for pre-sorted list.

Thank's for the help

Upvotes: 2

Views: 6881

Answers (4)

Somebody
Somebody

Reputation: 11

If you're using log(n) compares for an array of length n, then you will have a time complexity of n log (n)

Otherwise, if you always use a constant amount of compares (such as 3), you will get O(n)

In general, if you use k gap values, your time complexity will be O(kn). People saying the best case is O(n log n) use log n gap values and people who say it's O(n) refer to always using a constant number of gap values regardless of the input.

Upvotes: 1

Olof Forshell
Olof Forshell

Reputation: 3274

The best case is O(n). Here's why:

Let's start with insertion sort. An already sorted list of n entries will require n minus 1 comparisons to complete (no exchanges necessary).

Put the insertion sort in the context of a shellsort with a single increment, 1. An already sorted list of n entries will require n minus the gap (1).

Suppose you have two gaps 5 followed by 1 and n is greater than 5. An already sorted list will require n-5 comparisons to process the first gap (no exchanges necessary) plus n-1 comparisons for the second or 2n-6 (no exchanges necessary).

It doesn't matter if you used n as input to generate the gaps. You end up with each gap being a constant value c (the final c being 1).

So the algorithm for the best case is "n*number of gaps - the sum of all gaps".

I don't see how "n*number of gaps - ..." could be anything other than O(n).

I know most discussions put it as something else and I get the impression that no one has bothered to sit down and do the math. As you can see, it's not rocket science.

Upvotes: 0

Jerry Coffin
Jerry Coffin

Reputation: 490408

I think (at least as normally implemented) it's approximately O(n log n), though the exact number is going to depend on the progression you use.

For example, in the first iteration you invoke insertion sort, let's say, five times, each sorting every fifth element. Since each of these is linear on the number of elements sorted, you get linear complexity overall.

In the next iteration you invoke insertion sort, say, twice, sorting every other element. Again, linear overall.

In the third, you do insertion sort on every element, again linear.

In short, you have a linear algorithm invoked a (roughly) logarithmic number of times, so it should be about O(n log n) overall. That assumes some sort of geometric progression in the step sizes you use, which is common but (perhaps) not absolutely required.

Upvotes: 1

Igor ostrovsky
Igor ostrovsky

Reputation: 7392

In the best case when the data is already ordered, the innermost loop will never swap. It will always immediately break, since the left value is known to be smaller than the right value:

for(k=n/2; k>0; k/=2)
   for(i=k; i<n; i++)
       for(j=i;j>k; j-=k)
          if(false) swap
          else break;

So, the algorithm collapses to this:

for(k=n/2; k>0; k/=2)
   for(i=k; i<n; i++)
      no_op()

The best case then becomes:

O((n - n/2) + (n - n/4) + (n - n/8) + ... + (n - 1)) 
= O(nlog(n) - n) 
= O(nlog(n))

That said, according to Wikipedia, some other variants of Shell Sort do have an O(N) best case.

Upvotes: 2

Related Questions