1. Introduction

1.1. Le mot le plus long

Lequel de ces mots est le plus long :

• table
• ordinateur
• chaise

Facile. Mais pouvez-vous expliquer votre méthode ?

Plus une tâche est facile, plus elle peut être difficile à expliquer. Surtout à un ordinateur, idiot et incapable d’intuition ou de prise d’initiative, et qui plus est au travers d’un langage de programmation.

Essayons quand même.

variables: liste_de_mots, mot_courant, mot_le_plus_long
mot_le_plus_long = ""
Pour chaque mot_courant dans liste_de_mots:
    Si longueur(mot_courant) > longueur(mot_le_plus_long):
        mot_le_plus_long = mot_courant
    Fin Si
Fin Pour

1.2. Trier une liste de mots

Tâche plus complexe : trier la liste des mots.

• table
• ordinateur
• chaise

Facile. Mais pouvez-vous expliquer votre méthode ?

Essayez quand même ! Y a-t-il plusieurs méthodes ? Plusieurs solutions (c’est-à-dire plusieurs listes différentes pouvant être considérées comme triées) ? Votre méthode fonctionne-t-elle encore avec des listes plus longues ?

1.3. Généralités sur le tri

1.3.1. Dans la nature

1.3.1.1. Tableaux de données

Qui n’a jamais vu d’explorateur de fichiers, de tableur, de liste de sportifs ou d’élèves ?

1.3.1.2. Autres exemples

• Z-sorting pour la 3D,
• opérations bancaires,
• …

Selon Cormen, Leiserson, Rivest, and Stein, un quart des cycles serait consacrés au tri.

1.3.2. Place de ces algorithmes

Au niveau du lycée, on pourrait dire que les algorithmes de tri sont les premiers parmi les algorithmes « avancés ».

Ils constituent quasiment une science à part entière, et sont utilisés comme base pédagogique pour accéder à divers concepts.

2. Présentation de quelques algorithmes

2.1. Avec des tresses

sortvis.org

2.2. Avec des danses

algo-rythmics

2.3. Avec des bâtons

sorting-algorithms.com

2.4. Avec représentation sonore

video sur YouTube

2.5. Avec des balles

sorting.at

3. Les définitions

Quelques liens vers des articles Wikipedia :

• algorithmes de tri
• tri stupide (bogosort)
• tri à bulles (bubble sort)
• tri par sélection (selection sort)
• tri par insertion (insertion sort)
• tri de Shell (shell sort)
• tri fusion (merge sort)
• tri rapide (quick sort)
• tri par tas (heap sort)
• …

4. Implémentation de quelques algorithmes

4.1. Bases algorithmiques

4.1.1. Pour tester ces fragments

4.1.1.1. Python

Brython

4.1.1.2. Javascript

Un navigateur, avec document.write() ou console.log(), voire nodejs avec console.log(). Pour un code portable :

print = console.log
print = document.write

Pour visualiser graphiquement, il serait possible d’utiliser http://d3js.org/.

4.1.1.3. Processing

Processingjs

Pour visualiser graphiquement, il est possible d’utiliser ce squelette.

4.1.2. Lire et écrire dans un tableau ou une liste

4.1.2.1. Python

liste = [3, 2, 0, 4, 1]
print(liste)
print(liste[0])
print(liste[4])
liste[4] = 5
print(liste[4])

donnera :

[3, 2, 0, 4, 1]
3
1
5

4.1.2.2. Javascript

tab = [3, 2, 0, 4, 1]
console.log(liste)
console.log(liste[0])
console.log(liste[4])
tab[4] = 5
console.log(liste[4])

donnera :

[3, 2, 0, 4, 1]
3
1
5

4.1.2.3. Processing

int[] tab = new int[5];
tab[0] = 3;
tab[1] = 2;
tab[2] = 0;
tab[3] = 4;
tab[4] = 1;
println(tab);
println(tab[0]);
println(tab[4]);
tab[4] = 5;
println(tab[4]);

donnera :

[0] 3
[1] 2
[2] 0
[3] 4
[4] 1
3
1
5

4.1.3. Parcourir un tableau ou une liste

4.1.3.1. Python

liste = [3, 2, 0, 4, 1]
for elt in liste:
    print(elt)

et

liste = [3, 2, 0, 4, 1]
for i in range(len(liste):
    print(elt)

donneront :

3
2
0
4
1

4.1.3.2. Javascript

tab = [3, 2, 0, 4, 1]
for(var i = 0; i < tab.length; i++) { 
    console.log(tab[i])
}

donnera :

3
2
0
4
1

4.1.3.3. Processing

int[] tab = new int[5];
tab[0] = 3;
tab[1] = 2;
tab[2] = 0;
tab[3] = 4;
tab[4] = 1;
for(int i = 0; i < tab.length; i++) {
    println(tab[i]);
}

donnera :

3
2
0
4
1

4.1.4. Algorithme mystère

En pseudo-code :

// Initialisations:
a <- 2
b <- 5
// Algo:
auxi <- a  // auxi est une variable auxiliaire
a <- b
b <- auxi

Tracer cet algorithme pour en deviner le rôle.

4.2. Implémentation de quelques algorithmes

Après avoir choisi un langage de programmation, implémenter les algorithmes suivants :

4.2.1. Bubble sort

Rappel de la définition

Ces videos et ce squelette pourront vous aider.

4.2.2. Selection sort

Rappel de la définition

Cette video et ce squelette pourra vous aider.

5. Approfondissements

5.1. Trier des chaînes de caractère

Remplacer les nombres par des mots (plus facile en Python et Javascript). Quel ordre obtient-on (pour pas cher) ? Comment trier les mots en fonction de leur longueur ?

Comment un dictionnaire trie les noms à particule ? Cet ordre est-il respecté ?

5.2. Comparer les algorithmes

Les critères sont innombrables :

• nombre d’échanges,
• nombre de comparaisons,
• place nécessaire en mémoire,
• …

5.3. Tests sur données particulières

Les algorithmes ont souvent des situations de départ de prédilection. Voir http://www.sorting-algorithms.com.

6. Références

• Wikipedia
• Les algorithmes de tri (pdf)
• Algorithmes de tri en JS