You call this inside a loop (or two loops actually). But here's the problem,
time returns the current number of seconds since an arbitrary historical point of time (1970 January 1st at midnight). Most of the time in your loop, that will be the same number. So you are seeding the number the same. But occasionally you will tick over to the next second.
You should either create a variable
time_t invocation_time = time(NULL);
that you can then use
Or just move that seeding call outside the loops.
You would create the variable if you want to always seed with the same number so you get the same "random" sequence each time. You could even set the value to something fixed rather than the current time. I just used the current time because that's what you had been using and I have no particular reason to prefer a different value. By creating the variable, you ensure that you will be seeding with the same value each time and will get the same sequence of numbers. You won't sometimes repeat and sometimes not, as you do now.
If you want a different sequence each time, then just seed the randomness once per invocation of your program. Repeated calls to
srand make things less random rather than more. You would only do this if you wanted to repeat the original results. And frankly, if that's what you wanted, it would probably be easier to just generate the data once and make a copy for each iteration.
srand once at the beginning of the program is the more typical approach. Calling it multiple times with the same value is an option if you want to make the values repeatable in some way. The way that you are doing it now is neither of those things. It is neither random nor repeatable. Sometimes it repeats and sometimes it is from a pseudorandom sequence. Which is somewhat unpredictable, although there likely would be patterns.
I think that what you want in this situation is to seed once at the beginning of the program, so you get different values in
a each time. But it really depends on exactly what you are trying to test.
It would be more common to write this
a[k] = rand() % 50;
Now we can easily see that you are doing an array dereference. It's also conceivable that this might have performance impact. Because iterating over an array is something that would be done frequently and might be optimized. Whereas pointer addition is rarer and might not be, even if identical in effect. But I still think that the primary reason to write it this way is that it is easier for people reading your code to see what's happening.
You will also notice that I added whitespace. This also makes it easier to see what things go together and what are different. The compiler will remove this during tokenization, so it has impact on the executable. But for the source code, it makes it easier for the person reading the code to figure out what it is doing.
Similarly, it will be easier to read your code if you always indent inside a block and reduce the indentation when the block ends. This makes it easier to see where your code starts and ends.
Now to get to the question that you were actually asking.
for( i = 2, j; i < n; i++)
int x = a[i];
j = i;
while(j > 1 && a[j-1] > x)
comps += 2;
a[j] = a[j-1];
comps += 2;
a[j] = x;
Whether this is counting the comparisons correctly or not depends on exactly what you want to count.
You are not counting a comparison
i < n that you are doing on each iteration of the outer loop. I would usually think of this as something that you should measure.
You are counting two comparisons on the failure of the inner loop even when only one is done. I.e. when
j is equal to 1, you count two comparisons even though short circuiting will only do the
j > 1 and not the
a[j-1] > x. Perhaps you want to count as if short circuiting does not occur.
In terms of swaps, you aren't counting either
int x = a[i];
a[j] = x;
but you are counting each
a[j] = a[j-1];
What's a swap? If it is an assignment, then you should count the first two. If it is an exchange, you should not count the last one, as it is not a swap. You are doing no "swaps" in that loop. You are moving a block of memory.
Note that what I'd actually call a swap involves three assignments (although it's quite possible that only two of them hit memory, as one can be held in a register). So if your improvement to insertion sort is that you are doing fewer assignments, you are counting the wrong thing. You should be counting assignments, not swaps.
for(i = 0; i < n-1; i++)
if(a[i] > a[i+1])
int temp = a[i];
a[i] = a[i+1];
a[i+1] = temp;
I'm having trouble understanding what you consider to be "classic" insertion sort and what your revision is. This would be easier to understand if you used functions. Then you could call each with the same data and compare those results. And for those of us reading your code, we could see what was different between the two functions.
That would also create more of a separation between your test setup and the sorting. As is, those things are pretty much run together. There isn't a clear demarcation between what is setup and what is sorting. If your sorting were entirely in functions, then it would be clearer. The stuff outside the functions is setup. The stuff inside is sorting.
It would also be easier if we could see the results from both the classic and revised versions. Perhaps they are showing data as expected. Perhaps not. Without the classic version, it's hard for me to see what you are trying to compare. So it's difficult to critique it.