Естественная сортировка с qsort не работает - PullRequest
Новая
       11

Естественная сортировка с qsort не работает

0 голосов
/ 24 мая 2018

Я пытаюсь отсортировать массив вершин, программа, которую мне нужно сделать, состоит в том, чтобы раскрасить вершины из разных графов, чтобы сделать это более эффективно, мы используем разные порядки для запуска жадных алгоритмов, моя проблема в том, когда я пытаюсь упорядочитьих в порядке возрастания, я использую qsort (), и по некоторым причинам он не работает на некоторых графиках, и я не могу понять, почему, я оставлю ниже структуру вершины, функцию сравнения, а также функцию Iиспользую для проверки сортировки массива.Вершина сравнивается по имени (nombre по-испански)

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

График: 

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

График

1 Ответ

0 голосов
/ 25 мая 2018

Я не совсем уверен, почему ваш оригинал не работал, предполагая, что int имеет тот же размер, что и int32_t для вашего компилятора.Если vertice1->nombre меньше vertice2->nombre, то результатом vertice1->nombre-vertice2->nombre будет большое значение без знака, которое выходит за пределы диапазона для 32-разрядного int.Большинство компиляторов просто отображают значения вне диапазона на отрицательные числа, хотя фактический результат определяется реализацией.

При вычитании значений unsigned int «отрицательная» разница в конечном итоге будет иметь большую unsigned int значение, выходящее за пределы диапазона int, поэтому результат будет определяться реализацией.Для функции сравнения qsort или bsearch используется только знак (положительный, отрицательный или нулевой) возвращаемого значения, поэтому можно избежать результата, определенного реализацией, всегда возвращая -1 для "отрицательного"разница, 1 для «положительной» разницы, или 0 для без разницы.Для этого есть (как минимум) три способа: -

  1. с использованием if операторов: 

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

  2. с использованием условного оператора: 

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

  3. с использованием разницы сравнений: 

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

    (это самый «умный» из 3 вариантов, хотя, возможно, и не самый ясный).

Если qsort или bsearch хотят, чтобы значения были в обратном порядке, то просто измените порядок переменных или измените операторы сравнения.

...