Help needed in quicksorting an array of pointers to structures

rocky1986's Avatar
Light Poster
Hello, I'm trying to sort an array of pointer to structures. The structures look like this:

Code:
typdef struct
{
   double coord[3];

}vector;

Here's my program. Pretty much every thing is standard as what we do in quicksort except that there is a entity called axis. axis is nothing but an index into the coord array. It can take values 0, 1, 2. MY doubt is as follows:

I tried to make left, right, i, j as size_t or even unsigned long and the program abruptly terminated (it failed). Why is this happening ? Please help me out this problem has bothered me for long and has weared me out totally. Is there a flaw in my algo ? If yes, please can you suggest me a better one ?

Code:
void quicksort(vector **parent_vpa,  long left,  long right, int axis)
{
    long i, j;
    vector *pivotpoint;
    vector *tempstore;

    if (left < right)
    {
        i = left;
        j = right;

        pivotpoint = parent_vpa[(left+right)/2];
    
        while (i <= j)
        {
            while (parent_vpa[i]->coord[axis] < pivotpoint->coord[axis])
            {
                i++;
            }

            while (parent_vpa[j]->coord[axis] > pivotpoint->coord[axis])
            {
                j--;
            }
    
            if (i <= j)
            {
                tempstore = parent_vpa[i];
                parent_vpa[i] = parent_vpa[j];
                parent_vpa[j] = tempstore;
                i++;
                j--;              
            }
        }

        if (left < j)
        {
            quicksort(parent_vpa, left, j, axis);
        }
    
        if (i < right)
        {
            quicksort(parent_vpa, i, right, axis);
        }
    }
    else
        return;
}

Last edited by shabbir; 1Jul2008 at 07:32.. Reason: Code block
0
rocky1986's Avatar
Light Poster
sorry heres the code with tags:

Code:
void quicksort(vector **parent_vpa, long left, long right, int axis)
{
long i, j;
vector *pivotpoint;
vector *tempstore;

if (left < right)
{
i = left;
j = right;

pivotpoint = parent_vpa[(left+right)/2];

while (i <= j)
{
while (parent_vpa[i]->coord[axis] < pivotpoint->coord[axis])
{
i++;
}

while (parent_vpa[j]->coord[axis] > pivotpoint->coord[axis])
{
j--;
}

if (i <= j)
{
tempstore = parent_vpa[i];
parent_vpa[i] = parent_vpa[j];
parent_vpa[j] = tempstore;
i++;
j--;
}
}

if (left < j)
{
quicksort(parent_vpa, left, j, axis);
}

if (i < right)
{
quicksort(parent_vpa, i, right, axis);
}
}
else
return;
}
0
aali's Avatar, Join Date: Jul 2008
Go4Expert Member
Why don't try this code?
Code:
void QuickSort(int start, int end, int arr[])
{
     if (start >= end)
        return;
        
    int p = (start + end) / 2;
    
    int i = start;
     int  j = end;
    
    while (i<j)
    {
          while(arr[i]<arr[p] && i<p)
             i++;
          while(arr[j]>arr[p] && j>p)
             j--;
          
        int  temp = arr[i];
          arr[i] = arr[j];
          arr[j] = temp;
          if (p == j )
          {
             p = i;
             j--;
          }
          else
              if (p==i)
              {
                 p = j;
                 i++;
              }
              else
              {
                  i++;
                  j--;
              }
    }
    
    QuickSort(start, p-1, arr);
    QuickSort(p+1, end, arr);
}

Last edited by shabbir; 22Jul2008 at 21:56.. Reason: Code block