When I try to execute the following code, it results in Segmentation error. Using online GDB the program simply stops working after the first call of partition function. The program never undergoes recursion and stops working right after partition()
is invoked.
#include <stdio.h>
int partition(int arr[], int len)
{
int pivot = len / 2;
int left = 0;
int right = len - 1;
int temp;
while (right != 0 || left !=0)
{
if (right != pivot)
{
if (arr[right] < arr[pivot])
{
temp = arr[right];
arr[right] = arr[pivot];
arr[pivot] = temp;
pivot = right;
}
else right--;
}
else
{
if (arr[left] > arr[pivot])
{
temp = arr[left];
arr[left] = arr[pivot];
arr[pivot] = temp;
pivot = left;
}
else left ;
}
}
return pivot;
}
void quicksort(int arr[], int len)
{
if (len > 1)
{
int pivot = partition(arr, len);
quicksort(arr, pivot);
quicksort(arr pivot 1, len-pivot-1);
}
}
int main()
{
int arr[] = {1,6,3,2,9,5,4,7,8};
quicksort(arr, 9);
for (int i =0; i< 9; i )
{
printf("%d ", arr[i]);
}
return 0;
}
For some reason when partition function is called the variables pivot, left, right are all initialized with garbage values.
Please Help.
CodePudding user response:
Your primary while
condition, (right != 0 || left !=0)
, is flawed. All it takes is one lower-bound bump via else left '
and that condition will be perma-true, eventually leading to segment breach.
Rather, you want to collapse right and left until such time as they reach common ground. Ex: while (right > left)