ordenar - array of strings c++

Cómo ordenar una matriz de cadenas alfabéticamente(distingue entre mayúsculas y minúsculas, intercalación no estándar)

Question

Necesito un código de lenguaje AC para ordenar algunas cadenas y debe distinguirse entre mayúsculas y minúsculas y para la misma letra en mayúsculas y minúsculas, la minúscula debe aparecer primero . Por ejemplo, el resultado del ordenamiento para las siguientes cadenas:

eggs
bacon
cheese
Milk
spinach
potatoes
milk
spaghetti

debiera ser:

bacon
cheese
eggs
milk
Milk
potatoes
spaghetti
spinach

He escrito un código pero el resultado que obtengo es:

Milk
bacon
cheese
eggs
milk
potatoes
spaghetti
spinach

No tengo idea de cómo mejorar esto y he buscado mucho. ¿Podría alguien ayudarme con esto?

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

int main(){
    char c;
    char name[20][10], temp[10];
    int count_name = 0;
    int name_index = 0;
    int i, j;

    while ((c = getchar()) != EOF){
        if (c == 10){
            name[count_name][name_index] = ''/0'';
            count_name++;
            name_index = 0;
        } else {
            name[count_name][name_index] = c;
            name_index++;
        }
    }

    for(i=0; i < count_name-1 ; i++){
        for(j=i+1; j< count_name; j++)
        {
            if(strcmp(name[i],name[j]) > 0)
            {
                strcpy(temp,name[i]);
                strcpy(name[i],name[j]);
                strcpy(name[j],temp);
            }
        }
    }

    for (i = 0; i < count_name; i++){
        printf("%s/n", name[i]);
    }
}

Answer 1

Mantenga las mismas palabras juntas ...

Para las listas de palabras, a menudo es más útil agrupar las "mismas" palabras (aunque difieran en el caso). Por ejemplo:

Keeping things together:          Simple "M after m":
------------------------          -------------------
mars                              mars
mars bar                          mars bar
Mars bar                          milk
milk                              milk-duds
Milk                              milky-way
milk-duds                         Mars bar
milky-way                         Milk
Milky-way                         Milky-way

Si quieres que las palabras estén ordenadas como la primera columna, te presento tres formas de hacerlo:

• Usando strcasecmp() combinado con strcmp() .
• Una implementación de paso único que realiza el seguimiento del tipo de carácter con isalpha() , tolower() e isupper() .
• Una implementación de un solo paso que utiliza una tabla de clasificación.

Al final discuto dos alternativas:

• Usando la tabla de clasificación para establecer un orden arbitrario.
• Configuración de la configuración regional para utilizar la clasificación basada en la configuración regional.

Usando las funciones de la biblioteca disponibles

Si es posible hacerlo, evite reinventar la rueda. En este caso, podemos hacerlo utilizando la función POSIX strcasecmp() para ver si son iguales con una comparación que no distingue entre mayúsculas y minúsculas, y strcmp() a strcmp() cuando lo son.

int alphaBetize (const char *a, const char *b) {
    int r = strcasecmp(a, b);
    if (r) return r;
    /* if equal ignoring case, use opposite of strcmp() result to get
     * lower before upper */
    return -strcmp(a, b); /* aka: return strcmp(b, a); */
}

(En algunos sistemas, la función de comparación que no distingue entre mayúsculas y minúsculas se llama stricmp() o _stricmp() . Si no tiene una disponible, a continuación se proporciona una implementación).

#ifdef I_DONT_HAVE_STRCASECMP
int strcasecmp (const char *a, const char *b) {
    while (*a && *b) {
        if (tolower(*a) != tolower(*b)) {
            break;
        }
        ++a;
        ++b;
    }
    return tolower(*a) - tolower(*b);
}
#endif

Evitando dos pasadas sobre las cuerdas.

A veces, las funciones existentes no funcionan lo suficientemente bien, y usted tiene que hacer algo más para hacer las cosas más rápido. La siguiente función realiza la comparación aproximadamente de la misma manera en una sola pasada, y sin usar strcasecmp() o strcmp() . Pero, trata a todos los caracteres no alfabéticos como menos que letras.

int alphaBetize (const char *a, const char *b) {
    int weight = 0;
    do {
        if (*a != *b) {
            if (!(isalpha(*a) && isalpha(*b))) {
                if (isalpha(*a) || isalpha(*b)) {
                    return isalpha(*a) - isalpha(*b);
                }
                return *a - *b;
            }
            if (tolower(*a) != tolower(*b)) {
                return tolower(*a) - tolower(*b);
            }
            /* treat as equal, but mark the weight if not set */
            if (weight == 0) {
                weight = isupper(*a) - isupper(*b);
            }
        }
        ++a;
        ++b;
    } while (*a && *b);
    /* if the words compared equal, use the weight as tie breaker */
    if (*a == *b) {
        return weight;
    }
    return !*b - !*a;
}

El uso de esta comparación para la clasificación mantendrá la milk y la Milk lado de la otra, incluso si la lista incluye los productos milk-duds .

Usando una tabla de clasificación

Aquí hay una forma de crear dinámicamente una tabla de clasificación a partir de una "configuración". Sirve para ilustrar una técnica de contraste para cambiar la forma en que se comparan las cadenas.

Puede mapear cómo se comparan las letras del alfabeto con un tipo de tabla simple que describe el orden relativo que desea que tengan las letras (o cualquier carácter, excepto el byte NUL):

const char * alphaBetical =
    "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";

A partir de este orden, podemos crear una tabla de consulta para ver cómo se comparan dos letras entre sí. La siguiente función inicializa la tabla si aún no se ha hecho primero y, de lo contrario, realiza la consulta de la tabla.

int alphaBeta_lookup (int c) {
    static int initialized;
    static char table[CHAR_MAX+1];
    if (!initialized) {
        /* leave all non-alphaBeticals in their relative order, but below
           alphaBeticals */
        int i, j;
        for (i = j = 1; i < CHAR_MAX+1; ++i) {
            if (strchr(alphaBetical, i)) continue;
            table[i] = j++;
        }
        /* now run through the alphaBeticals */
        for (i = 0; alphaBetical[i]; ++i) {
            table[(int)alphaBetical[i]] = j++;
        }
        initialized = 1;
    }
    /* return the computed ordinal of the provided character */
    if (c < 0 || c > CHAR_MAX) return c;
    return table[c];
}

Con esta tabla de consulta, ahora podemos simplificar el cuerpo del bucle de la función de comparación alphaBetize() :

int alphaBetize (const char *a, const char *b) {
    int ax = alphaBeta_lookup(*a);
    int bx = alphaBeta_lookup(*b);
    int weight = 0;
    do {
        char al = tolower(*a);
        char bl = tolower(*b);
        if (ax != bx) {
            if (al != bl) {
                return alphaBeta_lookup(al) - alphaBeta_lookup(bl);
            }
            if (weight == 0) {
                weight = ax - bx;
            }
        }
        ax = alphaBeta_lookup(*++a);
        bx = alphaBeta_lookup(*++b);
    } while (ax && bx);
    /* if the words compared equal, use the weight as tie breaker */
    return (ax != bx) ? !bx - !ax : weight;
}

¿Podemos hacer las cosas más simples?

Usando la tabla de clasificación, puede crear muchos ordenamientos diferentes con una función de comparación simplificada, como:

int simple_collating (const char *a, const char *b) {
    while (alphaBeta_lookup(*a) == alphaBeta_lookup(*b)) {
        if (*a == ''/0'') break;
        ++a, ++b;
    }
    return alphaBeta_lookup(*a) - alphaBeta_lookup(*b);
}

Usando esta misma función y modificando la cadena alphaBetical , puede lograr casi cualquier orden que desee (alfabético, alfabético inverso, vocales antes de consonantes, etc.). Sin embargo, la disposición de mantener unidas las palabras semejantes requiere intercalar palabras en mayúsculas con palabras en minúsculas, y esto solo puede hacerse haciendo una comparación que ignore el caso.

Tenga en cuenta que con la función simple_collating() anterior y la cadena alphaBetical que proporcioné, Bacon aparecerá antes que la milk , pero Mars irá después que la milk y antes que la Milk .

Si desea ordenar en función de su localidad.

Si desea utilizar una secuencia de clasificación que ya está definida para su configuración regional, puede establecer la configuración regional y llamar a la función de comparación de clasificación:

/*
 * To change the collating locale, use (for example):
       setlocale(LC_COLLATE, "en.US");
 */
int iso_collating (const char *a, const char *b) {
    return strcoll(a, b);
}

Ahora, al cambiar la configuración regional, el orden de clasificación se basará en una secuencia de clasificación estandarizada.

Answer 2

Aquí, si lo hago bien, quieres algo como lo describiría de la siguiente manera:

Se debe utilizar una clasificación que no distinga mayúsculas y minúsculas, donde bajo el empate, la condición de desempate "en minúscula es lo primero".

Así que es como

1. earlier_letter_in_the_alphabet < later_letter_in_the_alphabet ignorando el caso

2. lowercase < uppercase

3. shorter_word < wider_word
   • Esto no fue mencionado, lo tomé prestado del orden lexicográfico, el de los diccionarios.
   • Puede ser utilizado simplemente tomando ''/0'' como el más bajo posible en comparaciones

Paso 2 que debe tomarse solo si no distingo nada. El paso 3 ya se verificará con 1. Todo esto debe hacerse letra por letra, lo que significa que debe cambiar a 2 tan pronto como obtenga un empate entre los caracteres correspondientes, no solo cuando todas las cadenas estén vinculadas.

Suponiendo que esto era correcto, todo lo que tenemos que hacer ahora es escribir una función que haga esta comparación para nosotros para cualquiera de las dos cadenas dadas.

#include <ctype.h>  // for tolower and islower

int my_character_compare(const char a, const char b)
{
    int my_result;

    my_result = tolower(a) - tolower(b);
    // unless it is zero, my_result is definitely the result here
    // Note: if any one of them was 0, result will also properly favour that one


    if (my_result == 0 && a != b)
    // if (could not be distinguished with #1, but are different)
    {
        // means that they are case-insensitively same
        // but different...
        // means that one of them are lowercase, the other one is upper
        if (islower(a))
            return -1;  // favour a
        else
            return 1;   // favour b
    }


    // regardless if zero or not, my_result is definitely just the result
    return my_result;
}

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    my_result = my_character_compare(*a, *b);
    // unless it is zero, my_result is definitely the result here

    while (my_result == 0 && *a != 0)
    // current characters deemed to be same
    // if they are not both just 0 we will have to check the next ones
    {
        my_result = my_character_compare(*++a, *++b);
    }

    // whatever the my_result has been:
    //   whether it became != zero on the way and broke out of the loop
    //   or it is still zero, but we have also reached the end of the road/strings
    return my_result;
}

Una función de comparación, por convención / regla, debe devolver un valor negativo para favorecer que el primer parámetro esté al frente, un valor negativo para favorecer al segundo parámetro, cero si no puede distinguirlos. Solo una información adicional que probablemente ya conozca por la forma en que utiliza strcmp .

¡Y eso es! Reemplazar ese strcmp en su código con my_string_compare aquí, también my_string_compare estas definiciones que hemos hecho en la parte superior debe proporcionar un resultado correcto. De hecho, proporciona el resultado esperado para el ejemplo de entrada en cuestión.

Uno podría acortar las definiciones, por supuesto, las he hecho largas para que sea más fácil entender lo que está pasando. Por ejemplo, podría resumir todo lo siguiente:

#include <ctype.h>

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    while (*a || *b)
    {
        if ((my_result = tolower(*a) - tolower(*b)))
            return my_result;
        if (*a != *b)
            return (islower(*a)) ? -1 : 1;
        a++;
        b++;
    }

    return 0;
}

Esencialmente, hace lo mismo con el otro, puedes usar el que quieras; O incluso mejor, escribe uno.

Answer 3

Archivos de encabezado estándar requeridos por el programa:

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

El programa principal comienza aquí:

//Global Variables Required
//=========
const char *tgt[]={"bacon", "Bacon", "mIlk", 
        "Milk", "spinach", "MILK", "milk", "eggs"};    //Array for sorting
int tgt_size=8;                                        //Total Number of Records
int     SortLookupTable[128];                          //Custom sorting table
typedef int      cmp_t (const void *, const void *);




int main(int argc, char *argv[]) {
    printf("Before sort:/n/n");
    int n=0;
    for(n=0; n<tgt_size; n++)
        printf("%s/n", tgt[n]);

    CreateSortTable();

    myQsort(tgt, tgt_size, sizeof(char *), &compare);
    printf("/n/n====/n/n");
    for(n=0; n<tgt_size; n++)
        printf("%s/n", tgt[n]);

    return 0;
}

Tabla de clasificación personalizada según sea necesario:

void CreateSortTable(void){
    int     i;
    for (i = 0; i < 128; i++){
        SortLookupTable[i] = 0;
    }
    char *s;
    s=(char *)malloc(64);
    memset(s, 0, 64);
    strcpy(s, "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");

    i=1;
    for (; *s; s++){
        SortLookupTable[(int) ((unsigned char) *s)]=i;
        i++;
    }
}

Algoritmo de clasificación rápida, también puede utilizar la biblioteca estándar proporcionada:

//Some important Definations required by Quick Sort
=======
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || /
    es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

#define swap(a, b)                          /
    if (swaptype == 0) {                    /
        long t = *(long *)(a);              /
        *(long *)(a) = *(long *)(b);        /
        *(long *)(b) = t;                   /
    } else                                  /
        swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n)    if ((n) > 0) swapfunc(a, b, n, swaptype)


#define swapcode(TYPE, parmi, parmj, n) {       /
    long i = (n) / sizeof (TYPE);               /
    register TYPE *pi = (TYPE *) (parmi);       /
    register TYPE *pj = (TYPE *) (parmj);       /
    do {                                        /
        register TYPE   t = *pi;                /
        *pi++ = *pj;                            /
        *pj++ = t;                              /
        } while (--i > 0);                      /
}

#define min(a, b)   (a) < (b) ? a : b


//Other important function
void swapfunc(char *a, char *b, int n, int swaptype){
    if(swaptype <= 1)
        swapcode(long, a, b, n)
    else
        swapcode(char, a, b, n)
}

char * med3(char *a, char *b, char *c, cmp_t *cmp){
    if ( cmp(a, b) < 0){
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){

                return c;
            }else{
                return a;
            }
        }
    }else{
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){
                return a;
            }else{
                return c;
            }
        }
    }
}

//Custom Quick Sort

void myQsort(void *a, unsigned int n, unsigned int es, cmp_t *cmp){
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    int d, r, swaptype, swap_cnt;

loop:   SWAPINIT(a, es);
    swap_cnt = 0;
    if (n < 7) {
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es){
                swap(pl, pl - es);
            }
        return;
    }
    pm = (char *)a + (n / 2) * es;
    if (n > 7) {
        pl = a;
        pn = (char *)a + (n - 1) * es;
        if (n > 40) {
            d = (n / 8) * es;
            pl = med3(pl, pl + d, pl + 2 * d, cmp);
            pm = med3(pm - d, pm, pm + d, cmp);
            pn = med3(pn - 2 * d, pn - d, pn, cmp);
        }
        pm = med3(pl, pm, pn, cmp);
    }
    swap(a, pm);
    pa = pb = (char *)a + es;

    pc = pd = (char *)a + (n - 1) * es;
    for (;;) {
        while (pb <= pc && (r = cmp(pb, a)) <= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pa, pb);
                pa += es;
            }
            pb += es;
        }
        while (pb <= pc && (r = cmp(pc, a)) >= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pc, pd);
                pd -= es;
            }
            pc -= es;
        }
        if (pb > pc)
            break;
        swap(pb, pc);
        swap_cnt = 1;
        pb += es;
        pc -= es;
    }
    if (swap_cnt == 0) {  /* Switch to insertion sort */
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
                 pl -= es)
                swap(pl, pl - es);
        return;
    }

    pn = (char *)a + n * es;
    r = min(pa - (char *)a, pb - pa);
    vecswap(a, pb - r, r);
    r = min(pd - pc, pn - pd - es);
    vecswap(pb, pn - r, r);
    if ((r = pb - pa) > es)
        myQsort(a, r / es, es, cmp);
    if ((r = pd - pc) > es) {
        /* Iterate rather than recurse to save stack space */
        a = pn - r;
        n = r / es;
        goto loop;
    }
}

Dos de las funciones más importantes son:

unsigned char Change(char a){
    return (unsigned char ) SortLookupTable[(int)a];
}


int compare (const void *a, const void *b){
    char *s1= *(char **)a;
    char *s2= *(char **)b;
    int ret, len, i;
    ret=0;

    if (strlen((void*)s1) > strlen((void*)s2)){
        len=strlen((void*)s1);
    }else{
        len=strlen((void*)s2) ;
    }

    for(i=0; i<len; i++){
        if ( s1[i] != s2[i]){
            if ( Change(s1[i]) < Change(s2[i]) ){
                ret=0;
                break;
            }else{
                ret=1;
                break;
            }
        }
    }

    return ret;
}

Answer 4

La clave del código OP es el uso de la función strcmp() para comparar dos cadenas.
Entonces, comenzaré reemplazando esta función estándar por otra, como la siguiente:

  // We assume that the collating sequence satisfies the following rules:
  // ''A'' < ''B'' < ''C'' < ...
  // ''a'' < ''b'' < ''c'' < ...
  // We don''t make any other assumptions.

  #include <ctype.h>      
  int my_strcmp(const char * s1, const char * s2)
  {
      const char *p1 = s1, *p2 = s2;
      while(*p1 == *p2 && *p1 != ''/0'' && *p2 != ''/0'')
          p1++, p2++;  /* keep searching... */

      if (*p1 == *p2)
         return 0;
      if (*p1 == ''/0'')
         return -1;
      if (*p2 == ''/0'')
         return +1;

      char c1 = tolower(*p1),      c2 = tolower(*p2);
      int  u1 = isupper(*p1) != 0, u2 = isupper(*p2) != 0;
      if (c1 != c2)
        return c1 - c2;  // <<--- Alphabetical order assumption is used here 
      if (c1 == c2)
        return u1 - u2;
  }

Las últimas líneas se pueden compactar de esta manera:

     return (c1 != c2)? c1 - c2: u1 - u2;

Ahora, al reemplazar strcmp() por my_strcmp() tendrás el resultado deseado.

En un algoritmo de clasificación es una buena idea pensar por separado los 3 aspectos principales:

• La función de comparación.
• El algoritmo de ordenamiento abstracto que utilizaremos.
• La forma en que los datos se "mueven" en la matriz cuando se deben intercambiar dos elementos.

Estos aspectos se pueden optimizar de forma independiente.
Por lo tanto, por ejemplo, una vez que tenga la función de comparación bien establecida, el siguiente paso de optimización podría ser reemplazar el algoritmo de clasificación doble por uno más eficiente, como quicksort .
En particular, la función qsort() de la biblioteca estándar <stdlib.h> proporciona dicho algoritmo, por lo que no necesita preocuparse por la programación.
Finalmente, la estrategia que utilice para almacenar la información de la matriz podría tener consecuencias en el rendimiento.
Sería más eficiente almacenar cadenas como "array of pointers to char" en lugar de "array of array of char", ya que intercambiar punteros es más rápido que intercambiar dos arreglos completos de caracteres.

Arreglos de punteros

NOTA ADICIONAL: Los tres primeros if() son en realidad redundantes, porque la lógica de las siguientes oraciones implica el resultado deseado en el caso de que *p1 o *p2 sea ​​0. Sin embargo, al mantener esas if() ''s, El código se vuelve más legible.

Answer 5

Llego tarde a esta discusión, y no tengo ninguna expectativa en particular de participar y ganar el fabuloso premio, pero no veo una solución con los modismos que miraría primero, pensé.

Mi primer pensamiento al leer la especificación del problema fue alguna forma de secuencia de clasificación personalizada, que básicamente encontré en @ jxh''s Usando una noción de tabla de clasificación . No veo la insensibilidad a los casos como un concepto central, solo la ordenación extraña.

Por lo tanto, ofrezco el siguiente código únicamente como una implementación alternativa. Es específico de glibc ( se usa qsort_r (3)) , pero se siente como un enfoque más liviano y admite muchas secuencias de clasificación en tiempo de ejecución. Pero está ligeramente probado, y es muy probable que me falten varias debilidades. Entre los cuales: No he prestado especial atención a Unicode o al mundo de los caracteres anchos en general, y los lanzamientos a caracteres sin firmar para evitar subíndices de matrices negativas se sienten sospechosos.

#include <stdio.h>
#include <limits.h>

/*
 * Initialize an index array associated with the collating
 * sequence in co. The affected array can subsequently be
 * passed in as the final client data pointer into qsort_r
 * to be used by collating_compare below.
 */
int
collating_init(const char *co, int *cv, size_t n)
{
    const unsigned char *uco = (const unsigned char *) co;
    const unsigned char *s;
    size_t i;

    if (n <= UCHAR_MAX) {
        return -1;
    }
    for (i = 0; i < n; i++) {
        /* default for chars not named in the sequence */
        cv[i] = UCHAR_MAX;
    }
    for (s = uco; *s; s++) {
        /*
         * the "collating value" for a character''s own
         * character code is its ordinal (starting from
         * zero) in the collating sequence. I.e., we
         * compare the values of cv[''a''] and cv[''A''] -
         * rather than ''a'' and ''A'' - to determine order.
         */
        cv[*s] = (s - uco);
    }

    return 0;
}

static int
_collating_compare(const char *str1, const char *str2, int *ip)
{
    const unsigned char *s1 = (const unsigned char *) str1;
    const unsigned char *s2 = (const unsigned char *) str2;

    while (*s1 != ''/0'' && *s2 != ''/0'') {
        int cv1 = ip[*s1++];
        int cv2 = ip[*s2++];

        if (cv1 < cv2) return -1;
        if (cv1 > cv2) return 1;
    }

    if (*s1 == ''/0'' && *s2 == ''/0'') {
        return 0;
    } else {
        return *s1 == ''/0'' ? -1 : 1;
    }
}

int
collating_compare(const void *v1, const void *v2, void *p)
{
    return _collating_compare(*(const char **) v1,
                              *(const char **) v2,
                              (int *) p);
}

Lo anterior está cerca del código que podría colocarse en un módulo o biblioteca independiente, pero carece de su propio archivo de encabezado (o entrada en un archivo de encabezado). Mi propia prueba simplemente concatena el código de arriba y abajo en un archivo llamado custom_collate_sort.c, y usa

gcc -DMAIN_TEST -Wall -o custom_collate_sort custom_collate_sort.c

... para compilarlo.

#if defined(MAIN_TEST)

/* qsort_r is a GNU-ey thing... */

#define __USE_GNU
#include <stdlib.h>
#include <string.h>

#define NELEM(x) (sizeof x / sizeof 0[x])

static int
cmp(const void *v1, const void *v2)
{
    return strcmp(*(const char **) v1, *(const char **) v2);
}

static int
casecmp(const void *v1, const void *v2)
{
    return strcasecmp(*(const char **) v1, *(const char **) v2);
}

int
main(int ac, char *av[])
{
    size_t i;

    int cval[256], ret;
    int cval_rev[256], rret;

    char *tosort[] = {
        "cheeSE", "eggs", "Milk", "potatoes", "cheese", "spaghetti",
        "eggs", "milk", "spinach", "bacon", "egg", "apple", "PEAR",
        "pea", "berry"
    };

    ret = collating_init("aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVxXyYzZ",
                         cval, NELEM(cval));

    rret = collating_init("ZzYyXxVvUuTtSsRrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa",
                          cval_rev, NELEM(cval_rev));

    if (ret == -1 || rret == -1) {
        fputs("collating value array must accomodate an index of UCHAR_MAX/n", stderr);
        return 1;
    }

    puts("Unsorted:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s/n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], cmp);

    puts("Sorted w/ strcmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s/n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], casecmp);

    puts("Sorted w/ strcasecmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s/n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval);

    puts("Sorted w/ collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s/n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval_rev);

    puts("Sorted w/ reversed collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s/n", tosort[i]);
    }

    return 0;
}

#endif /* MAIN_TEST */

Answer 6

Puedes escribir una función de comparación personalizada para ordenar.

Primero, mira el orden por defecto de strcmp :

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

const char *tgt[]={
    "bacon", "Bacon", "mIlk", "Milk", "spinach", "MILK", "milk", "eggs"
};
int tgt_size=8;

static int cmp(const void *p1, const void *p2){
    return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int main(int argc, char *argv[]) {
    printf("Before sort:/n/t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    qsort(tgt, tgt_size, sizeof(char *), cmp);

    printf("/nAfter sort:/n/t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    return 0;
}

strcmp ordena por código de caracteres ASCII; es decir, ordena AZ luego az para que todas las AZ en mayúscula aparezcan antes de cualquier palabra con una letra minúscula:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    Bacon MILK Milk bacon eggs mIlk milk spinach 

Podemos escribir nuestra propia función de comparación usada en cmp usada en qsort que ignora el caso. Eso se parece a esto:

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == ''/0'')
            return 0;
    return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);
} 

Asegúrese de cambiar también cmp a:

static int cmp(const void *p1, const void *p2){
    return mycmp(* (char * const *) p1, * (char * const *) p2);
}

La versión que ignora el caso ahora se imprime:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs Milk MILK milk mIlk spinach 

Esta es la misma salida que obtendría con la función POSIX strcasecmp .

La función mycmp primero compara lexicográficamente en orden normal [a|A]-[z|Z] . Esto significa que obtendrás palabras iguales, pero puedes obtener bacon, Bacon tan probable como Bacon, bacon . Esto se debe a que qsort no es una clasificación estable y ''Bacon'' se compara con ''bacon''.

Ahora lo que queremos es si la comparación es 0 mientras se ignora el caso (es decir, la misma palabra como ''LECHE'' y ''leche'') ahora se compara el caso incluido y se invierte el orden:

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;
    int sccmp=1;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == ''/0'')
            sccmp = 0;
    if (sccmp) return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);

    for (; *a == *b; a++, b++)
        if (*a == ''/0'')
            return 0;
    return ((*a < *b) ? +1 : -1);
}

Imprime la versión final:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs milk mIlk Milk MILK spinach 

Desafortunadamente, este enfoque se vuelve difícil de manejar para UNICODE. Para clasificaciones complejas, considere usar una asignación o una ordenación de varios pasos con una ordenación estable .

Para las intercalaciones alfabéticas complejas y de ubicación, considere las intercalaciones de Unicode . Como ejemplo, en diferentes ubicaciones, las letras se alfabetizan de manera diferente:

Swedish                      z < ö
                             y == w
German                       ö < z
Danish                       Z < Å
Lithuanian                   i < y < k
Tr German                    ä == æ
Tr Spanish                   c < ch < d   
German Dictionary Sort:      of < öf
German Phonebook Sort:       öf < of

Los valores predeterminados para estas distinciones se capturan en la Tabla de elementos de DUCET predeterminada de Unicode ( DUCET ) que proporciona una asignación predeterminada para las intercalaciones de UNICODE y las comparaciones de cadenas. Puede modificar los valores predeterminados para capturar la distinción entre la clasificación del diccionario y la clasificación de la guía telefónica, diferentes ubicaciones o tratamientos diferentes para cada caso. Las variaciones de ubicación individuales se rastrean activamente en el repositorio de datos de configuración regional común de Unicode ( CLDR ).

La recomendación para la clasificación de niveles múltiples es escalonada:

Level   Description           Examples
L1      Base characters       role < roles < rule
L2      Accents               role < rôle < roles
L3      Case/Variants         role < Role < rôle
L4      Punctuation           role < “role” < Role
Ln      Identical             role < ro□le < “role”

Una implementación ampliamente utilizada de las intercalaciones de Unicode se encuentra en la biblioteca de la UCI . La colación predeterminada de DUCET para varios ejemplos sería:

b < B < bad < Bad < bäd
c < C < cote < coté < côte < côté 

Puede explorar la biblioteca de ICU y cambiar las ubicaciones y los destinos con el ICU Explorer

Si desea implementar su propia versión de DUCET para las risitas, puede seguir el método general utilizado en este script de Python . No es abrumador, pero no trivial.