Sorting algorithms - Relocation Counter

Question

I want to count the total relocations for each of these sorting algorithms. From the results it seems my code is correct, but I need someone to confirm it. Is the counter variable placed in the right position?

int bubblesort(int *p)
{
        int i,j,temp,relocations=0;
        for(i=1;i<N;i++)
                for(j=N-1;j>=i;j--)
                        if(p[j-1]>p[j])
                        {
                                temp=p[j-1];
                                p[j-1]=p[j];
                                p[j]=temp;
                                relocations++;
                        }
        return relocations;
}

int straightSelection(int *p)
{
        int k,i,min,j,relocations=0;
        for(i=0;i<N-1;i++)
        {
                k=i;
                min=p[i];
                for(j=i+1;j<N;j++)
                {
                        if(p[j]<min)
                        {
                                k=j;
                                min=p[j];
                        }
                }
                p[k]=p[i];
                p[i]=min;
                relocations++;
        }
        return relocations;
}

int straightInsertion(int *p)
{
        int x,i,j,relocations=0;
        for(i=2;i<=N;i++)
        {
                x=p[i];
                p[0]=x;
                j=i-1;
                while(x<p[j])
                {
                        p[j+1]=p[j];
                        j=j-1;
                        relocations++;
                }
                p[j+1]=x;
                relocations++;
        }
        return relocations;
}

int quicksort(int left, int right, int *p)
{
        int relocations=0;
        int i,j,mid,x,temp;

        if(left<right)
        {
                i=left;
                j=right;
                mid=(left+right)/2;
                x=p[mid];
                while(i<j)
                {
                        while(p[i]<x)
                                i++;
                        while(p[j]>x)
                                j--;
                        if(i<j)
                        {
                                if(p[i]==p[j])
                                {
                                        if(i<mid)
                                                i++;
                                        if(j>mid)
                                                j--;
                                }
                                else
                                {
                                        temp=p[i];
                                        p[i]=p[j];
                                        p[j]=temp;
                                        relocations++;
                                }
                        }
                }
                relocations += quicksort(left,j-1,p);
                relocations += quicksort(j+1,right,p);
        }
        return relocations;
}

Answer 1

Your quicksort has a bug

Your midpoint calculation can overflow for large arrays:

mid=(left+right)/2;

Consider the following example code (C++ but it applies to C as well):

int x = std::numeric_limits<int>::max()/2 + 1;
unsigned int y = (x + x)/2;
cout<<"x:"<<x<<" y:"<<y<<endl; // x:1073741824 y:3221225472

The correct way to calculate this is like this:

mid = left + (right - left)/2;

which will not overflow if right>left for any right and left.