quicksort and struct...need help please.

[filadon]

I have a problem making my quicksort function recursive. If you look at the bolded lines, you will see that the function is taking three args instead of one. I have tried all i know but I still can't figure out a way to make it work.

typedef struct _qs_data
{
long *arr; /* array of long integers */
long left; /* left-most idx used in cur. invocation */
long right; /*right-most idx used in cur. invocation */
long depth; /* depth of recursion */
} qs_data;

/* Quicksort function. */
void quicksort ( struct _qs_data *data )
{
/*struct _qs_data *val1;
struct _qs_data *val2;*/
long pivot;
long leftIndex = data->left;
long rightIndex = data->right;

pivot = data->arr[data->left];

while ( data->left < data->right)
{
while((data->arr[data->right] >= pivot) && (data->left < data->right))
data->right--;
if (data->left != data->right)
{
data->arr[data->left] = data->arr[data->right];
data->left++;
}
while ((data->arr[data->left] <= pivot) && (data->left < data->right))
data->left++;
if (data->left != data->right)
{
data->arr[data->left] = data->arr[data->right];
data->right--;
}
}
data->arr [data->left] = pivot;
pivot = data->left;
data->left = leftIndex;
data->right = rightIndex;
if(data->left < pivot)
quicksort(data->arr, data->left, pivot-1);//problem with the number of args
if(data->right > pivot)
quicksort(data->arr, pivot+1, data->right);//same prob here
}

[Adak]

First, Welcome to the forum, Filadon!

Second: Always paste your code between code tags (you get them by highlighting your code, and clicking on the # icon in the forum editor).

Third: yes, Quicksort needs the left and right side index so it knows what it's sorting in each recursive call.

[filadon]

k I will do that in the future. thanks. But as u see I need to pass one arg to the recursive lines. I tried creating a new struct variable <Var1> to put all the three args <Var1>(data->arr, data->left, pivot-1) in it so I pass it as a single variable to quicksort(Var1); but it didn't work. Not sure if I was doing it wrong.
struct _qs_data Var1 -> (data->arr, data->left, pivot-1);

[Adak]

k I will do that in the future. thanks. But as u see I need to pass one arg to the recursive lines. I tried creating a new struct variable <Var1> to put all the three args <Var1>(data->arr, data->left, pivot-1) in it so I pass it as a single variable to quicksort(Var1); but it didn't work. Not sure if I was doing it wrong.
struct _qs_data Var1 -> (data->arr, data->left, pivot-1);

you also need data->right and pivot + 1, I believe.

[filadon]

yea I need that too.

[nimitzhunter]

here's that code in codetag for easy read:

typedef struct _qs_data
{
long *arr; /* array of long integers */
long left; /* left-most idx used in cur. invocation */
long right; /*right-most idx used in cur. invocation */
long depth; /* depth of recursion */
} qs_data;

/* Quicksort function. */
void quicksort ( struct _qs_data *data )
{
/*struct _qs_data *val1;
struct _qs_data *val2;*/
long pivot;
long leftIndex = data->left;
long rightIndex = data->right;

pivot = data->arr[data->left];

while ( data->left < data->right)
{
while((data->arr[data->right] >= pivot) && (data->left < data->right))
data->right--;
if (data->left != data->right)
{
data->arr[data->left] = data->arr[data->right];
data->left++;
}
while ((data->arr[data->left] <= pivot) && (data->left < data->right))
data->left++;
if (data->left != data->right)
{
data->arr[data->left] = data->arr[data->right];
data->right--;
}
}
data->arr [data->left] = pivot;
pivot = data->left;
data->left = leftIndex;
data->right = rightIndex;
if(data->left < pivot)
quicksort(data->arr, data->left, pivot-1);//problem with the number of args
if(data->right > pivot)
quicksort(data->arr, pivot+1, data->right);//same prob here
}

[nimitzhunter]

make your function call to be

void quicksort(data, left, right);

instead of bury the left and and right inside your structure. left/right doesn't have to tag along with the array.

then,

pivot = data->arr[data->left];
...
pivot = data->left;

pivot should not be an element of arr. you don't need so many while loop. Here's what i would do for quicksort

void quicksort(data, left, right)
if ( left < right)
   pivot = left - 1; 
   for( j = left; j<right;++j)
        if(data[j] <= data[right])
           swap(data[++pivot],data[j]);
 
   swap(data[++pivot],data[j]);
   quicksort(data,left,pivot-1);
   quicksort(data,pivot+1,right);

[filadon]

Hey nimitzhunter, I see what you mean but i am going to be using pthreads to implement the quicksort function hence the structure. Life would be much easier if I use one arg. Hopefully this is a good explanation of where am going with this program.

[nimitzhunter]

I don't think you can achieve recursion if you keep using satellite data in struct because each call to quick sort function will alter the value of left and right.

data->left++

I'm not familiar with pthreads, so can't comment about that.

[filadon]

I don't think you can achieve recursion if you keep using satellite data in struct because each call to quick sort function will alter the value of left and right.

data->left++

I'm not familiar with pthreads, so can't comment about that.

But from what i have read in regards to structures, the value in the struct remains the last written value to the struct variable...just like regular variables only that they exist within a struct.