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;
}

• JS1: Seems like the insertion sort "relocation" should be 1/2 the cost of the other ones because it only stores 1 item instead of 2 for a swap. But it's up to you to decide what you are measuring.

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.