1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Help needed in quicksorting an array of pointers to structures

Discussion in 'C' started by rocky1986, Jun 30, 2008.

  1. rocky1986

    rocky1986 New Member

    Joined:
    Aug 16, 2006
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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 a moderator: Jul 1, 2008
  2. rocky1986

    rocky1986 New Member

    Joined:
    Aug 16, 2006
    Messages:
    6
    Likes Received:
    0
    Trophy Points:
    0
    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;
    }
     
  3. aali

    aali New Member

    Joined:
    Jul 16, 2008
    Messages:
    18
    Likes Received:
    0
    Trophy Points:
    0
    Occupation:
    student
    Location:
    Riyadh
    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 a moderator: Jul 22, 2008

Share This Page