Suivez-nous sur X
|
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z,
ALL
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
0,
A,
B,
C,
D,
E,
F,
G,
H,
I,
J,
K,
L,
M,
N,
O,
P,
Q,
R,
S,
T,
U,
V,
W,
X,
Y,
Z
|
|
A propos d'Obligement
|
|
David Brunet
|
|
|
|
En pratique : Algorithmes et structures de données - Les tris
(Article écrit par Lucien Turski-Marcon et Bruno Bailluet et extrait d'Amiga News Tech - juin 1992)
|
|
Chose promise, chose due, nous allons aborder les différentes méthodes de tri. Nous allons d'abord
étudier trois types de tri, que nous décrirons succinctement avant de passer aux procédures et schémas
explicatifs.
Tri à bulles
Qui ne l'a pas utilisé ? Cette méthode est la plus naturelle de toutes, puisqu'elle
consiste en une série de comparaisons et de permutations entre les différents éléments, afin d'en faire
ressortir celui qui correspond au critère de selection (le plus grand ou le plus petit) pour le placer à l'une
des extrémités de la zone de tri (le tableau tout simplement).
Tri par sélection
Cette méthode consiste à ramener le plus petit élément en début de tableau. Il
s'agit d'une variante du tri à bulles qui a le mérite d'être moins gourmande en nombre de permutations. En effet,
la permutation ne s'effectue qu'après avoir parcouru tout le tableau (entre deux bornes qui diminuent au fil de
la progression) pour retrouver l'élément de plus petite valeur.
Tri par insertion
Il s'agit là d'une méthode dont le principe est de parcourir séquentiellement les
données à trier ; pour chaque donnée lue, on recherche sa place parmi les données déjà triées puis on l'insère
à l'endroit adéquat, en décalant les données déjà triées qui lui sont supérieures d'un cran vers la droite.
Chaque procédure est accompagnée d'un petit schéma qui vous permettra de suivre le déroulement de la méthode sur une ou
deux étapes.
Et pour couronner le tout, un petit source C optimisé qui récapitule les trois méthodes.
#include <exec/types.h>
#include <stdio.h>
#define MAX 16
VOID TriSelect (int t[], int N);
VOID TriBulle (int t[], int N);
VOID TriInsert (int t[], int N);
main()
{
int tab[MAX], i, choix = 0;
while (1)
{
puts ("1. Tri BULLE");
puts ("2. Tri par SELECTION");
puts ("3. Tri par INSERTION");
puts ("4. Sortie");
printf ("\n\nVOTRE CHOIX : ");
scanf ("%d",&choix);
switch (choix)
{
case 1 :
for (i = 0; i < MAX; i++)
{
printf ("Entrez l'element N° %d : ",i);
scanf ("%d",&tab[i]);
}
TriBulle (tab,MAX);
break;
case 2 :
for (i = 0; i < MAX; i++)
{
printf ("Entrez l'element N° %d : ",i);
scanf ("%d",&tab[i]);
}
TriSelect (tab,MAX);
break;
case 3 :
for (i = 0; i < MAX; i++)
{
printf ("Entrez l'element N° %d : ",i);
scanf ("%d",&tab[i]);
}
TriInsert (tab,MAX);
break;
case 4 :
exit (0);
default :
break;
}
printf ("Voici le tableau trie : \n");
for (i = 0; i < MAX; i++)
printf ("Element %d : %d\n",i,tab[i]);
}
}
VOID TriBulle (int t[], int N)
{
int i, j, v;
for (i = N; i >= 1; i--)
for (j = 1; j < i; j++)
if (t[j-1] > t[j])
{
v = t[j-1];
t[j-1] = t[j];
t[j] = v;
}
}
VOID TriInsert (int t[], int N)
{
int i, j, v;
for (i = 1; i <= N; i++)
{
v = t[i];
j = i;
while ((t[j-1] > v) && (j != 0))
{
t[j] = t[j-1];
j--;
}
t[j] = v;
}
}
VOID TriSelect (int t[], int N)
{
int i, j, min, q;
for (i = 0; i < N; i++)
{
min = i;
for (j = i+1; j <= N; j++)
if (t[j] < t[min])
min = j;
q = t[min];
t[min] = t[i];
t[i] = q;
}
}
|
|