Page 250 - Programming Microcontrollers in C

Sorting Programs 235

calls++; /* count the number of times called */
depth++;
if(right > left)
{
swap(v+left, v+(right+left)/2); /* chose the
value at center to partition on */
value = left;
for(i=left+1; i<=right; i++)
if(v[i] < v[left])
swap(v+(++value), v+i);
swap(v+left, v+value); /* put the partition
element in place*/
quick_sort(v,left, value-1);
quick_sort(v,value+1,right);
}
if(depth>max_depth)
max_depth=depth;
depth=0;
}

void swap ( int *, int *);
void quick_sort(int v[ ], int left, int right) ;
#include <stdio.h>
int calls, depth, max_depth;
main()
{
int v[11]={81,99,23,808,3,77,18,27,128,360,550};
int i;
quick_sort(v, 0,11 -1);
for( i=0; i<11; i++)
printf(“%d “,v[i]);
printf(“\n”);
printf(“calls=%d\nmax_depth=%d\n”,calls,max_depth);
}

Note that the global variables calls and depth are incremented
each time quick_sort() is entered. When quick_sort() is
exited through its normal return procedure at the end of the routine,
depth is examined to determine if it is greater than max_depth .