[Eni PgM]

Voila je dois écrire une fonction qui trie une liste chainée entrée en paramètre en utilisant un tri autre que le "tri-bulle".

Voici les fichiers utilisés :

dns.c

Code:

#include "dns.h"
 
//fonction saisie
 
liste saisie()
{
liste L,temp;
int i,taille;
i=0;
 
srand(time(NULL));
printf("Saisir le nombre d'élément de la liste :\n");
scanf("%d",&taille);
 
while( i < (taille-1) )
{
		temp = (liste) malloc(sizeof(cellule));
		temp->element = rand()%100; //tire un nombre au hasard entre 0 et 99
		temp->suivant = L;
		L=temp;
		i++;
}
 
return L;
}
 
//fonction d'affichage
 
void affichage(liste L)
{
	 int i;
	 liste temp;
	 for(temp=L,i=0; temp!=NULL; temp=temp->suivant, i++)
	 {
		 printf("%d:%d",i,temp->element);
		 printf("\n");
	 }
}
 
//fonction tri bulle
 
liste tri_bulle(liste L)
{
 
}
 
 
//fonction tri 2
 
liste tri_2(liste L)
{
 
}

dns.h

Code:

#ifndef _dns_
#define _dns_
#include <stdio.h>
#include <time.h>
 
typedef struct cell 
{
int element;
struct cell *suivant;
};
 
typedef struct cell cellule;
typedef cellule* liste;
 
 
//prototypes des fonctions
 
liste saisie();
void affichage(liste);
liste tri_bulle(liste);
liste tri_2(liste);
#endif

testdns.c

Code:

#include "dns.h"
main()
{
liste L,L2;
L = saisie();
L2 = L;
 
printf("Liste non triée :\n");
affichage(L);
 
printf("Tri bulle :\n");
tri_bulle(L);
affichage(L);
 
printf("Tri 2 :\n"); 
tri_2(L2);
affichage(L2);
}

makefile

Code:

testdns : testdns.o dns.o dns.h
	 gcc -Wall -o testdns testdns.o dns.o
testdns.o : testdns.c
	 gcc -c testdns.c
dns.o : dns.c
	 gcc -c dns.c

J'aimerai donc que quelqu'un m'écrive une petite fonction tri_2 en me donnant l'algorythme du tri utilisé ( tri par ordre croissant et pas de tri bulle !)

Si vous repérez des fautes n'hésitez pas à me le signaler

D'avance Merci

['Bleys]

J't'aurais bien aidé mon chou mais c'est parti loin le C

[Mothra]

Fais un tri minmax. Ne comptes pas sur moi pour faire tes devoirs a ta place.

[Kathar - Alleria - Lango]

Le laboratoire n'est pas là pour que les gens fassent le boulot à ta place.
Tu pourras facilement trouver les différents algorithmes de tri en recherchant sur google : quicksort, heapsort (tri par tas), mergesort (tri fusion), ...

Si tu as besoin d'aide pour déterminer l'algorithme le mieux adapté à ton problème, tu peux en discuter ici, mais demander que l'on fasse ton boulot à ta place, c'est hors de question. Surtout que le faire serait anti-pédagogique.

['Bleys]

C'est sûr que c'est pas à lui que ça va poser un problème de conscience ..

[Eni PgM]

Je ne demande pas qu'on fasse mes devoirs à ma place, juste d'écrire une fonction soit une demi douzaine de lignes sachant que les tris autre que le bulle, dont je suis en train de coder la fonction, ne m'inspirent pas trop.

Je viens de sortir le code plus haut il est normal que j'en ai un peu marre

Pour le choix du tri il n'y a pas de contraintes, il faut juste trier dans l'odre croissant donc autant prendre le plus simple à coder.

[Mothra]

Minmax : dans un ensemble de n éléments, je parcours et je me souviens de l'emplacement du minimum et du maximum de l'ensemble. J'échange le minimum avec le premier, le maximum avec le dernier, j'itère sur l'ensemble de taille n - 2, je prend garde aux cas limites de l'ensemble a 1 ou 2 éléments.

Autrement, plutot que prendre le plus simple, tu peux prendre un avec une meilleure complexité, et esperer avoir une meilleure note.

[RisWaaq]

Encore plus simple, la méthode "humaine" :
je mémorise le premier élément et je parcours toute ma liste. A chaque fois que je tombe sur un élément plus petit (ou plus grand, ça dépend de l'ordre de tri), je mémorise celui-là plutôt que celui que j'avais.
Une fois le bout de la liste atteint, je sors l'élément mémorisé et je le place en début d'une nouvelle liste.

Je recommence avec une liste de N-1 éléments, je ressors le plus petit (ou le plus grand) et je le place derrière l'élément de ma liste d'1 éléments.

[Eni PgM]

Je vais peut etre me laisser tenter par ce dernier, enfin ce weekend car la je sature merci.

[mlouk]

J'ai trouvé cette manière de faire mais il y en à d'autre.
void
sort_contents
(list **h)
{
list *ph,*after,*p,*pa,*pb;
ph=h[0];
while (ph)
{
after=ph->next;
if (ph->next && ph->pos>ph->next->pos)
while (ph->next && ph->pos>ph->next->pos)
{
pa=ph->next->next;
pb=ph->prev;
p=ph->next;
p->next=ph;
ph->prev=p;
ph->next=pa;
p->prev=pb;
if (pa)
pa->prev=ph;
if (pb)
pb->next=p;
else
h[0]=p;
}
else
while (ph->prev && ph->pos<ph->prev->pos)
{
pa=ph->next;
pb=ph->prev->prev;
p=ph->prev;
ph->next=p;
p->prev=ph;
ph->prev=pb;
p->next=pa;
if (pa)
pa->prev=p;
if (pb)
pb->next=ph;
else
h[0]=ph;

}
ph=after;
}
}
Je passe l'addresse de la liste à trier, je me base dans un premier temps sur le(s) maillon(s) suivant s'il existe si c'est bon je regarde avec le(s) maillon(s) précédent(s).
Je ne traverse pas systématiquement la liste.
Je n'oublie pas de redonner le maillon de tête si nécessaire.
Pas besoin de redonner le maillon de tête.

Je pense que c'est la méthode la plus simple.

[Votre pseudo ici]

Woah ce remontage de post d'il y a 7 ans o_O.

Je crois qu'il a eu la réponse depuis.

Sinon, personne ici ne semble avoir donné la réponse la plus triviale: le tri par insertion (O(n²))

[Zuglok]

C'est étrange quand même de créer un compte sur un forum de jeux vidéo pour prendre le temps répondre à une question de prog datant d'il y a 7 ans.

Vraiment je suis intrigué, c'est presque une démarche artistique.

[Kathar - Alleria - Lango]

Citation :

Publié par Zuglok

C'est étrange quand même de créer un compte sur un forum de jeux vidéo pour prendre le temps répondre à une question de prog datant d'il y a 7 ans.

Vraiment je suis intrigué, c'est presque une démarche artistique.

Surtout pour pondre un machin mal codé et illisible comme ça…
J’aime bien le « je pense que c’est la méthode la plus simple », il m’a bien fait rire.

Tu as raison, un nouvelle forme d’art est peut-être en train de naître devant nos yeux.