Comment trié un tableau dans c

Version imprimable

12/12/2017, 09h05
Ademgui

Comment trié un tableau dans c

J'aime bien savoir.
12/12/2017, 10h40
Kannagi

Réponse simple : qsort :p
12/12/2017, 11h35
ternel

Sinon, en le remplissant déjà trié. C'est souvent possible.

Ou encore, pas du tout, et ne pas s'obtiner à utiliser des données triées. C'est finalement assez rarement nécessaire.

Ca dépend surtout du contexte.
12/12/2017, 17h16
Sve@r

Sinon boucler sur chaque élément du tableau et le comparer avec son suivant. Si les deux ne sont pas à la bonne place, on les permute.
Et on recommence tout ça tant qu'on a au-moins une permutation. C'est l'algorithme du tri à bulles. Et ça marche aussi si, au lieu de comparer chaque élément avec son suivant, on compare chaque élément avec son précédent.
12/12/2017, 20h33
Christophe

Citation:

Et ça marche aussi si, au lieu de comparer chaque élément avec son suivant, on compare chaque élément avec son précédent.

et dans l'autre sens c'est le tri à plomb.

Tri à bulle
Tri à peigne
Quicksort

plusieurs tri en même temps

Bonjour,
je profite de la discussion pour poser une question.
Je cherche à faire le tri avec plusieur méthodes. Au final je dois comparer le temps d'exécution de chaque tri. Les tris doivent être fait sur des tableau à 500, 1000 et 10000 éléments avec une fois des tableaux initialisé aléatoirement et une autre avec des tableaux triés (c'est long !!! ouiii je sais ...).
Bref, ceci étant presque fait mais en fait je trouve une difficulté par rapport à la présentation des résultats. il nous est demandé de mettre les temps d’exécution obtenu dans un tableau . A cet effet, j'ai pensé faire une fonction qui calcul le temps d'exécution qui aura pour paramètre un pointeur (pointeur vers une fonction de tri ) et le tableau à trier.
Code:

1 2 3 4 5 6 7 8 9 10 11 double mesure_temps (*pointeur, tab) { clock_t debut, fin; double temps; debut=clock(); tri_insertion(appel de la fonction du tri souhaité) fin=clock() temps=((double)fin-debut); return temps; }
mais là je n'y arrive pas.
Quelqu'un aurait une solution à me proposer ??

Bien à vous ;) ;)

Merci

18/01/2018, 18h30
Sve@r
Bonjour

Citation:

Envoyé par RimaG

je profite de la discussion pour poser une question.

Généralement cela ne se fait pas. Mais bon, puisque ta question est un peu en rapport avec celle du PO (qui aurait pu, lui, avoir la politesse de revenir...)

Citation:

Envoyé par RimaG

A cet effet, j'ai pensé faire une fonction qui calcul le temps d'execution qui aura pour paramètre un pointeur (pointeur vers une fonction de tri ), et le tableau à trié.

Très bonne démarche. Mais cela suppose que toutes les fonctions de tri aient exactement la même signature

Donc si par exemple tu as différentes fonctions de tri, comme
void triA(int *, size_t);
void triB(int *, size_t);
void triC(int *, size_t);

Alors tu peux écrire ta fonction de mesure comme recevant un pointeur sur la fonction à exécuter, puis les paramètres de ladite fonction (ici du tableau à trier et le nb de ses éléments). Et la fonction, elle, se contentera d'exécuter la fonction en lui passant les paramètres attendus et en chronométrant le temps; sans même se préoccuper de quelle fonction elle exécute
Code:

1 2 3 4 5 6 double mesure_temps(void (*tri)(), int *tab, size_t n) { clock_t debut; debut=clock(); (*tri)(tab, n); return clock()-debut; }
Et tu peux même, pour pas te fatiguer la vie, mettre les fonctions de tri dans un tableau de fonctions que tu balayes ensuite pour les exécuter de façon successive
Code:

1 2 3 4 5 6 7 int main() { int tab={0, 1, 2, 3, 4, 5, 6} void (*fct[])()={triA, triB, triC, NULL}; void (**pt)(); for (pt=fct; *pt != NULL; pt++) printf("%lf\n", mesure_temps(*pt, tab, 7)); }
Ensuite, à chaque fois que tu crées une nouvelle fonction de tri, te suffit simplement de la rajouter dans le tableau et recompiler. Et pour éviter de te faire ch... à passer à chaque fois le nb d'éléments à tes fonctions, tu encapsules le tableau et sa taille dans une structure et c'est la structure que tu transmets aux fonctions...

Ce sont une excellente initiative et de très bons conseils de Sve@r, un programmeur compétent se doit de factoriser ce qui peut l'être.

Pour rebondir sur le message précédent, tu pourrais éventuellement pousser le zèle jusqu'à inclure l'implémentation de référence qsort dans la mesure ; par exemple :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
 
 
/* generic comparison function */
typedef int (*cmp_t)(
    const void *,
    const void *
);
 
/* generic sort function */
typedef void (*sort_t)(
    void *,
    size_t,
    size_t,
    cmp_t
);
 
typedef struct sortdef {
    const sort_t      sort;
    const char *const name;
} sortdef_t;
 
 
/* compares two integers */
int intcmp(const void *a, const void *b) {
    int i = *(const int *)a,
        j = *(const int *)b;
    return i < j ? -1 : (i > j);
}
 
 
void bubblesort(void *buf, size_t count, size_t size, cmp_t cmp) {
    // bubble-sorts the buffer..
}
 
void mergesort(void *buf, size_t count, size_t size, cmp_t cmp) {
    // merge-sorts the buffer..
}
 
void quicksort(void *buf, size_t count, size_t size, cmp_t cmp) {
    // quick-sorts the buffer..
}
 
 
/* returns CPU time used by specified sort function, in seconds */
double clock_sort(void *buf, size_t count, size_t size, cmp_t cmp, sort_t sort) {
	const clock_t start = clock();
	sort(buf, count, size, cmp);
	return ((double)clock() - start) / CLOCKS_PER_SEC;
}
 
 
#define ELEM_COUNT_MAX 100000
 
int main() {
    int source[ELEM_COUNT_MAX];
    const size_t count = sizeof source / sizeof *source;
 
    // initialize unsorted buffer
    srand(123456789);
    for (size_t i = 0; i < count; ++i)
        source[i] = rand();
 
    sortdef_t sorts[] = {
        { .sort =      qsort, .name = "stdlib's qsort" },
        { .sort = bubblesort, .name = "my bubble sort" },
        { .sort =  mergesort, .name =  "my merge sort" },
        { .sort =  quicksort, .name =  "my quick sort" }
    };
 
    printf("sorted %zu elements:\n", count);
    int data[ELEM_COUNT_MAX];
    for (size_t i = 0; i < sizeof sorts / sizeof *sorts; ++i) {
        memcpy(data, source, sizeof source); // reset buffer
        printf("  with %s in: %lf seconds\n",
               sorts[i].name,
               clock_sort(data, count, sizeof *data, intcmp, sorts[i].sort)
        );
    }
 
    return 0;
}

19/01/2018, 19h57
RimaG

Mercii pour vos réponses

J'ai suivi les conseils de Sve@r vu qu'ils font suites à mes idées. Après, j'ai comparé les resultats obtenus en utilisant les pointeurs de fonction avec un programme dans lequel j'ai place le clock debut et le clock de la fin avant/après chaque appel de fonction (sans passer par la fonction et les pointeurs) et j'ai trouvé des differences.
En faite avec la deuxième méthode les resulats sont plus preics me semble t il. PAr exemple, en utilisant les pointeurs, j'ai obtenu pour le Quick Sort un temps d'execution de 0 seconde dans tous les cas alors que avec la deuxieme methode une valeur de 0,112 secondes pour un tableau de 10 000 elts aléatoirement rempli.

Est l'utilisation des ppointeurs qui allège le programe et qui fait cette difference?

Sinon saviez vous si je peux renvoyer les resultats de mon programme vers un fichier sachant que je programme en C et sur Ubuntu

Mercii les developpeurs :D :D
20/01/2018, 08h40
Sve@r
Citation:

Envoyé par RimaG

J'ai suivi les conseils de Sve@r vu qu'ils font suites à mes idées.

Oui. Enfin ceux de Matt_Houston sont les mêmes mais plus détaillés...

Sinon ce genre d'écart de benchmark est difficile à apprécier. Ton ordi peut avoir un autre truc au moment où tu lances ton programme. Tu peux aussi lancer le même programme deux fois et avoir un second temps plus rapide parce que l'ordi a conservé le code dans sa RAM et n'a alors pas eu besoin de swapper. Et puis 10 000 valeurs c'est pas énorme pour un ordinateur...
Dans l'absolu, c'est sûr que passer un pointeur en plus c'est
- un paramètre en plus pour la fonction
- un déréférencement à exécuter (appeler triA(tab, nb) est un poil plus rapide qu'appeler (*fct)(tab, nb) car l'opération "étoile fct" a un coût)
Mais bon, est-ce que cela joue vraiment ici ? Après tout, dans le second cas, tous les tris ont le même handicap et toi, ton but est de les comparer l'un par rapport à l'autre.

Ceci dit, tu peux faire un test avec qsort car ses performances deviennent catastrophiques si le tableau est déjà trié mais à l'inverse de ce que tu veux. Si par exemple tu veux un tri croissant mais que ton tableau est intégralement trié en décroissant, alors qsort devient pire que le plus pourri des tris à bulles. Donc tu peux essayer ce cas là voir ce que ça donne dans tes valeurs...

Et enfin pour renvoyer le résultat d'un programme dans un fichier "toto" sur Unix/Linux, te suffit de lancer ./programme >toto. Et si tu veux le résultat dans "toto" et aussi à l'écran alors ./programme |tee toto
20/01/2018, 09h57
Christophe

Je rajouterais une autre information. Il est possible de gérer un arbre de tri. Sur le principe, ton tableau est en permanence trié, le "tri" étant effectué lors de l'ajout d'un élément.

J'ai trouvé ça sur DVP :
http://rmdiscala.developpez.com/cour...brechap4.6.htm

Le temps d'insertion dans le tableau est plus long, mais l'accès à l'information à posteriori est plus rapide.