I – Introduction
Introduction à l’algorithmique : https://pixees.fr/informatiquelycee/n_site/nsi_prem_intro_algo.html
Qu’est-ce qu’un algorithme ?
Voici deux définitions trouvées dans la littérature :
- Procédure de calcul bien définie qui prend en entrée une valeur ou un ensemble de valeur, et qui donne en sortie une valeur ou un ensemble de valeur.
- Un algorithme est la spécification d’un schéma de calcul sous forme d’une suite finie d’opérations élémentaires obéissant à un enchainement déterminé.
II – Tri par insertion, par sélection
Les algorithmes de tri des éléments d’un tableau ont une place à part en algorithmique. En effet, ils sont souvent utilisés pour mettre en évidence certains concepts algorithmiques (concepts que l’on retrouve dans d’autres types d’algorithmes).
II – A Tri par insertion : tri par sélection
Voici l’algorithme du tri par sélection :
VARIABLE t : tableau d'entiers i : nombre entier j : nombre entier k : nombre entier DEBUT j←2 tant que j<=longueur(t): //boucle 1 i←j-1 k←t[j] tant que i>0 et que t[i]>k: //boucle 2 t[i+1]←t[i] i←i-1 fin tant que t[i+1]←k j←j+1 fin tant que FIN
Remarque : il est possible de mettre des commentaires à l’aide de « // » afin de rendre la compréhension des algorithmes plus aisée
Poursuivez le travail commencé ci-dessous (attention de bien donner l’état du tableau à chaque étape) :
II – B Tri par sélection
Voici l’algorithme du tri par sélection :
VARIABLE t : tableau d'entiers i : nombre entier min : nombre entier j : nombre entier DEBUT i←1 tant que i<longueur(t): //boucle 1 j←i+1 min←i tant que j<=longueur(t): //boucle 2 si t[j]<t[min]: min←j fin si j←j+1 fin tant que si min≠i : échanger t[i] et t[min] fin si i←i+1 fin tant que FIN
Poursuivez le travail commencé ci-dessous (attention de bien donner l’état du tableau) :
On peut résumer le principe de fonctionnement de l’algorithme de tri par sélection avec le schéma suivant :
III – Exercices
Pour chacune des questions qui suivent, écrire un algorithme permettant de résoudre le problème puis le coder en python.
Lien des tests :
III – A trouver l’indice d’une valeur donnée dans un tableau
La méthode index permet de renvoyer l’indice de l’élément dans la liste s’il a été trouvé.
III – B Écrire une fonction qui retourne le minimum d’un tableau
III – C Écrire une fonction qui retourne le maximum d’un tableau
III – D Écrire une fonction qui renvoi le min et le max d’un tableau
III – E Écrire une fonction qui échange 2 valeurs d’un tableau
IV – Efficacité des tris
Pour comprendre le tri par insertion : http://lwh.free.fr/pages/algo/tri/tri_insertion.html
Pour comprendre le tri par sélection : http://lwh.free.fr/pages/algo/tri/tri_selection.html
Pour apprendre à exécuter un script « à la main » pour mieux le comprendre vous pouvez vous aider de python tutor.
Aucune réponse