Quelques algorithmes simples

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.