NOMBRES - Curiosités, théorie et usages

 

Accueil                           DicoNombre            Rubriques           Nouveautés      Édition du: 07/07/2019

Orientation générale        DicoMot Math          Atlas                   Références                     M'écrire

Barre de recherche          DicoCulture              Index alphabétique                      Brèves de Maths

      

LOGIQUE

 

Débutants

Général

Méthode de TRI

 

Glossaire

Général

 

 

INDEX

 

Logique

 

Programmation

 

Introduction

Tri avec Python et Maple

Tri rapide (Quiksort)

 

Sommaire de cette page

>>> Gestion de piles

>>> Tri classique

>>> Tri par bulle

>>> Comparaison

>>> Programmation

>>> Efficacité ?

 

 

 

 

 

LOGIQUE DE TRI

en informatique

 

*       Une formalité pour le cerveau humain.

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

*       Il existe de nombreux algorithmes de tri.

 

 

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

 

 

 

 

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 1000

    = 6, 9 103 t

 

Comparaison

N

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é

Note

Malgré la référence, cette comparaison ne tient pas par rapport au tableau présenté par Wikipédia.

*    Au pire: chacun des tris exige n² opérations.

*    Au mieux: n log n pour le classique et n pour le tri à bulles.

 

 

Programmation Maple

 

Commentaires

Déclaration de la procédure ( en fait, une sorte de nouvelle instruction)
Déclaration des paramètres utilisés à l'intérieur de la procédure.

NN mémorise la liste N pour travail en interne et q en donne la quantité d'éléments.

 

Les deux boucles fonctionnent comme ceci:

*       Après une première passe, le nombre le plus grand se retrouve à droite dans la liste.

*       À la passe suivante, le nombre le plus grand étant positionné à droite, on examine les autres nombres: tous sauf le dernier.

*       À la passe suivante, examen de tous les nombres sauf les deux derniers.

*       Et ainsi de suite jusqu’à la dernière passe qui consiste à comparer le premier nombre au deuxième.

 

La procédure retourne la liste NN triée.

Fin de procédure

 

Essais avec une liste quelconque et effet de tri sur cette liste.

Voir Programmation – Index

 

Efficacité ?

Tout programme de tri qui garantit une complexité de N log N est le meilleur. C'est prouvé. En moyenne l'algorithme de tri rapide (quicksort) réalise cette performance.

Néanmoins, pour certains types particuliers de données, il peut exister de meilleurs algorithmes que ceux-ci.

Le tri à bulles, simple à implémenter, est un algorithme lent. Vous trouverez la comparaison entre divers algorithme sur la page Wikipédia.

 

 

 

  

Suite

*    Tri et problème polynomial

*    Algorithme de tri Quicksort

*    Algorithmes

*    Outils de la logique

Voir

*    Intelligence artificielle

*    Raisonnement

*    Énigmes et paradoxes

*    Fractales

Livre

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

Sites

*      Algorithmes de tri – Wikipédia avec comparaison des vitesses de tri

*    Algorithmes de tri – Pascal Loewenguth

*    Tri rapide – Wikipédia

*    Sorting Algorithms – Better Explained

*    15 algorithmes de tri en 6 minutes – VideoMan – Vidéo amusante.

*    Sorting Algorithms Animations – toptal

*    Sorting Algorithms – GeeksforGeeks – Tout sur tous les algorithmes connus y compris détails des algorithmes

*    A tour of the top 5 sorting algorithms with Python code – George Seif

Cette page

http://villemin.gerard.free.fr/Wwwgvmm/Logique/Tri.htm