MERGE SORT

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019 - 21 févr. 2005 à 00:02
vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 - 22 févr. 2005 à 18:23

Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.

https://codes-sources.commentcamarche.net/source/29675-merge-sort

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
22 févr. 2005 à 18:23

dominion> ok, c'est que je n'ai pas l'habitude de voir des break comme ca, je me suis trompé

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
21 févr. 2005 à 19:56

On crée un tableau de pointeurs qui est la simulation des params (adresses) dans la récursion mais il n'y a pas d'empilage dépilage.

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
21 févr. 2005 à 19:18

BruNews : que veux-tu dire par simulé ?

steve_clamage Messages postés 475 Date d'inscription dimanche 3 octobre 2004 Statut Membre Dernière intervention 11 août 2006 5
21 févr. 2005 à 19:08

Merci pour cette precision BruNews, si qsort fais comme ca montre que les algos récursif mérite biens qu'on les étudies, ca peux toujours etre une solution.

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
21 févr. 2005 à 17:25

vecchio56 : si le break est là, c'est justement pour éviter le n² ! Regarde :

(6, 2, 3, 5, 4, 8)
Je pars du principe qu'on a déjà fait le début. On en est à
(2, 3, 6), (4, 5, 8)
qui sont deux tableaux triés distincts (c'est une vue de l'esprit, ils sont tous les deux stockés dans t). Mon code passe 3 fois dans le premier tableau, et teste la premiere valeur du deuxième tableau. Ce qui donne :

2 < 4 ==> OUI, donc break;
3 < 4 ==> OUI, idem que pour 2 < 4
6 < 4 ==> NON, on décale donc le 6 de 1 vers la droite pour laisser la place au 4 qu'on intègre au premier tableau, ce qui donne : (2, 3, 4, 6), (5, 8)
6 < 5 ==> NON, idem que pour 6 < 4 : (2, 3, 4, 5, 6), (8)
6 < 8 ==> OUI, donc break;
Il n'y a plus rien après 6 dans le premier tableau, c'est donc trié. Total : 5 tests. C'est le plus que j'ai trouvé. C'est optimisable en prenant au centre du tableau au début, je pense... Mais je n'ai pas encore eu l'occasion de vérifier.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
21 févr. 2005 à 11:13

steve_clamage > c'est exact ce que fait qsort(), la récursion est simulée par une stack interne à la procédure, c'est d'une efficacité redoutable.

Ceci dit, on ne remet pas en cause le coté didactique de cette source, c'est impec pour montrer l'emploi des template.

vecchio56 Messages postés 6535 Date d'inscription lundi 16 décembre 2002 Statut Membre Dernière intervention 22 août 2010 14
21 févr. 2005 à 11:11

Dans la boucle de fusion:
for (signed long int i = beg; i < newend; ++i)
for (signed long int j = newbeg; j < end; ++j)
{
if (t[i] <= t[j]) break; ...

si le tableau est déja trié par exemple, on va a chque fois dans le break, et du coup les deux for font n/2 itérations, donc rien que la fusion est en n^2, alors que cet algo est censé être en n log2 n. (Je fais confiance à Kirua)
Soit je me trompe, soit la mise en ouvre n'est pas bonne...

steve_clamage Messages postés 475 Date d'inscription dimanche 3 octobre 2004 Statut Membre Dernière intervention 11 août 2006 5
21 févr. 2005 à 08:23

il me semble qu'il y a aussi des techniques pour simuler la récursivité avec sa propre pile mais je sais pas ce que ca vaut

cs_Kirua Messages postés 3006 Date d'inscription dimanche 14 avril 2002 Statut Membre Dernière intervention 31 décembre 2008
21 févr. 2005 à 07:55

Et ça va exploser la taille de l'exe, merci bien :/ Autant rester générique. Et puis très bien il y a des algos de tri fournis: mais si un jour il doit coder avec un langage qui n'a pas ça en bibliothèque standard, faudra bien qu'il mette la main à la patte, et ça risque d'être meilleur avec un merge sort n log n qu'avec un bubble sort n².

Quoique, l'histoire de récursivité ça me chagrine qd même, c'est notoirement un procédé lent ... à revoir, quitte à garder une version récursive pour benchmark et lisibilité.

steve_clamage Messages postés 475 Date d'inscription dimanche 3 octobre 2004 Statut Membre Dernière intervention 11 août 2006 5
21 févr. 2005 à 00:34

on peux supprimer la récurence et dérouler le code avec les templates, seulement la taille du tableau devra etre connue à la compilation

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
21 févr. 2005 à 00:16

Ce code a un but purement pédagogique... Il est clair qu'il existe des algos de tri plus efficaces, mais il peut permettre à certains de mieux comprendre le merge sort. C'est tout...

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
21 févr. 2005 à 00:11

C'est livré avec le compilo, ça s'appelle qsort().

cs_dominion Messages postés 230 Date d'inscription mardi 21 janvier 2003 Statut Membre Dernière intervention 15 mai 2008
21 févr. 2005 à 00:08

C'est vrai aussi, mais c'est plus lisible comme ça... Libre à toi de recoder sans récurrence, je ne pense pas que cela soit difficile.

BruNews Messages postés 21040 Date d'inscription jeudi 23 janvier 2003 Statut Modérateur Dernière intervention 21 août 2019
21 févr. 2005 à 00:02

Pour vraiment accélérer le traitement, faudrait supprimer la récurrence.

Discussions similaires

affichage d'un tirage au sort

array.sort

code source d'une fonction fournie par PHP (sort())?

tirer aleatoirement un caractere dans l'alphabet

Tirage au sort avec poids

Votre réponse

Discussions similaires