Complexité

Tri du joueur de cartes

Le tri par insertion est un tri « naturel » souvent qualifié de « tri du joueur de carte ».
Comment un joueur de carte trie-t-il ses cartes ?

• Au début, la main gauche du joueur est vide et ses cartes sont posées sur la table.
• Le joueur prend alors sur la table les cartes, une par une avec sa main droite, pour les placer dans sa main gauche.
• Pour savoir où placer une carte dans son jeu, le joueur la compare avec chacune des cartes déjà présentes dans sa main gauche, en examinant les cartes de la droite vers la gauche.
• À tout moment, les cartes tenues par la main gauche sont triées ; ces cartes étaient, à l’origine, les cartes situées au sommet de la pile sur la table.

1. Choisir sept cartes à jouer. Les placer en ligne au hasard sur une table et mettre en œuvre la technique décrite ci-dessus.
   Se filmer pendant toute l’opération en commentant chacune des étapes !

Tri par insertion

Introduction

La méthode du tri par insertion est ilustré à cette adresse, ou, de façon plus folklorique, à cette adresse.

La recherche d’un élément dans un tableau est beaucoup plus efficace si ce tableau est ordonné. À vrai dire, ce n’est pas en cours d’informatique que vous avez découvert ceci : dans toutes les bibliothèques les livres sont classés de façon à rendre leur recherche plus rapide !

La question que se propose d’aborder ce document est donc : « comment classer les éléments d’un tableau selon une relation d’ordre donnée ? ».

Rappel : Type de Données Abstrait (TDA)

Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :

• Son nom ;
• Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.

Qu’est-ce qu’une file ?

Rappel : Type de Données Abstrait (TDA)

Une structure de données ou type de données abstrait est un moyen d’organiser et de manipuler les données en mémoire. Un TDA est donc définit par :

• Son nom ;
• Sa spécification, c’est à dire la liste des manipulations/opérations que l’on peut ou pas effectuer. La spécification indique généralement la complexité de chacune des opérations prévues par le TDA.

Qu’est-ce qu’une pile ?

Tableaux

Remarque : Dans la suite de ce document, on va considérer que la liste Python tab, créé par l’instruction tab = [i for i in range(20)] est de longueur fixe. Elle se comporte alors comme un tableau.

Python possède dans la bibliothèque standard un grand nombre de structures de données, programmées de manière efficace.

Rappels : modules, fonctions

Algorithmique

En informatique, pour qu’un algorithme puisse être implémenté, il est nécessaire de s’assurer que la « suite finie et non ambiguë d’opérations ou d’instructions à réaliser » s’effectue en une durée finie .

Recherche d’un élément dans un tableau

La recherche d’éléments dans un tableau a déjà été évoquée en classe de première. Les deux algorithmes mis en œuvre à cette occasion, la recherche linéaire et la recherche dichotomique, utilisaient des boucles.
L’objectif de cette séance est de rapidement revoir ces algorithmes et de mettre en œuvres des algorithmes récursifs de même complexité. Quatre algorithmes de recherche vont donc être implémentés :

• La recherche linéaire itérative ;
• La recherche linéaire récursive ;
• La recherche dichotomique itérative ;
• La recherche dichotomique récursive.

Travail à faire

• Implémenter en Python les cinq algorithmes suivants et répondre aux questions.

Recherche séquentielle (ou linéaire)

Recherche séquentielle itérative