qsort 的自然排序不起作用

Question

我正在尝试对顶点数组进行排序，我需要编写的程序是对来自不同图形的顶点进行着色，为了更有效地这样做，我们使用不同的顺序运行贪心，我的问题是当我尝试按升序排列它们时，我正在使用 qsort() 并且由于某种原因它在某些图形上不起作用而且我不明白为什么，我将留在顶点结构下方，比较函数以及我用来检查数组的函数是否已排序。正在按名称（西班牙语名称）比较顶点

类型定义：

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

顶点：

/* 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 */
};

图表：

/* 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*/
};

比较函数：

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;
}

排序：

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

最后我检查它是如何排序的：

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);
}

我在终端上运行时从 1 个特定图表中得到的结果：

2 4294965727

0

The Graph

Answer 1

假设 int 与编译器的 int32_t 大小相同，我不完全确定为什么您的原始文件不起作用。如果您的 vertice1->nombre 小于 vertice2->nombre，那么 vertice1->nombre-vertice2->nombre 的结果将是一个超出 32 位 int 范围的大无符号值。大多数编译器只会将超出范围的值映射为负数，尽管实际结果是实现定义的。

当减去 unsigned int 值时，"negative" 差异最终会变成一个较大的 unsigned int 值，该值超出了 int 的范围，因此结果将由实现定义。对于 qsort 或 bsearch 比较函数，仅使用返回值的符号（正、负或零），因此始终返回 [=24= 可以避免实现定义的结果] 表示 "negative" 差异，1 表示 "positive" 差异，或 0 表示无差异。有（至少）三种方法可以做到这一点：–

使用 if 语句：

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

使用条件运算符：
```
result = a > b ? 1 : (a < b ? -1 : 0);
```
使用比较差异：
```
result = (a > b) - (a < b);
```
（这是3个选项中的"cleverest"，虽然可能不是最清楚的）。

如果 qsort 或 bsearch 想要倒序的值，那么只需倒转变量的顺序或倒转比较运算符。

qsort 的自然排序不起作用

Natural sort with qsort not working

c

qsort