Insertion Sort Algorithm on Reverse Ordered Array Costs 0.00000 seconds?

Question

I randomly created 30.000 number in array. then i sorted these numbers normally. After that, i reversed, and apply insertion sort algorithm. take a look;

 begin = clock();
 insertion(dizi, boyut);
 end = clock();

 printf("\n time cost: %f z... ", (double)(end - begin) / CLOCKS_PER_SEC);

when I print it says 0.000000 seconds, which is impossible. Where did i make wrong?

Here is my insertion sort code

void insertion(int dizi[], int boyut)
{
    int i, j, temp;

    for(i = 1; i < boyut; i++)
    {
        temp = dizi[i];
        j = i-1;
        while((temp < dizi[j] && j >= 0))
        {
            dizi[j+1] = dizi[j];
            j--;
        }
        dizi[j+1] = temp;
    }
}

my code probably has a mistake, and i cant see it. I need advice, thank u. — Muhammed Eminoglu, Mar 19 '17 at 18:04
check `j>=0` *before* `dizi[j]`... but that's not the problem you're looking for — Matt Timmermans, Mar 19 '17 at 18:48
http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array this answer is also true for reverse sorted arrays. — maraca, Mar 20 '17 at 02:36

score 1 · Answer 1 · answered Mar 19 '17 at 18:06

The mistake is subtle: the compiler observes that you do a bunch of writes to that array, but then never do anything with it, so it helpfully deletes that section to make your code run faster. In this case, much much faster.

To address this, after sorting the data, print a random element from the array, so that the data is "used". If a random element is printed, the compiler knows it needs to actually sort the whole array, and can't cheat.

Insertion Sort Algorithm on Reverse Ordered Array Costs 0.00000 seconds?

1 Answers1