Natural sort with qsort not working

Question

I am trying to sort an array of vertexes, the program I need to make is to color vertexes from different graphs, in order to do so more efficiently we use different orders to run greedy, my problem is when i try to order them in ascending order, I'm using qsort() and for some reason it doesn't work on some graphs and I can't understand why, I will leave below the structure of the vertex, the comparison function and also the function I'm using to check the array is sorted. The vertex are being compared by the name (nombre in spanish)

Typedefs:

typedef uint32_t u32; /* Definición de tipo u32 */
typedef struct _Vertice_t *PVertice;
typedef struct _Grafo_t *Grafo;

Vertex:

/* Definición de Estructura Vertice */
struct _Vertice_t {
    u32 nombre; /* Nombre real del vértice */
    u32 grado; /* Grado del vértice */
    u32 color; /* Color del vértice  */
    u32 index; /* Indice */
        u32 mem_vecinos;
        u32 tag;
        bool visitado;/*variable para saber el numero de componentes conexas*/
        u32 x_aleatorio;/* u32 para uso exclusivo en funcion orden aleatorio */
        u32 aleatorio; /* u32 para uso exclusivo en funcion orden aleatorio */
    u32 cant_de_colores; //uso exclusivo para orden bloque  == 1
    PVertice *vecinos; /* Vecinos del vértice */
};

Graph:

/* Definición de Estructura Grafo */
struct _Grafo_t {
    u32 nro_vertices; /* Cantidad de vértices del Grafo */
    u32 nro_lados; /* Cantidad de lados del Grafo */
    u32 nro_colores; /* Cantidad de colores usados para colorear el Grafo */
    PVertice vertices; /* Arreglo de Vértices del Grafo */
        bool *facil_busqueda;
    PVertice *orden; /* Arreglo indicador del orden de los vértices del Grafo*/
};

Comparison function:

int cmpfunc (const void * a, const void * b) {
    PVertice vertice_1 = *(PVertice*)a;
    PVertice vertice_2 = *(PVertice*)b;
  int resultado = ( vertice_1->nombre )-(vertice_2->nombre);
    return resultado;
}

Sorting:

void OrdenNatural(Grafo G) {
    qsort(G->orden, G->nro_vertices, sizeof(PVertice), cmpfunc);
}

Finally how I check it is sorted:

bool arrayIsSorted(PVertice *a, u32 n) {
  if ((n == 1) || (n == 0))
    return true;

  if (a[n-1]->nombre < a[n-2]->nombre) {
    printf("%u %u\n", a[n-1]->nombre, a[n-2]->nombre);
    return false;
  }

  return arrayIsSorted(a, n-1);
}

The result I get from 1 particular Graph when ran on terminal:

2 4294965727

0

The Graph

Answer 1

I'm not entirely sure why your original didn't work assuming int is the same size as int32_t for your compiler. If your vertice1->nombre is less than vertice2->nombre then the result of vertice1->nombre-vertice2->nombre will be a large unsigned value that is out of range for a 32-bit int. Most compilers will just map the out-of-range values to negative numbers although the actual result is implementation-defined.

When subtracting unsigned int values, a "negative" difference will end up as a large unsigned int value that is out-of-range for an int, so the result will be implementation-defined. For a qsort or bsearch comparison function, only the sign (positive, negative, or zero) of the returned value is used, so an implementation-defined result can be avoided by always returning -1 for a "negative" difference, 1 for a "positive" difference, or 0 for no difference. There are (at least) three ways to accomplish that :–

1. using if statements:

   if (a > b)
       result = 1;
   else if (a < b)
       result = -1;
   else
       result = 0;
   

2. using the conditional operator:

   result = a > b ? 1 : (a < b ? -1 : 0);
   

3. using difference of comparisons:

   result = (a > b) - (a < b);
   

   (this is the "cleverest" of the 3 options, although perhaps not the clearest).

If the qsort or bsearch wants the values in reverse order then just reverse the order of the variables or reverse the comparison operators.