CODEWITHSUNDEEP
algorithmsortingtime-complexitycode-analysisshellsort
Tansheet Ali Taj
Tansheet Ali Taj

Reputation: 45

How to Calculate Running Time of Shell-sort Algorithm

How to Calculate step by step Running Time of Shell-sort Algorithm ?

shellsort(itemType a[], int l, int r){
   int i, j, k, h; 
   itemType v;
   int incs[16] = { 1391376, 463792, 198768, 86961, 33936,
                    13776, 4592, 1968, 861, 336, 
                    112, 48, 21, 7, 3, 1 };
   for (k = 0; k < 16; k++)
   {
      for (h = incs[k], i = l+h; i <= r; i++)
      { 
         v = a[i]; j = i;
         while (j >= h && a[j-h] > v)
         { 
            a[j] = a[j-h]; 
            j -= h; 
         }
        a[j] = v; 
      }//end inner-for loop 
   }//end outer for-loop
}//end shellsort

Upvotes: 0

Views: 391

Answers (1)

tmyklebu
tmyklebu

Reputation: 14215

Wikipedia has a bound of O(N exp(sqrt(8 log(5/2) log(n))) and directs you to a paper by Incerpi and Sedgewick. I'd suggest you look there; getting good bounds on the runtime of many shellsort variants is highly nontrivial. Including, probably, this one.

Upvotes: 1

Related Questions