# Sorting algorithms - Relocation Counter

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

• 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. – JS1 May 8 '15 at 3:31

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