NOMBRES - Curiosités, théorie et usages

Accueil / Dictionnaire / Rubriques / Index / Atlas / Références /    Nouveautés

ORIENTATION GÉNÉRALE    -   M'écrire   -   Édition du: 07/08/2016

Débutants

Général

LOGIQUE

Glossaire

Général

 

Méthode de TRI

 

 

 

 

Introduction

 

Sommaire de cette page

>>> Gestion de piles

>>> Tri classique

>>> Tri par bulle

>>> Comparaison

 


 

LOGIQUE DE TRI

en informatique

 

 

*       Une formalité pour le cerveau humain.

*       Un casse-tête pour l'ordinateur.

 

 

Gestion de piles

 

FIFO

          first in first out

 

Premier entré, premier sorti.

 

Comme la pile de paquets de chewing-gum dans les distributeurs.

 

 

LIFO

          last in first out

 

Dernier entré, premier sorti.

 

Comme la pile de mouchoirs dans votre armoire.

 

 

 

TRI CLASSIQUE

 

Explication du processus (voir illustrations plus bas)

 

Étape 1 – Opération 1: Trouver la valeur la plus petite;

Opération 2: La mémoriser;

Dans la pile, la cellule devient vacante.
Opération 3: Déplacer d'un cran vers la droite toutes les valeurs situées dans les cellules à gauche de la cellule vacante;

La cellule de tête à gauche devient vacante.
Opération 4: Placer la valeur mémorisée dans la cellule vacante;

La valeur la plus petite se retrouve ainsi en tête de pile, à gauche.

Fin de l'étape 1.

Étapes suivantes: Recommencer cette procédure avec la nouvelle valeur la plus petite dans la pile;

Fin lorsque la nouvelle valeur la plus petite est dans la cellule à l'extrémité droite de la pile.

 

Étape 1 – Détail des opérations

 

Départ

6

7

1

56

42

13

3

Mémo

Opération 1

 

 

1

 

 

 

 

1

2

6

7

 

56

42

13

3

1

3

 

6

7

56

42

13

3

1

4

1

6

7

56

42

13

3

 

 

Toutes les étapes

 

Départ

6

7

1

56

42

13

3

Étape 1

1

6

7

56

42

13

3

2

1

3

6

7

56

42

13

3

1

3

6

7

13

56

42

4

1

3

6

7

13

42

56

 

 

 

TRI par BULLE

 

 

On prend les deux premiers nombres.

S’ils sont dans le bon ordre, on ne change pas.

Sinon, on inverse.

On recommence avec 2e et le 3e .

Etc.

 

En chiffres rouges, les deux cellules analysées.

En jaune, les nombres bien placés.

Cellules en bleu: le parcours du nombre 3.

 

Départ

6

7

1

56

42

13

3

1

6

7

1

56

42

13

3

2

6

1

7

56

42

13

3

3

6

1

7

56

42

13

3

4

6

1

7

42

56

13

3

5

6

1

7

42

13

56

3

6

6

1

7

42

13

3

56

7

1

6

7

42

13

3

56

8

1

6

7

42

13

3

56

9

1

6

7

42

13

3

56

10

1

6

7

13

42

3

56

11

1

6

7

13

3

42

56

12

1

6

7

13

3

42

56

13

1

6

7

13

3

42

56

14

1

6

7

13

3

42

56

15

1

6

7

13

3

42

56

16

1

6

7

3

13

42

56

17

1

6

7

3

13

42

56

18

1

6

7

3

13

42

56

19

1

6

7

3

13

42

56

20

1

6

7

3

13

42

56

21

1

6

3

7

13

42

56

22

1

6

3

7

13

42

56

23

1

6

3

7

13

42

56

24

1

6

3

7

13

42

56

25

1

6

3

7

13

42

56

26

1

3

6

7

13

42

56

27

1

3

6

7

13

42

56

28

1

3

6

7

13

42

56

29

1

3

6

7

13

42

56

30

1

3

6

7

13

42

56

 

Il y a beaucoup plus d’opérations que dans le cas du tri classique,

mais l'algorithme est plus simple pour l’informatique.

 

Observez le nombre 3 qui se propage de la droite vers la gauche,

comme une " bulle " qui remonte à la surface (ici, vers la droite).

 

 

 

Comparaison – Vitesse de tri

 

Tri classique

 

 

Le nombre d'opérations à effectuer est proportionnel au carré de la quantité d'objets à trier.

 

Pour 1000 fiches

T = (103)² t

= 106 t

 

Tri à bulles

ou par petits paquets

 

Le nombre d'opérations à effectuer est proportionnel au produit du nombre d'objets par son logarithme.

 

Pour 1000 fiches

T = 103 ln 100

    = 6, 9 103 t

 

Comparaison

N

N . ln N

Ratio

10

100

23,02

4,3

100

10000

460,51

21,7

1000

1000000

6907,75

144,7

10000

100000000

92103,40

1085,7

100000

10000000000

1151292,54

8685,8

 

Référence: pages 84 et 85 du livre cité

 

 


  

Suite

*    Algorithmes

*    Outils de la logique

Voir

*    Intelligence artificielle

*    Raisonnement

*    Énigmes et paradoxes

*    Fractales

Livre

Espèce de Trochoïde – Luc de Brabandere et Christophe RibesseDunod – 2006: Florilège de 50 idées mathématiques expliquées au profane. Superbe!