Comment sortinger un tableau de chaînes par ordre alphabétique (classement sensible à la casse, non standard)

J’ai besoin de code de langage courant alternatif pour sortinger certaines chaînes et il devrait être sensible à la casse et pour la même lettre en majuscules et minuscules, les minuscules doivent venir en premier . Par exemple, le résultat du sorting pour les chaînes suivantes:

eggs bacon cheese Milk spinach potatoes milk spaghetti 

devrait être:

 bacon cheese eggs milk Milk potatoes spaghetti spinach 

J’ai écrit un code mais le résultat obtenu est le suivant:

 Milk bacon cheese eggs milk potatoes spaghetti spinach 

Je ne sais pas comment améliorer cela et j’ai beaucoup cherché. Quelqu’un pourrait-il m’aider avec ça?

 #include  #include  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 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]); } } 

Gardez les mêmes mots ensemble …

Pour les listes de mots, il est souvent plus utile de regrouper les “mêmes” mots (même s’ils diffèrent par la casse). Par exemple:

 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 vous voulez des mots arrangés comme la première colonne, je vous présente trois façons de le faire:

  • Utilisation de strcasecmp() associée à strcmp() .
  • Une implémentation en une seule passe suivant le type de caractère avec isalpha() , tolower() et isupper() .
  • Implémentation en une seule passe utilisant une table de classement.

À la fin, je discute de deux alternatives:

  • Utilisation de la table de classement pour établir un ordre arbitraire.
  • Définition des parameters régionaux pour qu’ils utilisent un classement basé sur les parameters régionaux.

Utilisation des fonctions de bibliothèque disponibles

Si possible, évitez de réinventer la roue. Dans ce cas, nous pouvons le faire en utilisant la fonction POSIX strcasecmp() pour voir si elles sont égales avec une comparaison ne strcasecmp() casse, et en nous strcmp() sur strcmp() quand elles le sont.

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

(Sur certains systèmes, la fonction de comparaison ne faisant pas la ssortingcmp() les majuscules et les minuscules est appelée ssortingcmp() ou _ssortingcmp() . Si cette _ssortingcmp() n’est pas disponible, une implémentation est fournie ci-dessous.)

 #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 

Eviter deux passages sur les cordes

Parfois, les fonctions existantes ne fonctionnent pas assez bien et vous devez faire autre chose pour accélérer les choses. La fonction suivante effectue la comparaison à peu près de la même manière en une seule passe, sans utiliser strcasecmp() ou strcmp() . Mais, il traite tous les caractères non alphabétiques comme étant inférieurs aux lettres.

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

L’utilisation de cette comparaison pour le sorting gardera le milk et le Milk l’un à côté de l’autre, même si la liste inclut les milk-duds .

Utiliser une table de classement

Voici un moyen de créer dynamicment une table de classement à partir d’une “configuration”. Il sert à illustrer une technique contrastive pour changer la façon dont les chaînes sont comparées.

Vous pouvez mapper la façon dont les lettres de l’alphabet sont comparées à une sorte de tableau simple qui décrit l’ordre relatif dans lequel vous voulez que les lettres (ou tout caractère sauf l’octet NUL) aient:

 const char * alphaBetical = "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ"; 

À partir de cet ordre, nous pouvons créer une table de correspondance pour voir comment deux lettres sont censées se comparer. La fonction suivante initialise la table si cela n’a pas déjà été fait en premier, sinon effectue la recherche de table.

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

Avec cette table de correspondance, nous pouvons maintenant simplifier le corps de la boucle de la fonction de comparaison 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; } 

Peut-on simplifier les choses?

À l’aide du tableau de classement, vous pouvez créer de nombreux classements différents avec une fonction de comparaison simplifiée, telle que:

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

En utilisant cette même fonction et en modifiant la chaîne alphaBetical , vous pouvez réaliser pratiquement tout ordre souhaité (alphabétique, alphabétique inverse, voyelles avant les consonnes, etc.). Cependant, pour garder les mêmes mots ensemble, il faut intercaler des mots en majuscules avec des mots en minuscules, et cela ne peut être fait qu’en effectuant une comparaison sans tenir compte de la casse.

Notez qu’avec la fonction simple_collating() ci-dessus et la chaîne alphaBetical j’ai fournie, Bacon viendra avant le milk , mais Mars ira après le milk et avant le Milk .

Si vous souhaitez effectuer un sorting en fonction de vos parameters régionaux.

Si vous souhaitez utiliser une séquence de classement déjà définie pour vos parameters régionaux, vous pouvez définir les parameters régionaux et appeler la fonction de comparaison de classement:

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

Maintenant, en modifiant les parameters régionaux, l’ordre de sorting sera basé sur une séquence de classement normalisée.

Vous pouvez écrire une fonction de comparaison personnalisée pour le sorting.

Tout d’abord, regardez l’ordre de sorting par défaut strcmp :

 #include  #include  #include  #include  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 

strcmp sortinge par code de caractère ASCII; c'est-à-dire qu'il sortinge AZ puis az sorte que tous les AZ majuscules passent avant tout mot avec une lettre minuscule

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

Nous pouvons écrire notre propre fonction de comparaison utilisée dans cmp utilisée dans qsort qui ignore la casse. Cela ressemble à ceci:

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

Assurez-vous également de changer cmp pour:

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

L'affaire ignorant la version est maintenant imprimée:

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

C'est la même sortie que vous obtiendriez avec la fonction POSIX strcasecmp .

La fonction mycmp compare d'abord le lexicographe dans l'ordre normal [a|A]-[z|Z] . Cela signifie que vous obtiendrez comme des lettres, mais vous obtiendrez peut-être du bacon, Bacon aussi probable que du Bacon, bacon . Cela est dû au fait que qsort n’est pas un type stable et que «bacon» est égal à «bacon».

Maintenant, ce que nous voulons, c'est si la comparaison est 0 tout en ignorant la casse (c'est-à-dire, le même mot comme «MILK» et «lait») comparent maintenant la casse incluse et inversent l'ordre:

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

La version finale imprime:

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

Malheureusement, cette approche devient difficile à manier pour UNICODE. Pour les sortings complexes, envisagez d'utiliser un mappage ou un sorting à plusieurs étapes avec un sorting stable .

Pour les classements alphabétiques complexes et tenant compte de l'emplacement, utilisez les classements Unicode . Par exemple, dans des endroits différents, les lettres alphabétiques différemment:

 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 

Les valeurs par défaut de ces distinctions sont consignées dans la table DUCET (Unicode Collation Element Table) qui fournit un mappage par défaut pour les classements UNICODE et les comparaisons de chaînes. Vous pouvez modifier les valeurs par défaut pour capturer la distinction entre le sorting par dictionnaire et le sorting dans le répertoire, des emplacements différents ou un traitement différent pour chaque cas. Les variations de localisation individuelles sont activement suivies dans le référentiel de données de localisations communes Unicode ( CLDR ).

La recommandation pour le sorting à plusieurs niveaux est hiérarchisée:

 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” 

Une implémentation largement utilisée des classements Unicode se trouve dans la bibliothèque ICU . Le classement DUCET par défaut pour plusieurs exemples serait:

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

Vous pouvez explorer la bibliothèque ICU et modifier les emplacements et les cibles avec ICU Explorer.

Si vous souhaitez implémenter votre propre version de DUCET for glires, vous pouvez suivre la méthode générale utilisée dans ce script Python . Ce n'est pas accablant, mais pas anodin.

La clé du code OP est l’utilisation de la fonction strcmp() pour comparer deux chaînes.
Je vais donc commencer par remplacer cette fonction standard par une autre, comme suit:

  // We assume that the collating sequence satisfies the following rules: // 'A' < 'B' < 'C' < ... // 'a' < 'b' < 'c' < ... // We don't make any other assumptions. #include  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; } 

Les dernières lignes peuvent être compactées de cette façon:

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

Maintenant, en remplaçant strcmp() par my_strcmp() vous obtiendrez le résultat souhaité.

Dans un algorithme de sorting, il est judicieux d’envisager séparément les 3 aspects principaux:

  • La fonction de comparaison.
  • L'algorithme de sorting abstrait que nous allons utiliser.
  • La manière dans ces données sera "déplacée" dans le tableau lorsque deux éléments doivent être échangés.

Ces aspects peuvent être optimisés indépendamment.
Ainsi, par exemple, une fois que la fonction comparisson est bien établie, la prochaine étape d'optimisation pourrait consister à remplacer l'algorithme de sorting pour sorting par un algorithme plus efficace, tel que quicksort .
En particulier, la fonction qsort() de la bibliothèque standard vous fournit un tel algorithme, vous n'avez donc pas besoin de le programmer.
Enfin, la stratégie que vous utilisez pour stocker les informations du tableau peut avoir des conséquences sur les performances.
Il serait plus efficace de stocker des chaînes telles que "tableau de pointeurs à caractère" au lieu de "tableau de tableau de caractères", car l'échange de pointeurs est plus rapide que l'échange de deux tableaux entiers de caractères.

Tableaux de pointeurs

NOTE ADDITIONNELLE: Les trois premiers if() sont en réalité redondants, car la logique des phrases suivantes implique le résultat souhaité dans le cas où *p1 ou *p2 vaut 0. Cependant, en conservant ceux de if() , le code devient plus lisible.

Ici, si je comprends bien, vous voulez quelque chose que je décrirais comme suit:

Un type non sensible à la casse dans lequel la condition de condition de départage «la minuscule vient en premier» doit être utilisée.

Alors c’est comme:

  1. earlier_letter_in_the_alphabet < later_letter_in_the_alphabet ignorant le cas

  2. lowercase < uppercase

  3. shorter_word < wider_word
    • Cela n'a pas été mentionné, je l'ai emprunté à l'ordre lexicographique, celui des dictionnaires
    • Peut être utilisé simplement en prenant '\0' comme le plus bas possible dans les comparaisons

Étape 2 à prendre que si 1 ne distingue rien. L'étape 3 sera déjà vérifiée avec 1. Toutes ces opérations doivent être effectuées lettre par lettre, ce qui signifie que vous devez passer à 2 dès que vous obtenez une égalité entre les caractères correspondants, pas seulement lorsque toutes les chaînes sont associées.


En supposant que cela soit correct, tout ce que nous avons à faire maintenant, c’est d’écrire une fonction qui effectue cette comparaison pour nous pour deux chaînes données.

 #include  // 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_ssortingng_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/ssortingngs return my_result; } 

Une fonction de comparaison, par convention / règle, doit renvoyer une valeur négative pour favoriser le premier paramètre devant, une valeur négative pour favoriser le deuxième paramètre, zéro si elle ne peut pas les distinguer. Juste une information supplémentaire que vous connaissez probablement déjà en utilisant strcmp .

Et c'est tout! Remplacer cette strcmp dans votre code par my_ssortingng_compare ici, my_ssortingng_compare également les définitions que nous avons données devrait fournir un résultat correct. En effet, il fournit le résultat attendu pour l'exemple de saisie en question.

Bien sûr, on pourrait raccourcir les définitions, je les ai faites longues pour qu'il soit plus facile de comprendre ce qui se passe. Par exemple, je pourrais tout résumer comme suit:

 #include  int my_ssortingng_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; } 

Fait essentiellement la même chose avec l’autre, vous pouvez utiliser ce que vous voulez; ou mieux encore, écrivez-en un.

Je suis en retard dans la discussion et je n’attends pas particulièrement de céder et de remporter le fabuleux prix, mais je ne vois pas de solution utilisant les idiomes que je rechercherais en premier, pensais que je pourrais en parler.

Ma première pensée en lisant la spécification du problème était une forme de séquence de classement personnalisée, que j’avais essentiellement trouvée dans Utilisation de la notion de tableau de classement de @ jxh. Je ne considère pas l’insensibilité à la casse comme un concept fondamental, mais simplement comme un ordre peu commun

Donc, je propose le code suivant uniquement comme une implémentation alternative. Elle est spécifique à la glibc – qsort_r (3) est utilisée – mais ressemble à une approche plus légère et prend en charge de nombreuses séquences d’assemblage au moment de l’exécution. Mais il a fait l’object de légers tests et il me manque très probablement plusieurs faiblesses. Parmi ceux-ci: Je n’ai prêté aucune attention particulière à Unicode ou au monde des caractères larges en général, et les conversions en caractères non signés pour éviter les indices de tableau négatifs semblent suspectes.

 #include  #include  /* * 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. Ie, 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); } 

La précédente est proche du code qui pourrait être placé dans un module ou une bibliothèque séparé, mais ne possède pas son propre fichier d’en-tête (ou une entrée dans un fichier d’en-tête). Mon propre test concatène simplement le code ci-dessus et ci-dessous dans un fichier nommé custom_collate_sort.c, et utilise

 gcc -DMAIN_TEST -Wall -o custom_collate_sort custom_collate_sort.c 

… pour le comstackr.

 #if defined(MAIN_TEST) /* qsort_r is a GNU-ey thing... */ #define __USE_GNU #include  #include  #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 */ 

Fichiers d’en-tête standard requirejs par programme:

 #include  #include  #include  

Le programme principal commence ici:

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

Tableau de sorting personnalisé selon les besoins:

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

Algorithme de sorting rapide, vous pouvez également utiliser la bibliothèque standard fournie:

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

Deux des fonctions les plus importantes sont:

 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