Besoin de compréhension sur un algo

Version imprimable

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:

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

14/08/2019, 10h05
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 :(

Bonjour

Citation:

Envoyé par rosco-rs

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
https://www.youtube.com/watch?v=qpeeRU_K90k
Citation:
Envoyé par rosco-rs
Code:

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.
Citation:
Envoyé par rosco-rs
Code:

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:

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 !!!

Citation:

Envoyé par rosco-rs

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.

14/08/2019, 23h04
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 ;) !
16/08/2019, 11h46
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.
16/08/2019, 12h24
Sve@r
Citation:

Envoyé par Médinoc

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é

Citation:

Envoyé par Médinoc

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" :mouarf:)