Sortiere ein Array von ganzen Zahlen lexikografisch

Question

Ich verwende qsort(), um ein 2D-Array von ganzen Zahlen lexiographisch zu sortieren, wobei jede Zeile eine Eingabe ist, aber Probleme mit Zeigerarithmetik beim Überqueren einer Zeile im Array hat.

Idee ist, jede Spalte in einer Zeile in eine Zeichenfolge zu verketten, und strcmp mit anderen Zeichenfolgen, die ähnlich aus anderen Zeilen berechnet werden.

Der Eingang ist nur auf positive ganze Zahlen beschränkt. Einige sortieren Beispiele unten,
{1, 1, 10} vor {1, 2, 0}
{3, 1, 5} vor {3, 11, 5}
{1, 19, 2} vor {1, 2, 1}

#define COL_SIZE 3 

int cmp_func (const void *a, const void *b) { 
    char str1[100], str2[100], temp[10]; 
    int i; 
    const int **ia = (const int **)a; 
    const int **ib = (const int **)b; 

    printf("(a: %p), (b: %p)\n", a, b); 
    str1[0] = '\0'; 
    str2[0] = '\0'; 

    for (i = 0; i < COL_SIZE; i++) { 
     printf("(ia+%d: %p), (ib+%d: %p)\n", i, (ia + i), i, (ib + i)); 
     sprintf(temp, "%d", (int)*(ia + i)); 
     strcat(str1, temp); 

     sprintf(temp, "%d", (int)*(ib + i)); 
     strcat(str2, temp); 
    } 

    printf("a: %s, b:%s\n", str1, str2); 
    return(strcmp(str1, str2)); 
} 

int main (void) { 
    int i, len; 
    int A[][COL_SIZE] = {{1,2,3}, 
         {1,1,5}, 
         {1,0,1}, 
         {1,2,1}, 
         {1,2,0}}; 

    len = sizeof(A)/sizeof(A[0]); 
    printf("sizeof(int): %ld, sizeof(int *): %ld\n", sizeof(int), sizeof(int *)); 

    for (i = 0; i < len; i++) { 
     printf("Address of A[%d][0]: %p\n", i, A[i]); 
    } 

    qsort(A, len, COL_SIZE * sizeof(int *), cmp_func); 
    return 0; 
} 

Unterhalb der Ausgang ist:

sizeof(int): 4, sizeof(int *): 8 
Address of A[0][0]: 0x7fff58e9fb30 
Address of A[1][0]: 0x7fff58e9fb3c 
Address of A[2][0]: 0x7fff58e9fb48 
Address of A[3][0]: 0x7fff58e9fb54 
Address of A[4][0]: 0x7fff58e9fb60 
(a: 0x7fff58e9fb30), (b: 0x7fff58e9fb48) 
(ia+0: 0x7fff58e9fb30), (ib+0: 0x7fff58e9fb48) 
(ia+1: 0x7fff58e9fb38), (ib+1: 0x7fff58e9fb50) 
(ia+2: 0x7fff58e9fb40), (ib+2: 0x7fff58e9fb58) 
a: 131, b:112 
(a: 0x7fff58e9fb48), (b: 0x7fff58e9fb60) 
(ia+0: 0x7fff58e9fb48), (ib+0: 0x7fff58e9fb60) 
(ia+1: 0x7fff58e9fb50), (ib+1: 0x7fff58e9fb68) 
(ia+2: 0x7fff58e9fb58), (ib+2: 0x7fff58e9fb70) 
Abort trap: 6 

Die Zeigerarithmetik für *(ia + 1) verursacht die Adresse in jedem Iteration zum Springen um 8 (sizeof(int *)) von 0x7fff58e9fb30 bis 0x7fff58e9fb38, wobei der nächste Wert in A [0] bei 0x7fff58e9fb34 (Größe von int) gespeichert wird.

Wie kann ich das beheben, so dass ich einen Offset von 4 statt 8 bekommen kann?

Answer 1

Sie ein Array von Arrays Sortierung, nicht ein Array von Zeigern. Folglich müssen Sie den Code in der Vergleichsfunktion bereinigen. Außerdem wandelt die aktuelle Inkarnation des Komparators alle Zahlen in Strings um, bevor irgendwelche Vergleiche durchgeführt werden. Es ist machbar und sinnvoll, eine Zahl in jeder Zeile gleichzeitig umzuwandeln und zu stoppen, wenn Sie einen Unterschied finden, indem Sie nur die nächste Zahl umrechnen, wenn die vorherigen gleich sind.

Dies führt zu dem folgenden Code, der für VLAs einen C99-Compiler oder einen C11-Compiler mit Unterstützung erfordert - variabler Länge Arrays - die in C99 obligatorisch sind aber optional in C11:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

static void dump_array(const char *tag, size_t n_rows, size_t n_cols, int A[n_rows][n_cols]); 

enum { COLS = 3 }; 

extern int cmp_func (const void *a, const void *b); 

int cmp_func(const void *va, const void *vb) 
{ 
    const int *a = *(const int (*)[COLS])va; 
    const int *b = *(const int (*)[COLS])vb; 

    for (int i = 0; i < COLS; i++) 
    { 
     char str1[20], str2[20]; 
     sprintf(str1, "%d", a[i]); 
     sprintf(str2, "%d", b[i]); 
     int rc = strcmp(str1, str2); 
     if (rc != 0) 
      return rc; 
    } 
    return 0; 
} 

int main(void) 
{ 
    int A[][COLS] = 
    { 
     { 1, 91, 10 }, 
     { 1, 9, 9 }, 
     { 1, 9, 11 }, 
     { 1, 1, 5 }, 
     { 1, 9, 10 }, 
     { 1, 0, 1 }, 
     { 1, 2, 3 }, 
     { 1, 91, 10 }, 
     { 1, 19, 0 }, 
     { 1, 91, 0 }, 
     { 1, 2, 0 }, 
     { 1, 2, 1 }, 
    }; 
    enum { ROWS = sizeof(A)/sizeof(A[0]) }; 

    dump_array("Before", ROWS, COLS, A); 
    qsort(A, ROWS, sizeof(A[0]), cmp_func); 
    dump_array("After", ROWS, COLS, A); 
    return 0; 
} 

static void dump_array(const char *tag, size_t n_rows, size_t n_cols, int A[n_rows][n_cols]) 
{ 
    printf("%s:\n", tag); 
    for (size_t r = 0; r < n_rows; r++) 
    { 
     const char *pad = "{"; 
     for (size_t c = 0; c < n_cols; c++) 
     { 
      printf("%s%3d", pad, A[r][c]); 
      pad = ","; 
     } 
     puts(" }"); 
    } 
} 

Die Zeiger übergeben cmp_func() sind Zeiger auf Arrays von COLSint s oder int (*)[COLS]; Die Zuordnungen zu a und b erzeugen ein Array int [COLS], das zu einem int * zerfällt. Normalerweise verwende ich v als Präfix für die const void * Argumente zu einem Komparator, und entfernen Sie die v für die Arbeitsvariablen in der Funktion.

Die Testdaten enthält es Prüfwerte aus dem Kommentar, und der Ausgang ist:

Before: 
{ 1, 91, 10 } 
{ 1, 9, 9 } 
{ 1, 9, 11 } 
{ 1, 1, 5 } 
{ 1, 9, 10 } 
{ 1, 0, 1 } 
{ 1, 2, 3 } 
{ 1, 91, 10 } 
{ 1, 19, 0 } 
{ 1, 91, 0 } 
{ 1, 2, 0 } 
{ 1, 2, 1 } 
After: 
{ 1, 0, 1 } 
{ 1, 1, 5 } 
{ 1, 19, 0 } 
{ 1, 2, 0 } 
{ 1, 2, 1 } 
{ 1, 2, 3 } 
{ 1, 9, 10 } 
{ 1, 9, 11 } 
{ 1, 9, 9 } 
{ 1, 91, 0 } 
{ 1, 91, 10 } 
{ 1, 91, 10 } 

Dieser Code zum code von RoadRunner ähnlich ist, unterscheidet sich aber in erster Linie in der einfacheren und effizienteren Vergleichsfunktion cmp_func() die konvertiert nicht unbedingt alle Zahlen in jeder Zeile jedes Mal in Zeichenfolgen, wenn zwei Zeilen verglichen werden. (In den Beispieldaten ist der erste Wert immer 1, daher werden mindestens zwei Zahlenpaare konvertiert. Dies ist jedoch wahrscheinlich nicht normal.)

Answer 2

Ich denke nicht, dass zum Verketten von ganzen Zahlen, dass Zeilen zu vergleichen, eine gute Idee ist. Im Allgemeinen können die resultierenden Strings unterschiedliche Größen haben. Zumindest müssen Sie führende Nullen zu jeder konvertierten Zahl hinzufügen, um die Zeichenfolgen auszurichten und Vorzeichen der ganzen Zahlen zu berücksichtigen.

Auch Sie falsch die Void-Zeiger dereferenzieren.

Und der Anruf der qsort ist falsch, obwohl es funktioniert, vorausgesetzt, dass sizeof(int *) gleich sizeof(int) ist.

qsort(A, len, COL_SIZE * sizeof(int *), cmp_func); 

Sie sind: Sie sollten

qsort(A, len, sizeof(int[COL_SIZE]), cmp_func); 

schreiben würde ich das Programm folgende Art und Weise

#include <stdlib.h> 
#include <stdio.h> 

#define COL_SIZE 3 

int cmp_rows(const void *a, const void *b) 
{ 
    const int *left = *(const int(*)[COL_SIZE])a; 
    const int *right = *(const int(*)[COL_SIZE])b; 

    for (size_t i = 0; i < COL_SIZE; i++) 
    { 
     if (left[i] < right[i]) return -1; 
     else if (right[i] < left[i]) return 1; 
    } 

    return 0; 
} 

int main(void) 
{ 
    int A[][COL_SIZE] = 
    { 
     { 1,2,3 }, 
     { 1,1,5 }, 
     { 1,0,1 }, 
     { 1,2,1 }, 
     { 1,2,0 } 
    }; 

    qsort(A, sizeof(A)/sizeof(*A), sizeof(int[COL_SIZE]), cmp_rows); 

    for (size_t i = 0; i < sizeof(A)/sizeof(*A); i++) 
    { 
     for (size_t j = 0; j < COL_SIZE; j++) printf("%d ", A[i][j]); 
     printf("\n"); 
    } 

    return 0; 
} 

Die Programmausgabe ist

1 0 1 
1 1 5 
1 2 0 
1 2 1 
1 2 3 

Answer 3

Das Problem ist hier schreiben Sagen Sie qsort() neu, um zu sortieren 'A', die 'len' (5) Items hat und jeder Item ist 3 * int's gross. Aber, A besteht aus int's, nicht * int's.

qsort(A, len, COL_SIZE * sizeof(int), cmp_func); 

Probieren Sie es aus.

Answer 4

In diesen beiden Zeilen:

const int **ia = (const int **)a; 
const int **ib = (const int **)b; 

Dies ist falsch, Sie benötigen nur einen * Zeiger, als Elemente in jeder Reihe gegen andere Reihen vergleichen.

const int *ia = (const int *)a; 
const int *ib = (const int *)b; 

Ferner dieser Linie:

Dieser geändert werden muss

qsort(A, len, COL_SIZE * sizeof(int *), cmp_func); 

Bedürfnisse geändert werden:

qsort(A, len, sizeof(*A), cmp_func); 

Der dritte Parameter nur in qsort erfordert eine Größe dessen, was es vergleicht. In diesem Fall die Größe jeder Zeile, die als sizeof(*A) oder sizeof(A[0]) ausgedrückt werden kann.

Darüber hinaus hat @Vlad aus Moskau einen besseren Ansatz, der keine Verkettung von Strings erfordert.

Wenn Sie noch einen String Ansatz verwenden möchten, können Sie dies versuchen:

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 

#define STRSIZE 100 
#define COL_SIZE 3 

int cmp_func(const void *a, const void *b) { 
    char str1[STRSIZE], str2[STRSIZE], temp[STRSIZE]; 
    size_t i; 

    const int *row1 = (const int *)a; 
    const int *row2 = (const int *)b; 

    *str1 = '\0'; 
    *str2 = '\0'; 

    for (i = 0; i < COL_SIZE; i++) { 
     sprintf(temp, "%d", row1[i]); 
     strcat(str1, temp); 

     sprintf(temp, "%d", row2[i]); 
     strcat(str2, temp); 
    } 

    return strcmp(str1, str2); 

} 

void print_array(int A[][COL_SIZE], size_t len) { 
    size_t row, col; 

    for (row = 0; row < len; row++) { 
     for (col = 0; col < COL_SIZE; col++) { 
      printf("%d ", A[row][col]); 
     } 
     printf("\n"); 
    } 
} 

int main(void) { 
    size_t len; 
    int A[][COL_SIZE] = {{1,2,0}, 
         {1,19,0}, 
         {1,19,0}, 
         {1,19,0}, 
         {1,2,0}}; 

    len = sizeof(A)/sizeof(*A); 

    printf("\nBefore:\n"); 
    print_array(A, len); 

    qsort(A, len, sizeof(*A), cmp_func); 

    printf("\nAfter:\n"); 
    print_array(A, len); 

    return 0; 
} 

Ausgang:

Before: 
1 2 0 
1 19 0 
1 19 0 
1 19 0 
1 2 0 

After: 
1 19 0 
1 19 0 
1 19 0 
1 2 0 
1 2 0