shell sort using hibbard increment

Question

I'm new to C. I want to do an experiment with shell sort using hibbard increment in C. And, in order to test the worst case, I always build a reversed array according to the input size. I expect to see the running time following the time complexity O(n^1.5). However, my output somehow follows the time complexity O(n). The following is my code. I would appreciate it if someone could help me find where the problem is.

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <math.h>

int get_input() {
  int input;
  printf("Please type input size(n): ");
  if(scanf("%d", &input) == 0) {
    fscanf(stdin, "%*[^\n]%*c");
  }
  return input;
}

int* build_data(int* array, int size) {
  array = malloc(sizeof(int) * size);
  for(int i=0; i < size; i++) {
    array[i] = size - i;
  }
  return array;
}

double record_time(int* array, int size, void (*fp)(int*, int)) {
  clock_t begin = clock();
  (*fp)(array, size);
  clock_t end = clock();

  return (double)(end - begin) / CLOCKS_PER_SEC;
}

void shell_sort(int* array, int size) {
  int* h_inc;
  int h_size;

  h_size = floor(log(size+1)/log(2));
  h_inc = malloc(sizeof(int) * h_size);
  for(int i=0; i < h_size; i++) {
    h_inc[i] = pow(2, i+1) - 1;
  }

  int i, j, tmp;

  for (int r = (h_size - 1); r >= 0; r--) {
    int gap = h_inc[r];

    for(i = gap; i < size; i++) {
      tmp = array[i];

      for(j = i; j >= gap && tmp < array[j-gap]; j-=gap) {
        array[j] = array[j-gap];
      }
      array[j] = tmp;
    }
  }

  free(h_inc);
  return;
}

int main() {
  while(1) {
    int size;
    int* data;
    double time_elapsed;

    size = get_input();
    if (size <= 0) { break; }

    data = build_data(data, size);
    time_elapsed = record_time(data, size, shell_sort);

    printf("Elapsed time: %f sec\n", time_elapsed);
    free(data);
  }
  return 0;
}

My output is:

Please type input size(n): 10000
Elapsed time: 0.001168 sec
Please type input size(n): 50000
Elapsed time: 0.006094 sec
Please type input size(n): 100000
Elapsed time: 0.010946 sec
Please type input size(n): 500000
Elapsed time: 0.054341 sec
Please type input size(n): 1000000
Elapsed time: 0.118640 sec
Please type input size(n): 5000000
Elapsed time: 0.618815 sec
Please type input size(n): 10000000
Elapsed time: 1.332671 sec

Answer 1

I don't think reverse order is the worst case for (this) shell sort. I took your code and ran it on my Mac and got times:

Please type input size(n): 10000
Elapsed time: 0.000247 sec
Please type input size(n): 50000
Elapsed time: 0.001314 sec
Please type input size(n): 100000
Elapsed time: 0.002768 sec
Please type input size(n): 500000
Elapsed time: 0.016154 sec
Please type input size(n): 1000000
Elapsed time: 0.033013 sec
Please type input size(n): 5000000
Elapsed time: 0.173584 sec
Please type input size(n): 10000000
Elapsed time: 0.338931 sec
Please type input size(n): 10000000
Elapsed time: 0.344284 sec
Please type input size(n): 10000000
Elapsed time: 0.343052 sec
Please type input size(n): 0

I then replaced your size - i with rand(), and added srand(time(0)); to the start of main():

static int *build_data(int *array, int size)
{
    array = malloc(sizeof(int) * size);
    for (int i = 0; i < size; i++)
    {
        array[i] = rand(); //size - i;
    }
    return array;
}

Running the alternative program, I got times like this:

Please type input size(n): 10000
Elapsed time: 0.001117 sec
Please type input size(n): 50000
Elapsed time: 0.007097 sec
Please type input size(n): 100000
Elapsed time: 0.015724 sec
Please type input size(n): 500000
Elapsed time: 0.095657 sec
Please type input size(n): 1000000
Elapsed time: 0.191383 sec
Please type input size(n): 5000000
Elapsed time: 1.214821 sec
Please type input size(n): 10000000
Elapsed time: 2.684908 sec
Please type input size(n): 10000000
Elapsed time: 2.716862 sec
Please type input size(n): 10000000
Elapsed time: 2.739099 sec
Please type input size(n): 0

These times are far longer than the times for the reverse sequence numbers. The times are also growing faster than linearly — not dramatically so, but definitely faster. And the difference is between subtraction and calling rand() is not the source of the trouble. I also created a version like this:

static int *build_data(int *array, int size)
{
    array = malloc(sizeof(int) * size);
    unsigned long random_sum = 0;
    for (int i = 0; i < size; i++)
    {
        array[i] = size - i;
        random_sum += rand();
    }
    printf("Random sum: %lu\n", random_sum);
    return array;
}

and an example output was:

Please type input size(n): 10000
Random sum: 10730036823932
Elapsed time: 0.000380 sec
Please type input size(n): 50000
Random sum: 53866916004733
Elapsed time: 0.001351 sec
Please type input size(n): 100000
Random sum: 107321572319270
Elapsed time: 0.002879 sec
Please type input size(n): 500000
Random sum: 536869931129596
Elapsed time: 0.015761 sec
Please type input size(n): 1000000
Random sum: 1073512237256859
Elapsed time: 0.034148 sec
Please type input size(n): 5000000
Random sum: 5370226579401372
Elapsed time: 0.170608 sec
Please type input size(n): 10000000
Random sum: 10737805324344696
Elapsed time: 0.357169 sec
Please type input size(n): 10000000
Random sum: 10735216573040655
Elapsed time: 0.350111 sec
Please type input size(n): 10000000
Random sum: 10739807847077051
Elapsed time: 0.349979 sec
Please type input size(n): 0

Slower, yes; there's an extra printf() required all else apart. But not as dramatically slower as the random data.

Answer 2

I guess we are comparing different things here. Time complexity and time taken to run a program is different. Time complexity can be simply said as asymptotic behavior of running time as input size tends to infinity.

Now you are saying that it is saying that it is following O(n). I guess you are looking that the two inputs and considering the multipicative increment in the time. It might be possible that your algorithm is running in An^1.5+bn+C cycles. So first of all you can't compare...exactly. You can say as input increases it would be asymtotically nearer to a function which is proprtionate to n^1.5.

Direct correlation between program run time and complexity is not what you should look for. Rather you can consider that from the basic oprations done in the program.

If you think that we can consider time complexity from running time entirely then I guess we need not have to consider those basic operations and all that.