Discussion :

[rosco-rs]

Bonsoir

Pendant quelque heure j'ai bloqué sur un programme dont l'intitulé était de trier par ordre croissant les valeurs d'un tableau je suis tombé sur ça et j'essaye d'en saisir le sens

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
	while (i < tab_size)
{
		j = i+1;               // Ici pourquoi faire sa ? pourquoi dire que notre variable j = la valeur de i + 1 ? (j et i étant ce qui va nous permettre
		while (j < tab_size)*** // de parcourir notre tableau)
		{
			if(tab[j] < tab[i])
				{
					tmp = tab[i];          // Ici j'ai compris le principe on affecte notre résultat dans une variable temporaire 
					tab[i] = tab[j];       // pour ensuite la mettre dans tab[j] (un swap)
					tab[j] = tmp;
				}
			j++;
		}
		printf("[%d] => %d\n", i, tab[i]);  // est dernier point Pourquoi tab[i] est non tab[j] notre résultat est pourtant stocker dans tab[j] 
	i++;                                                    // (tab[j] = tmp) 
	}
}

Un grand merci à celui qui pourrais m'éclairer
Les commentaires sont de moi

[Bktero]

Bonjour,

Tu as essayé de prendre un papier et un stylo, d'écrire un tableau non trié, et de dérouler l'algo à la main ? En faisant ça, tu comprendrais comment les éléments se déplacent dans le tableau.

PS : tu pourrais éditer ton profil et ajouter un t à étudian ? Parce que ça pique un peu

[Sve@r]

Bonjour

Pendant quelque heure j'ai bloqué sur un programme dont l'intitulé était de trier par ordre croissant les valeurs d'un tableau je suis tombé sur ça et j'essaye d'en saisir le sens

C'est l'algorithme du tri par sélection. A chaque itération de la grande boucle, l'élément le plus petit de tous les éléments examinés vient se placer à sa place naturelle (c'est le travail de la boucle interne). Quand la grande boucle a itéré "tab_size" fois, le tableau est trié.
Cet algo a été particulièrement mal programmé (dans le vrai algo, on chope l'élément le plus petit puis une fois celui-ci trouvé, on le permute avec l'élément en cours alors qu'ici on permute à chaque fois). Mais ça reste un tri par sélection

Code c :

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

1
2
		j = i+1;               // Ici pourquoi faire ça ? pourquoi dire que notre variable j = la valeur de i + 1 ? (j et i étant ce qui va nous permettre
		while (j < tab_size)*** // de parcourir notre tableau)

Parce que tous les éléments placés avant sont déjà triés. S'il y a un élément plus petit que l'élément en cours, il ne peut se trouver qu'après.

Code c :

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

1
2
3
					tmp = tab[i];          // Ici j'ai compris le principe on affecte notre résultat dans une variable temporaire 
					tab[i] = tab[j];       // pour ensuite la mettre dans tab[j] (un swap)
					tab[j] = tmp;

Exact, on échange tab[i] et tab[j].
Il existe une autre façon de swapper sans passer par une variable intermédiaire "tmp"

Code c :

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

1
2
3
tab[i]=tab[i]^tab[j];
tab[j]=tab[i]^tab[j];
tab[i]=tab[i]^tab[j];

Mais elle est plus coûteuse que la première (opération+affectation alors que la première ne fait qu'une affectation) et elle ne fonctionne que si "i" et "j" sont différents !!!

printf("[%d] => %d\n", i, tab[i]); // est dernier point Pourquoi tab[i] est non tab[j] notre résultat est pourtant stocker dans tab[j]

Quel résultat ? Tu as swappé deux valeurs du tableau. Si "résultat" il doit y avoir, il peut-être tout aussi bien dans l'une que dans l'autre. Pourquoi alors penses-tu qu'il est dans tab[j] ?????
Et justement c'est tab[i] l'élément en cours d'évaluation. La petite boucle est terminée, la position [i] contient la bonne valeur, on l'affiche. tab[j], lui, sera évalué plus tard.

[rosco-rs]

Un Grand merci a toi j'avais fait comme bktero m'avais conseiller et j'avais saisis déjà pas mal de choses mais avec t'es précision c'est beaucoup plus clair !

[Médinoc]

Es-tu sûr que c'est un tri par sélection? Un tri par sélection n'a qu'un seul swap par itération de la boucle externe.
Ici le swap est dans la boucle interne, ça ressemble beaucoup plus à un tri à bulles pour moi.

[Sve@r]

Un tri par sélection n'a qu'un seul swap par itération de la boucle externe.

Oui, c'est ce que j'ai dit dans ma remarque sur la façon dont il a été programmé

Ici le swap est dans la boucle interne, ça ressemble beaucoup plus à un tri à bulles pour moi.

Ca a d'abord été mon premier réflexe aussi... mais ensuite j'y ai réfléchi plus attentivement. Dans le tri à bulle, le swap se passe entre chaque élément et celui situé juste après. Ainsi à chaque itération de la boucle interne, l'élément adéquat descend le tableau pour arriver à sa bonne place en fin de tableau !!!

Dans cet algo, ce n'est pas ce qui se passe. Ici, le traitement prend chaque position dans l'ordre numérique et va ensuite chercher, en comparant chacun des autres éléments avec celui situé à cette position, quel élément devra s'y placer. Une fois que l'itération interne est terminée, c'est la position checkée qui contient le bon élément et on passe à la position suivante. Ce n'est donc pas un tri à bulles où les gros descendent vite tandis que les petits montent un peu à chaque itération ; là c'est une position et une seule qui est examinée de façon unique et définitive et les autres éléments on s'en branle ; ce qui est la caractéristique principale du tri par sélection.

Ainsi, si on a par exemple au départ 5 3 2 6 1, alors

• Cet algo donnera (pour une itération de la grande boucle)
  5 3 2 6 1
  3 5 2 6 1
  2 5 3 6 1
  2 5 3 6 1
  1 5 3 6 2
• Le tri à bulles donnera
  5 3 2 6 1
  3 5 2 6 1
  3 2 5 6 1
  3 2 5 6 1
  3 2 5 1 6
• Et le tri à bulles pris dans le sens inverse (donc de la fin vers le début)
  5 3 2 6 1
  5 3 2 1 6
  5 3 1 2 6
  5 1 3 2 6
  1 5 3 2 6

Donc à mon avis, si on fait abstraction de ce swap programmé connement dans la boucle interne, ça reste un tri par sélection. Ou, si on veut être précis, un tri par sélection avec tous les défauts du tri à bulles (donc un tri par sélection "con" )