How to sort an array of pointers with a pointer to NULL?-CodePudding

I tried to implement a bubble sort of array of pointers, from greatest to least value that they point to, basically I have to put a pointer to NULL in the middle of the elements (second cell), and when I try to sort them, I want the NULL pointer to be put to the last position of the cell (2) and the other ones to be in order except for this one that is put to the last position. But this gives me a segmentation fault:

typedef struct example{
     int data;
}exp;

exp *arr[3];

static void sort_arr(exp *[]);

int main(){
 
 arr[0] = malloc(sizeof(*arr[0]));
 arr[0]->data = 1;

 arr[1] = NULL;

 arr[2] = malloc(sizeof(*arr[2]));
 arr[2]->data = 2;

 sort_arr(arr);

 return 0;
}

static void sort_arr(exp *pass_arr[]){
    for (int i = 0; i < 3; i  )
    {
        for (int j = i   1; j < 3;   j)
        {
            if (pass_arr[i]->data < pass_arr[j]->data)
            {
                exp *temp = pass_arr[i];
                pass_arr[i] = pass_arr[j];
                pass_arr[j] = temp;
            }
        }
    }
    return;
}

CodePudding user response：

You need to check whether an array element is NULL, and treat it as lower than the other value.

            if (pass_arr[i] == NULL || 
                (pass_arr[j] != NULL && pass_arr[i]->data < pass_arr[j]->data))
            {
                exp *temp = pass_arr[i];
                pass_arr[i] = pass_arr[j];
                pass_arr[j] = temp;
            }

CodePudding user response：

Use a comparison function that is pointer-aware, something like

#define EQ  0
#define LT -1
#define GT  1

static int cmp( x *exp, y *exp )
{
  if ( x == NULL && y == NULL ) return EQ ; // Two NULLs compare equal
  if ( x == NULL && y != NULL ) return GT ; // NULL compares high with respect to non-NULL
  if ( x != NULL && y == NULL ) return GT ; // NULL compares high with respect to non-NULL

  // if we get here both X and Y are non-null,
  // and so can safely be de-referenced

  if ( x->data < y->data ) return LT ;
  if ( x->data > y->data ) return GT ;

  // must be equal

  return EQ; 
}

Your test in your sort routine changes then from

if ( pass_arr[i]->data < pass_arr[j]->data )
. . .

if ( cmp( pass_arr[i] , pass_arr[j] ) < 0 )
. . .

CodePudding user response：

It is enough to change the if statement for example the following way

if ( pass_arr[j] != NULL && 
     ( pass_arr[i] == NULL || pass_arr[i]->data < pass_arr[j]->data ) )

This is better than this condition

if (pass_arr[i] == NULL || 
    (pass_arr[j] != NULL && pass_arr[i]->data < pass_arr[j]->data))

because in the last case there can be redundant swaps of two null pointers.