0
\$\begingroup\$

enter image description here

I have already addressed this issue and corrected something .really..now the graph looks different

Please tell me if the program works correctly?You can see the results in the picture above.I will be grateful if you find any mistakes (if there are any, of course..) /I'm just not sure if the average number of swaps and comps is calculated correctly.I thought that with this sort there should be fewer of them, but the data obtained from the classic Insertion sort is not much different.Maybe that's how it should be, which is why I'm asking./

Thank you all in advance

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

    
    int main(int argc, char *argv[]) {
    
        FILE *f=fopen("stat18.csv","w");
        int n=100;
        int i,s;
        while (n<=10000){
        int st=0;
        for (s=0;s<5;s++)
        {
            int *a;
            a=(int *)malloc(n*sizeof(int));
            srand(time(NULL));
            int k;
            for (k=0;k<n;k++)
            {
                *(a+k)=rand()%50;
            }
            int j,comps,swaps;
            swaps=0;
            comps=0;
        int rem = a[0];
        a[0] = -1;
        
        for( i = 2, j; i < n; i++)
        {
            int x = a[i];
            j = i;
            while(j > 1 && a[j-1] > x)
            {
                comps += 2;
                swaps++;
                a[j] = a[j-1];
                j--;
            }
            comps += 2;
            a[j] = x;
        }
        a[0] = rem;
        for(i = 0; i < n-1; i++)
        {
            if(a[i] > a[i+1])
            {
                comps++;
                swaps++;
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
            comps++;
            i++;
        }
        st+=swaps + comps;  
        free(a);
    }
            
        st=st/5;
        fprintf(f,"%d ; %d\n", n , st);
        if (n<1000){
            n+=100;}
        else {n+=1000;} 
        }
        fclose(f);
        return 0;
    }
\$\endgroup\$
5
  • \$\begingroup\$ Welcome to the Code Review Community. Please be aware that the `Code must be working to the best of knowledge of the author. We aren't supposed to check for correctness. The point of the Code Review Community is to help you improve your coding skills. \$\endgroup\$ – pacmaninbw Mar 10 at 13:19
  • \$\begingroup\$ @pacmaninbw, part of reviewing code is to spot mistakes, isn't it? \$\endgroup\$ – Toby Speight Mar 10 at 13:27
  • \$\begingroup\$ I don't understand what your first paragraph and the chart are for - could you give some explanation? \$\endgroup\$ – Toby Speight Mar 10 at 13:31
  • 2
    \$\begingroup\$ @TobySpeight I didn't down vote or VTC, the problem I see is the lack of confidence in the question. \$\endgroup\$ – pacmaninbw Mar 10 at 14:18
  • \$\begingroup\$ The lack of documentation, lucid comments and structure in the code presented is amplified by non-helpful code layout/indentation. This puts an uncalled for burden on readers of this code just to identify the parts you state interest in. For all I can tell, the first loop, checking j to stay "inside array a", orders a initialised to pseudo-random values; the second starts with that pre-ordered array. Array size and accumulated (averaged?!) operation totals get printed - what results do you expect, and why? \$\endgroup\$ – greybeard Mar 11 at 7:20
1
\$\begingroup\$

Random seeding

        srand(time(NULL));

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

        srand(invocation_time);

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.

Calling 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.

Readability

            *(a+k)=rand()%50;

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.

Consistent indentation

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.

Counting

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;
                swaps++;
                a[j] = a[j-1];
                j--;
            }
            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];

or

            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])
            {
                comps++;
                swaps++;
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
            }
            comps++;
            i++;
        }

Comparing

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.