Permutation permettant de trier un vecteur

**Christophe Genolini** · 08/09/2016, 15h20

Bonjour,

(toutes mes excuses si ca n'est pas le bon endroit pour poster cette question...)
Je cherche une fonction C qui me donnerait la permutation permettant de trier un vecteur dans l'ordre croissant. Par exemple, j'ai la vecteur age=(18,16,21,15). La vecteur "age après tri" est (15,16,18,21). La permutation permettant d'obtenir age après tri est (4,2,1,3). Je cherche donc la fonction qui me donnerait (4,2,1,3). Savez-vous si elle existe ?

Merci beaucoup pour votre aide.
Christophe

**Matt_Houston** · 08/09/2016, 15h46

Elle n'existe pas dans la bibliothèque standard, mais tu peux - par exemple - encapsuler tes éléments dans un struct indexed { Type data; size_t index; }, initialiser index puis effectuer un qsort sur le tableau. La nouvelle séquence des valeurs de index te donnera la permutation.

**Christophe Genolini** · 09/09/2016, 12h42

Merci. Effectivement, c'est une possibilité.
Sinon, elle n'existe pas dans une librairie non-standard ?

**Matt_Houston** · 09/09/2016, 13h11

Très probablement, reste à la trouver. Cela dit la méthode que j'ai suggéré serait probablement implémentée en dix lignes et quinze minutes chrono, tests unitaires compris.

**picodev** · 09/09/2016, 15h15

Bonjour,

Comme le dit très bien Matt_Houston, quand il n'y a pas et que c'est simple à implémenter autant le faire. J'imagine que le prototype de ta fonction idéale prend pour paramètre un tableau et sa taille et te renvoie un tableau de même taille contenant la permutation. Quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

size_t *perm_sort(size_t size, int array[static size]);

Un algorithme pour faire ça sans passer par une structure pourrait suivre l'idée suivante : si on regarde un algo de tri (par comparaison) de plus près on s'aperçoit qu'en gros on suit une procédure de décision pour savoir quels éléments échanger, et on fait ça tant qu'on a pas le tableau trié. Si on se crée un tableau auxiliaire A={0,1,...,n} avec n+1 la taille du tableau à trier T et qu'au lieu d'échanger les éléments de T on échange les éléments correspondant de A alors à la fin A contient la permutation cherchée. Les comparaisons ne porteront plus sur T[i] et T[j] mais sur T[A[i]] et T[A[j]].

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
size_t *perm_sort(size_t size, int array[static size])
{
  // On crée et initialise A
  size_t *A=malloc(sizeof(size_t[size]));
  for(size_t i=0; i<size; ++i)
    A[i]=i;
 
  // On «tri», ici j'ai choisi gnome sort pour l'exemple
  size_t i=1,j=2;
  while (i<size) {
    if ( array[ A[i-1] ] > array[ A[i] ] ) {
      swap(A, i, i-1);
      if (--i) continue;
    }
    i=j++;
  }
 
  // éventuellement tu rajoutes 1 à chaque élément de A pour obtenir une permutation
  // qui commence avec 1 et non 0
  ...
 
  return A;
}

Code incomplet non testé juste pour donner l'idée.

**sambia39** · 23/09/2016, 21h43

Bonsoir,

Envoyé par Matt_Houston

Elle n'existe pas dans la bibliothèque standard, mais tu peux - par exemple - encapsuler tes éléments dans un struct indexed { Type data; size_t index; }, initialiser index puis effectuer un qsort sur le tableau. La nouvelle séquence des valeurs de index te donnera la permutation.

Je ne suis pas d’accord sur le principe d’utiliser une structure dès le départ. C’est complexifié la chose pour un résultat qui n’est pas forcements ce que l’on souhaite qu’ils fassent. Il faut voir le problème autrement et se concentrer uniquement sur les notions de tris.

Ce que le primo-postant (collègue enseignant) essayez de faire du moins essayer d’accomplir, est-ce que l’on appelle un tri indirect plus précisément l’implémentation d’un algorithme de tris indirect . C’est-à-dire un tri qui utilise un tableau secondaire indiquant, pour chaque élément du tableau à trier, le rang ou l’indice que celui-ci devrait avoir dans le tableau trié. Ce n’est que par la suite que vous pouvez trier votre tableau grâce à cette séquence et non l’inverse car, la séquence vous permet de réorganiser l’ensemble et obtenir un tableau trié.
Voici comment se présente cet algorithme et son implémentation.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
FUNC_SET_TAB_INDICE( TAB, TAB_INDICE, SIZE_TAB ):
 
ENTIER I = 0
ENTIER J = 0
ENTIER V_VALEUR = 0
ENTIER ID_INDEX = 0
 
POUR I = 0 à (SIZE_TAB-1) FAIRE:
	TAB_INDICE[I] = I
FIN_POUR
 
POUR I = 0 à (SIZE_TAB-1) FAIRE:
	ID_INDEX = TAB_INDICE[I]
	V_VALEUR = TAB[ID_INDEX]
 
	TANT_QUE  0 < J && (V_VALEUR < TAB[TAB_INDICE[J-1]):
		TAB_INDICE[J] = TAB_INDICE[j-1]
		J = J - 1
	FIN_TANT_QUE
	TAB_INDICE[J] = ID_INDEX
FIN_POUR
 
FIN_FUNC_SET_TAB_INDICE

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/*
 ============================================================================
 Name        : source.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 23/09/2016 SAMBIA39
 Description : Ansi-style
 ============================================================================
 */
 
 
#include <stdio.h>
#include <stdlib.h>
 
/*
*	Fonction qui fixe les indices. 
*	Elle permet par la suite d’effectuer un tri de 
*	façon indirecte  en déplaçant uniquement 
*	les valeurs des indices.
*/
void f_set_sequence( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;		
	int j = 0;
	int v = 0;			// Variable des valeurs 
	int id = 0;			// Variable des Id
 
	/*
	*	Acquisition des Indices
	*/
	for( i = 0; i < (int)size; i++ )
		TabId[i] = i;
 
	/*
	*	(1) Déplacement des éléments
	*	(2) Placement des indices
	*/
	for( i = 0; i < (int)size; i++ ){
		id = TabId[i];
		v = Tab[id];
 
		j = i;
		//(1)
		while( 0 < j && ( v < Tab[ TabId[j-1]]) ){
			TabId[j] = TabId[j-1];
			j--;
		}
		//(2)
		TabId[j] = id;
	}
}
 
 
 
int main( void ){
 
 
	int Tab[] = { 18, 3, 56, 10 };
	int Itab[4];
	unsigned int i = 0;
	f_set_sequence( Tab, Itab, 4 );
	fprintf( stdout, "Résultat de la séquence de tris\n");
	for( i = 0; i < 4; i++ )
		fprintf( stdout, "%d ", Itab[i] );
	fprintf( stdout, "\nSoit les valeurs suivantes\n");
	for( i = 0; i< 4;  i++ )
		fprintf( stdout, "%d(%d) ", Tab[i],i );
	fprintf( stdout, "\n");
	return EXIT_SUCCESS;
}

Ce qui donne l’implémentation suivante pour la réorganisation des données et la conservation des indices de tableaux:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
/*
 ============================================================================
 Name        : source.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 23/09/2016 SAMBIA39
 Description : Ansi-style
 ============================================================================
 */
 
 
#include <stdio.h>
#include <stdlib.h>
 
/*
*	Fonction qui fixe les indices. 
*	Elle permet par la suite d’effectuer un tri de 
*	façon indirecte  en déplaçant uniquement 
*	les valeurs des indices.
*/
void f_set_sequence( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;		
	int j = 0;
	int v = 0;			// Variable des valeurs 
	int id = 0;			// Variable des Id
 
	/*
	*	Acquisition des Indice
	*/
	for( i = 0; i < (int)size; i++ )
		TabId[i] = i;
 
	/*
	*	(1) Déplacement des éléments
	*	(2) Placement des indices
	*/
	for( i = 0; i < (int)size; i++ ){
		id = TabId[i];
		v = Tab[id];
 
		j = i;
		//(1)
		while( 0 < j && ( v < Tab[ TabId[j-1]]) ){
			TabId[j] = TabId[j-1];
			j--;
		}
		//(2)
		TabId[j] = id;
	}
}
 
 
/*
* 	Fonction qui permet de trier le tableau initial 
* 	grâce au tableau des indices
*	(1) variable de end utilisé pour la permutation
*	(2) variables d’origine utilisée pour la permutation 
*	(3) sauvegarde des valeurs
*	(4) réorganisations 
*/
void f_tris_indirect( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;
	int i_s = 0;
	int i_e = 0; //(1)
	int i_v = 0; //(2)
 
	for( i = 0; i < (int)size; i++ ){
 
		//(3)
		if( i != TabId[i] ){
			i_v = Tab[i];
 
			//(4)
			i_e = i;
			i_s = TabId[i_e];
			while( i != i_s ){
				Tab[i_e] = Tab[i_s];
				TabId[i_e] = i_e;
				i_e = i_s;
				i_s = TabId[i_e];
			}
			Tab[i_e] = i_v;
			TabId[i_e] = i_e;
		}
	}
}
 
/*
*	Programme principale
*/
int main( void ){
 
	int Tab[] = { 18, 3, 56, 10 };
	int Itab[4];
	unsigned int i = 0;
	f_set_sequence( Tab, Itab, 4 );
	fprintf( stdout, "Résultat de la séquence de tris\t:");
	for( i = 0; i < 4; i++ )
		fprintf( stdout, "%d ", Itab[i] );
	fprintf( stdout, "\nSoit les valeurs suivantes\t:");
	for( i = 0; i< 4;  i++ )
		fprintf( stdout, "%d(%d) ", Tab[i],i );
	fprintf( stdout, "\nTableau des valeurs trié \t:");
	f_tris_indirect(Tab, Itab, 4);
	for( i = 0; i< 4;  i++ )
		fprintf( stdout, "%d ", Tab[i]);
	fprintf( stdout, "\nFin de traitement");
	return EXIT_SUCCESS;
}

à bientôt

**Bktero** · 23/09/2016, 22h31

C'est simplifier que de recoder une fonction de tri alors que qsort existe ?

**picodev** · 24/09/2016, 00h39

Bah oui, surtout quand le but n'est pas de trier mais de trouver une permutation.
Alors effectivement on peut s'en sortir avec des copies vers une nouvelle structure, la trier, refaire une copie de cette nouvelle structure pour obtenir le résultat, la phase de tri utilisant qsort → on ne redéveloppe pas un tri mais tout ce qui va autour; ou directement manipuler la permutation → on redéveloppe un tri sans tout ce qui va autour.

**Matt_Houston** · 25/09/2016, 10h03

Il faudra nous expliquer comment déterminer la permutation sans trier les données dans le même temps..

**picodev** · 25/09/2016, 13h11

Si tu regardes bien mon code, je ne trie jamais les éléments du tableau. Comme l'a fait remarquer Sambia par la suite, il s'agit d'un tri indirect :on trie un tableau d'indice à la place de tableau lui-même.

En poussant le bouchon un peu plus loin, on pourrait même «s'affranchir» d'un algo de tri sur les indices :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
bogo_perm_sort( array )
pour toutes les permutations P de longueur length(array)
  si est ordonné(P appliqué à array) alors
    renvoyer P

On teste toutes les permutations jusqu'à trouver celle qui ordonne le tableau. Bon faut avoir le temps ^^
C'est en gros l'implémentation de bogosort …

**Matt_Houston** · 25/09/2016, 20h39

Bon. On cause de quoi là ?

Si c'est de la façon la plus stérile de trier-un-tableau-mais-bon-sans-vraiment-le-trier-tu-vois en C89 faut l'annoncer de suite, auquel cas je me retire bien volontiers du débat.

**sambia39** · 25/09/2016, 21h51

Bonsoir,
Il n’y a rien d’extraordinaire. J’ai répondu au primo postant on lui apportant une solution algorithmique. Peut-être que dans mon précédent post, je n’ai pas été clair, je m’en excuse d’avance.
Dans le poste qui suit, je vais du mieux que je peux pour répondre à chacune de vos remarques tout aussi pertinentes et si possible clair.

Je n’ai pas, la prétention de faire un cours ou donner un cours d’algorithmes de tri loin de moi cette idée. Mais pour me faire comprendre, je suis amené à expliquer ce que c’est que l’algorithme de tri indirect.
J’ai opté pour l’algorithme de tris indirects parce que celle-ci utilise un tableau secondaire indiquant, pour chaque élément du tableau à trier, le rang ou l’indice que celui-ci devrait avoir dans le tableau trié.

Mon précédent post (plus précisément le premier code source et son algorithme) répondait à la question posée par le primo postant à savoir s’il existe un moyen d’avoir « la permutation permettant de trier un vecteur dans l'ordre croissant » en l’occurrence connaître ou avoir le rang, l’indice ou la position des éléments que celui-ci devrait avoir dans le tableau après tris. (Peut-être que j’ai omis de mentionner que l’algorithme fournit juste la permutation permettant de trier un vecteur dans l'ordre croissant.)

Envoyé par Matt_Houston

Il faudra nous expliquer comment déterminer la permutation sans trier les données dans le même temps..

Alors comment cela se présente-t-il de façon concrète.
Le tableau d’indices n’est rien d’autre qu’un simple tableau d’entier de la même taille que le tableau de données (dans notre cas, le tableau du primo postant qui est le suivant: âge=(18,16, 21,15)) et contient que les numéros d’indice des positions des éléments du tableau de données (indice 0 = 18, indice 1 = 16, indice 2 = 21, indice 3 = 15 donc tab id = 0,1, 2,3). L’accès aux données du tableau de données passe alors, par le tableau des indices et non par le tableau de données et ceci est ce que l’on appelle un accès indirect d’éléments ou adresse car le tableau des indices n’indique pas l’adresse des éléments (on parle alors de faux pointeur), mais l’indice de la case ou se trouve l’élément. Mieux encore le tableau de données n’est point trié donc il reste inchangé, mais le tableau des indices lui, contiendra l’ordre de permutation ou l’ordre des éléments que celui-ci devrait avoir dans le tableau de donnée trié c'est-à-dire dans l’état trié (tableau des données après tri (15,16, 18,21) doit correspondre au tableau indice suivant(4,2, 1,3)).

Techniquement, on effectue un tri par insertion sur le tableau d’indice qui contient que les indices des éléments du tableau de données. Les comparaisons se basent sur les valeurs des éléments du tableau de données, mais les échange ou permutation effectuée se basent sur les indices donc on effectue un accès aux données de façon indirecte via le tableau des indices.
Mieux encore pour effectuer le tri du tableau de données rien de plus simple d’utiliser le tableau des indices pour mettre les éléments du tableau de données dans l’ordre du tableau d’indice. Et en faisant cela, on tri naturellement un tableau à moindre coût, car les éléments sont déplacés(permuté). Aux finales le code source ci-dessous effectue aucun tri sur le tableau de données, mais fournit la séquence dans laquelle les éléments doivent être triés.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
/*
 ============================================================================
 Name        : source.c
 Author      : SAMBIA39
 Version     : 0.1
 Copyright   : Copyright (c) 23/09/2016 SAMBIA39
 Description : Ansi-style
 ============================================================================
 */
 
 
#include <stdio.h>
#include <stdlib.h>
 
/*
*	Fonction qui fixe les indices. 
*	Elle permet par la suite d’effectuer un tri de 
*	façon indirecte  en déplaçant uniquement 
*	les valeurs des indices.
*/
void f_set_sequence( int Tab[], int TabId[], 
	size_t size ){
 
	int i = 0;		
	int j = 0;
	int v = 0;			// Variable des valeurs 
	int id = 0;			// Variable des Id
 
	/*
	*	Acquisition des Indice
	*/
	for( i = 0; i < (int)size; i++ )
		TabId[i] = i;
 
	/*
	*	(1) Déplacement des éléments
	*	(2) Placement des indices
	*/
	for( i = 0; i < (int)size; i++ ){
		id = TabId[i];
		v = Tab[id];
 
		j = i;
		//(1)
		while( 0 < j && ( v < Tab[ TabId[j-1]]) ){
			TabId[j] = TabId[j-1];
			j--;
		}
		//(2)
		TabId[j] = id;
	}
}

Et pourquoi je ne suis pas d'accord avec vous sur l'utilisation d'une structure ?. C'est parce que si on utilise une structure de données, on s'attend a manipuler des données complexes. Analyser de façon pertinente votre solution vous verrez que l’implémentation peut vite être complexe et mieux encore la chose peut ne pas fournir le résultat escompté dans le pire des cas.

Envoyé par Bktero

C'est simplifier que de recoder une fonction de tri alors que qsort existe ?

"qsort", implémente un algorithme de tri non spécifié qui permet de trier tout ou partie de n'importe quel tableau de données. Elle utilise une fonction écrite préalablement qui se charge d'exprimer le critère de tri. Dans mon premier code source, je une trie rien; je donne les séquences dans lequel les éléments doivent être triés.
Dans le second code source, je donne un exemple utilisant le tableau d’indices pour réorganiser le tableau de données donc effectuer un tri indirect. Je ne réinvente rien, j’implémente juste une fonction de tri qui se base sur le tableau d’indice et c'est un choix qui est largement moins coûteux que "qsort".

Envoyé par picodev

Bah oui, surtout quand le but n'est pas de trier mais de trouver une permutation.
Alors effectivement on peut s'en sortir avec des copies vers une nouvelle structure, la trier, refaire une copie de cette nouvelle structure pour obtenir le résultat, la phase de tri utilisant qsort → on ne redéveloppe pas un tri mais tout ce qui va autour; ou directement manipuler la permutation → on redéveloppe un tri sans tout ce qui va autour.

Envoyé par picodev

Si tu regardes bien mon code, je ne trie jamais les éléments du tableau. Comme l'a fait remarquer Sambia par la suite, il s'agit d'un tri indirect :on trie un tableau d'indice à la place de tableau lui-même.

Vos deux derniers messages sont contradictoires. Dans le premier, vous faites une remarque sur le fait que le but est de trouver une permutation et non triée. C’est exact et c’est ce que j’ai fourni dans mon premier code source avec son algorithme qui ne trie pas le tableau de données.
Ensuite vous appuyer la remarque du «qsort» (d’après ce que moi j’ai compris (sous-entendu) que la fonction « qsort » est mieux) pour finir par accordée du crédit sur l’algorithme de tris indirecte que j’ai énoncée. J'avoue que je n'ai pas compris votre manoeuvre et de toute façon ce n'est pas pertinent dans le cas actuel.

à bientôt

**picodev** · 25/09/2016, 22h21

Envoyé par Matt_Houston

Bon. On cause de quoi là ?

Si c'est de la façon la plus stérile de trier-un-tableau-mais-bon-sans-vraiment-le-trier-tu-vois en C89 faut l'annoncer de suite, auquel cas je me retire bien volontiers du débat.

Bon, ok … le bogosort c'est, comme son nom l'indiquem un tri stupide qui n'a qu'un intérêt théorique qui montre qu'il est possible de «déterminer la permutation sans trier les données dans le même temps».
C'est le genre d'exemple qui montre que les expressions comme «tous les tris doivent être en O(n log n)» ne sont que des abus de langage ou tout du moins qui ne sont pas forcément comprises pour ce qu'elles sont.

Mais le «trier un tableau sans vraiment le trier» en utilisant un tableau auxiliaire d'index n'a pas qu'un intérêt théorique. Le tri indirect permet d'accéder facilement aux données triées sans pour autant détruire l'ordre initial si on a besoin des deux ou qui est intéressant quand on ne peut modifier le tableau initial par exemple.

**sambia39** · 26/09/2016, 12h32

Bonjour,
Peut être que je me trompe mais , il me semble que vous avez fait deux erreurs dans votre avant dernier post et la dernière sauf, si c’est moi qui me suis trompé.

Envoyé par picodev

Bon, ok … le bogosort c'est, comme son nom l'indiquem un tri stupide qui n'a qu'un intérêt théorique qui montre qu'il est possible de «déterminer la permutation sans trier les données dans le même temps».
C'est le genre d'exemple qui montre que les expressions comme «tous les tris doivent être en ~~O(n log n)»~~ ne sont que des abus de langage ou tout du moins qui ne sont pas forcément comprises pour ce qu'elles sont.

Mais le «trier un tableau sans vraiment le trier» en utilisant un tableau auxiliaire d'index n'a pas qu'un intérêt théorique. Le tri indirect permet d'accéder facilement aux données triées sans pour autant détruire l'ordre initial si on a besoin des deux ou qui est intéressant quand on ne peut modifier le tableau initial par exemple.

La première erreur est celle de l’algorithme ce n’est pas

Envoyé par picodev

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
bogo_perm_sort( array )
pour toutes les permutations P de longueur length(array)
	si est ordonné(P appliqué à array) alors
		renvoyer P

mais

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
FUNC_BOGOSORT(TAB):
  TANT_QUE !OrdonnerTab(TAB):
   SHUFFLE_TAB(TAB)

On vérifie la liste si elle est déjà trie, le cas contraire on modifie de façon aléatoire la liste des éléments et on répète cette procédure tant que le tableau n’est pas trié. Votre variante est celle non pas du «*bogosort*», mais du «*bozosort*» qui est quant à lui vachement (et sans exagérer) totalement inefficace. Elle permute au hasard les éléments jusqu’à ce que le tableau soit trié.
L’algorithme est le suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
FUNC_BOZOSORT(TAB):
 TANT_QUE !OrdonnerTab(TAB):
  SWAP_DATA_TAB( TAB[SHUFFLE(TAB)], TAB[SHUFFLE(TAB)] )

La deuxième erreur est ce elle de la complicité de l’algorithme «*bogosort*» elle n’est pas en ~~"O(n log n)"~~, mais plutôt en O(n.n!) (voir selon la variante), car le nombre de permutations (si je peux dire ainsi) est factoriel d'où son inefficacité. Bien qu’il puisse fournir un tableau trié, on ne sait pas quand il nous le fournira. Cela est justifiable. Toute permutation effectuée pour aboutir à un ensemble trié et fini est factorielle n! et le pire des cas peut très bien tendre vers l’infini, car rien ne garantit que la permutation aléatoire aboutira à un tableau trié. Le cas cité donne O(n.n!) en temps, O(n!) en espace mémoire.
(Et honnêtement il n’y a pas d’abus de langage.)

Envoyé par picodev

Si tu regardes bien mon code, je ne trie jamais les éléments du tableau. Comme l'a fait remarquer Sambia par la suite, il s'agit d'un tri indirect :on trie un tableau d'indice à la place de tableau lui-même
En poussant le bouchon un peu plus loin, on pourrait même «s'affranchir» d'un algo de tri sur les indices :
.........
On teste toutes les permutations jusqu'à trouver celle qui ordonne le tableau. Bon faut avoir le temps ^^
C'est en gros l'implémentation de bogosort …

On ne peut pas substituer un algorithme de tris indirects par un algorithme stupide c’est totalement stupide. L’algorithme de tris indirects se base sur un tableau auxiliaire pour effectuer un tri et donne à la fin la permutation exacte de l’ensemble d’éléments que celui-ci devrait avoir dans le tableau trié. Le tri stupide effectue des permutations aléatoires pour (en espérant) triées un tableau qui est beaucoup plus coûteuse, instable et non adaptée pour ce genre de chose (qu’il reste dans le cadre pédagogique et même …) que le tri indirect. Même avec des ensembles assez volumineux le tri indirect est mieux que certains algorithmes de tris traditionnels et elle moins coûteuses.

Je pense qu’il faut rester sur l’essentiel et ne pas s’égarer. Le cas actuel nécessite l’utilisation de l’algorithme indirect plus précisément la séquence de tri (les indices d'élément que l'on devrait avoir dans le tableau trié). De plus il n’y a aucune utilité de faire une comparaison ou entrevoir les tris stupides, car elles sont stupides et inefficaces. Je recommande donc fortement l’algorithme de tris indirects que j’ai proposé dans mon tout premier post et sans chercher d'exemple d'autre cas « bozo-sort, bogo-sort, slow-sort, stooge-sort, structure de données complexes, etc..». Car pour moi, il n’y a pas raison des les mentionné (et pourquoi pas le lucky-sort pendant quand y ait ).
Bref, c’est mon point de vue et ma proposition, mais si le primo-postant tend a vouloir adopter autre chose que la solution proposée libre à lui.

à bientôt.

**picodev** · 26/09/2016, 13h36

Envoyé par sambia39

Bonjour,
Peut être que je me trompe mais , il me semble que vous avez fait deux erreurs dans votre avant dernier post et la dernière sauf, si c’est moi qui me suis trompé.

La première erreur est celle de l’algorithme ce n’est pas …

Bon je vais un peu expliquer messages car je commence sérieusement à douter de leur facilité de compréhension.

Message #5 → Je donne une pseudo implémentation d'un tri indirect que j'appelle perm_sort, en donnant une explication qui vaut ce qu'elle vaut. Le po a plusieurs réponses, plusieurs approches, il ne réagit pas, peu m'importe.

---

Message #8 → Je réagis car effectivement qsort n'est pas forcément la fonction la plus adaptée pour résoudre le problème, mais là ça reste un détail d'implémentation.

---

Message #10 : Je le commence par «si tu regardes bien mon code» en manquant sans doute de précision, je parlais bien évidemment du code que j'ai donné au message #5 ... et non du pseudo code bogo_perm_sort que je donne par la suite. Je pensais, apparemment à tort, que le fait de dire «En poussant le bouchon un peu plus loin, on pourrait même «s'affranchir» d'un algo de tri sur les indices» montrait que je passais à un autre code. J'imaginais, toujours à tort, que mon smiley ^^, le nom (bogo_perm_sort) serait interprété comme un trait d'humour en prenant à la lettre la réflexion Matt_Houston. En plus j'ajoute que «c'est en gros l'implémentation de bogosort», en gros signifiant (en général) «ça ne l'est pas mais c'est pas trop loin». C'est aussi pour ça que j'ai appelé mon «exemple» bogo_perm_sort et non bogosort …

---

Message #13 : ce message possède possède deux paragraphes. Le premier explique simplement que même si un tri est stupide il n'es reste pas moins un tri. Qu'un tri, aussi stupide soit-il, possède un intérêt ne serait-ce que théorique. Pourquoi théorique ? Simplement parce qu'il montre qu'il n'y a pas que les tris par comparaisons/échanges qui existent, que de nombreux a priori sur les tris existent et que beaucoup parlent de choses peu comprises mais simplement apprises.
À aucun moment je n'affirme que la complexité de bogosort est en O(n log n) ...

**Matt_Houston** · 26/09/2016, 14h38

Envoyé par sambia39

Bonsoir,
Il n’y a rien d’extraordinaire.

Oui, ça je te le confirme.

Ton truc - pardonne ma véhémence latine - c'est un putain de tri par insertion. C'est quadratique, pas franchement bandant.. ça fait le job sur de petites quantités de données, voilà. Que tu modifies ou non les données d'entrée ne change rien. Il n'y a pas d'algorithme de tri direct ou indirect, il y a des algorithmes de tri tout court dont les propriétés sont connues depuis Mathusalem et qu'il faut exploiter. Le reste, c'est de l'enculage de mouches.

Bien entendu qu'on peut injecter le calcul de la permutation dans une fonction de tri, au prix des conséquences associées à sa réécriture (augmentation de la durée de développement, de la taille du code, tests unitaires, bugs, etc...). Bien entendu qu'on peut imaginer mille manières de répondre à l'énoncé - qui n'est pas de l'OP d'ailleurs, puisque lui ne demandait pas comment faire. Quelqu'un ici a-t-il écrit le contraire ?

Quand je lis que déterminer la permutation n'est pas trier (mais qu'on le fait pour, au final, trier hein

), que qsort n'est pas adapté, quand je vois des digressions de deux écrans sur un tri enseigné depuis soixante ans... alors que la demande de l'OP tient en deux pauvres lignes. Ben je sais pas.. faut douter de rien.

**sambia39** · 26/09/2016, 17h48

Et bien ce putain de tri par insertion se fait sur les indices de tableaux. Le résultat de ces indices de tableau est utilisé par la suite pour réorganiser le vrai tableau de données (avec les vraies valeurs). Utiliser un tableau auxiliaire trié pour réorganiser les éléments dans le bon ordre c’est faire un tri indirect. Et l’on parle alors d’algorithmes de tris indirects.

Envoyé par Matt_Houston

Il n'y a pas d'algorithme de tri direct ou indirect, il y a des algorithmes de tri tout court dont les propriétés sont connues depuis Mathusalem et qu'il faut exploiter. Le reste, c'est de l'enculage de mouches.

Effectivement, il existe des algorithmes de tri. Alors expliqué moi pourquoi doit-on dire (les distinguer voir les classifier en disant) algorithme de tri par insertion, algorithme de tri par sélection ou par extraction, algorithme de tri par propagation, algorithme de tri par comptage, algorithme de tri bidirectionnel, algorithme de tri à peigne, algorithme de tris rapides, algorithme de tri indirect, algorithme de tri Oyelami, algorithme de tri gnome ? (par exemple), sachant qu’ils sont tous des algorithmes de tri tout court ?

Envoyé par Matt_Houston

alors que la demande de l'OP tient en deux pauvres lignes. Ben je sais pas.. faut douter de rien.

le PO n’a pas demandé comment faire, mais s'il existe une fonction qui réalise ce qu'il souhaite. C’est tout à fait normal que certains membres de ce forum lui fassent part de l'existence d'une solution (ou algorithme)(l’informent de l’existence d’une t-elle chose avec un exemple si possible selon celui qui poste le message afin d'appuyer ce qu'il avance.) Libre à tout un chacun de faire ce qu’il lui semble juste il n’est pas interdit d’aider, proposé, voir fournir la solution dans la mesure du possible.

Envoyé par Matt_Houston

Quand je lis que déterminer la permutation n'est pas trier (mais qu'on le fait pour, au final, trier hein

), que qsort n'est pas adapté, quand je vois des digressions de deux écrans sur un tri enseigné depuis soixante ans...

Oui vous pouvez le lire, "qsort" trie des tableaux, mais faut lui fournir la règle qui permet des trié le tableau en question cette règle passe par une fonction qui implémente un algorithme. Et l'algorithme que j’ai posté sans passe très bien de "qsort". Libre à vous si vous le souhaité, de continuer dans votre lancé de structure de données avec ces éléments et qsort afin trier le tableau et avoir les séquence souhaité. Libre à vous. Rien ne vous empêche également de ne pas être d'accord sur un algorithme.

Franchement, sur ce sujet les poignions divergent , il peut arrivé que l’on ne soit pas d’accord, mais a force le débat devient stérile et ça aboutira en rien de bon

à bientôt

**Médinoc** · 29/09/2016, 06h36

Franchement, si "tri indirect" désigne un tri d'indices pointant vers un autre tableau, alors il n'y a pas d'"algorithmes de tri indirect": Juste un algorithme de tri, tout court, appliqué à un autre tableau.
D'ailleurs, le qsort() de base est est extrêmement inadapté aux tris indirects, car le seul moyen "propre" de le faire est de trier non plus juste des indices, mais des couples {pointeurs vers premier élément du tableau; indice}.
Heureusement, les choses vont mieux quand on à accès à qsort_r().

Permutation permettant de trier un vecteur

C

Discussions similaires

Partager

Partager