Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Help needed in quicksorting an array of pointers to structures (http://www.go4expert.com/forums/help-quicksorting-array-pointers-t11761/)

rocky1986 1Jul2008 02:38

Help needed in quicksorting an array of pointers to structures
 
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;
}


rocky1986 1Jul2008 02:41

Re: Help needed in quicksorting an array of pointers to structures
 
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;
}


aali 22Jul2008 14:17

Re: Help needed in quicksorting an array of pointers to structures
 
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);
}



All times are GMT +5.5. The time now is 21:13.