Slauncha

Le programme suivant est un exemple d'implémentation du tri rapide (quick sort) en utilisant des pointeurs de fonctions.

Un tri se décompose souvent en trois parties - une comparaison qui détermine l'ordre des deux objets quelconques, une permutation qui permet de les échanger le cas échéant et un algorithme de tri qui effectue les comparaisons et permutations jusqu'à ce que les objets soient dans l'ordre voulu. L'algorithme de tri est indépendant des opérations de comparaison et de permutation ; ainsi en utilisant différentes fonctions de comparaison et de permutation, on peut s'arranger pour trier suivant différents critères. C'est l'approche que nous allons utilisée dans notre exemple.

pfunction sera capable d'effectuer une comparaison lexicographique entre deux lignes (réalisée par strcmp) ou une comparaison selon la valeur numérique de deux lignes (réalisé par numcmp via le flag -n).

Code source du fichier : pfunction.c

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

/* nombre de lignes max a trier */
#define MAXLIGNES 5000

/* longueur max des lignes en entree */
#define LGRMAX 1000
/* pointeurs sur les lignes de texte */
char *p_line[MAXLIGNES];

int readLines(char *p_line[], int nlines);
void writeLines(char *p_line[], int nlines);
void quicksort(void *p_line[],
               int left,
               int right,
               int (*comp)(void*, void*));
int numcmp(char *, char *);


/* numcmp : compare numeriquement s1 et s2 */
int numcmp(char *p1, char *p2)
{
    double v1, v2;
    v1 = atof(p1);
    v2 = atof(p2);
    if (v1 < v2) {
        return -1;
    } else if (v1 > v2) {
        return 1;
    } else {
        return 0;
    }
}

void swap(void *v[], int i, int j)
{
    void * temp;
    temp =v[i];
    v[i] = v[j];
    v[j] = temp;
}

int readLine(char s[], int lim)
{
    int c, i;

    for (i=0; i<lim-1 && (c=getchar()) != EOF && c!='\n'; i++)
        s[i] = c;
    if ( c == '\n') {
        s[i++] = c;
    }
    s[i] = '\0';
    return i;
}

/* readLines : lit les lignes en entree */

int readLines(char *p_line[], int iline)
{
    int lgr, nlin;
    char *p, line[LGRMAX];

    nlin = 0;
    while ((lgr = readLine(line, LGRMAX)) > 0) {
        if (nlin >= iline || (p = malloc(lgr)) == NULL) {
            return -1;
        } else {
            line[lgr-1] = '\0';
            /* supprime le caractere de fin de ligne */
            strcpy(p,line);
            p_line[nlin++] = p;
        }
    }
    return nlin;
}

/* writeLines : ecrit les lignes en sortie */
void writeLines(char *p_line[], int nlin)
{
    int i;
    for (i=0; i < nlin; i++) {
        printf("%s\n", p_line[i]);
    }
}

/* quicksort : trie v[left] ... v[right]
    dans l'ordre croissant */
void quicksort(void *v[], int left, int right,
               int (*comp)(void *, void *))
{
    int i, last;
    void swap(void *v[], int, int);

    if (left >= right) {
        /* ne rien faire si le tableau contient
         moins de deux elements */
        return;
    }
    swap(v, left, (left+right)/2);
    last = left;
    for (i = left+1; i<= right; i++) {
        if ((*comp)(v[i], v[left]) < 0) {
            swap(v, ++last, i);
        }
    }
    swap(v, left, last);
    quicksort(v, left, last-1, comp);
    quicksort(v, last+1, right, comp);
}



/* trie les lignes en entree */
int main(int argc, char *argv[])
{
    /* nombre de lignes lues en entree */
    int nlines;
    /* 1 si tri numerique */
    int numeric = 0;
    if (argc > 1 && strcmp(argv[1], "-n") == 0) {
        numeric = 1;
    }

    if ((nlines = readLines(p_line, MAXLIGNES)) >= 0) {
        printf("Lancement tri sur %i\n", nlines);

        quicksort( (void **)p_line, 0, nlines-1,
                   (int (*)(void *, void *))
                   (numeric ? numcmp : strcmp) );
 
        printf("Liste triee\n");
        /* decommentez la ligne suivante pour utiliser 
         le tri quicksort natif */
        /* qsort(p_line, nlines, sizeof(*p_line), 
           numeric ? numcmp : strcmp); */

        writeLines(p_line, nlines);
        return 0;
    } else {
        printf("Entree trop grande pour trier\n");
        return 1;
    }

}

  pfunction.c

  Exécution

$gcc pfunction.c -o pfunction
$chmod +x pfunction
$./pfunction -n
ou
$./pfunction

Le programme attends la saisie utilisateur :

• si le flag -n a été renseigné : la saisie devra être constituée de valeurs numériques suivit de touche entrée
• si aucun flag est présent : la saisie devra être constituée de valeurs alphanumériques suivit de touche entrée

Dans tous les cas, la saisie se termine en renseignant EOF (ctrl+d).
 

• Avec le flag -n de renseigné

12
5
199
1487
0
6
-3
4
Liste triee
-3
0
4
5
6
12
199
1487

• Aucun flag de renseigné

monkey
pig
fly
bee
fish
dog
cat
Liste triee
bee
cat
dog
fish
monkey
pig