If possible, how can I improve the following quick sort(performance wise). Any suggestions?
void main()
{
quick(a,0,n-1);
}
void quick(int a[],int lower,int upper)
{
int loc;
if(lower<upper)
{
loc=partition(a,lower,upper);
quick(a,lower,loc-1);
quick(a,loc+1,upper);
}
}
/* Return type: int
Parameters passed: Unsorted array and its lower and upper bounds */
int partition(int a[],int lower,int upper)
{
int pivot,i,j,temp;
pivot=a[lower];
i=lower+1;
j=upper;
while(i<j)
{
while((i<upper)&&(a[i]<=pivot))
i++;
while((a[j]>pivot))
j--;
if(i<j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}//end while
if(pivot>a[j])
{
temp=a[j];
a[j]=a[lower];
a[lower]=temp;
}
return(j);
}//end partition
The quicksort algorithm is easily parallelized. If you have multiple cores to work with, you could see quite a bit of speed up. Depending on how large your data set is, it could easily provide you with more speed up than any other optimization. However, if you have only one processor or a relatively small data set, there won't be much of a speed up.
I could elaborate more if this is a possibility.