Reputation: 1229
Hi I am using a sorting algorithm in one of my program. It is quick sort. I tested it with a sorted array as follow
int arr[7] = {1,2,3,4,5,6,7};
Code of sorting algorithm is
void sort(int arr[],int left,int right)
{
int i= left, j= right;
int pivot = arr[((left+right)/2)];
int tmp=0;
/* partition */
printf("%d\n",arr[0]);
while(i<=j)
{
while(arr[i]<pivot)
i++;
while(arr[j]>pivot)
j--;
if(i<=j)
{
tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--;
}
};
/* recursion */
if(left<j)
sort(arr,left,j);
if(i<right)
sort(arr,i,right);
}
When it return the result it gives arr[0] value as 0. which should be 1.
I am calling this function inside main. Below is the code for calling sort
int main()
{
int i;
int arr[7] = {1,2,3,4,5,6,7};int max=0,min=0;
int len = (sizeof(arr)/sizeof(arr[0]));
printf("%d\n",arr[0]);
sort(arr,0,len);
printf("%d\n",arr[0]);
return 0;
}
Upvotes: 0
Views: 69
Reputation: 225477
Here's your problem:
sort(arr,0,len);
You're passing the size as the rightmost array element. This results in you reading and writing off the end of the array, resulting in undefined behavior.
You need to pass in the index of the rightmost element, which is 1 less:
sort(arr,0,len-1);
Upvotes: 2
Reputation: 18865
The algorithm itself looks good, except I think it's better to have <= pivot
and >= pivot
in the while
loops.
The only issue I can think about is that you call the sort
function with arguments 0
and number of elements in the array. But note the right
here means the index of the right position, not behind. So it should be 7
or sizeof(arr)/sizeof(arr[0])-1)
Upvotes: 1