République Tunisienne
*****
Ministère de l’Enseignement Supérieur et de la Recherche Scientifique
*****
Université de Monastir
*****
Institut Supérieur d’Informatique et de Mathématiques de Monastir
*****
Département informatique
FLASHSORT
- Un algorithme de tri linéaire innovant -
réaliser par :
ABID SARRA EL ABED RYHEM
PLAN
Introduction
Principe de l’algorithme
Fonctionnement
Introduction
Analogie simple
Imaginez devoir ranger des livres par taille sur une étagère :
Les tris comparatifs (comme le tri rapide) comparent chaque livre aux autres
Flashsort mesure d'abord les livres les plus petits et grands, puis estime
directement où placer chaque livre
C'est quoi FlashSort ?
Flashsort est un algorithme de tri non-comparatif *, conçu pour trier des données
uniformément distribuées (ex : nombres aléatoires, mesures scientifiques) en temps
linéaire moyen O(n).
développé en 1997 par Karl-Dietrich Neubert.
Comment fonctionne Flashsort ?
Phase 1 : Classification Phase 2 : Permutation sur Phase 3 : Tri local
place
1. Parcours linéaire pour
trouver min et max
Utilisation d'un tableau Application d'insertion
2. Calcul du coefficient de auxiliaire L de taille m sort sur chaque classe
classification :
Suivi de cycles pour déplacer
c = (m-1) / (max - min) chaque élément exactement une Chaque classe a en
fois moyenne n/m éléments
(petit)
3. Pour chaque élément x :
Algorithmique en O(n) sans
classe = 1 + floor(c × (x - min))
mémoire supplémentaire
4. Construction de l'histogramme
des classes
Fonctionnement
Phase 1 : Classification Phase 2 : Permutation
// Trouver min et max
← ←
min A[0], max A[0] Pour i de 0 à n-1:
Pour i de 1 à n-1: Tant que i < L[classe(A[i])]:
←
Si A[i] < min alors min A[i] ←
k classe(A[i])
←
Si A[i] > max alors max A[i] Échanger A[i] et A[L[k]]
←
L[k] L[k] - 1
// Calculer le nombre de classes
←
m 0.43 × n // ou n/10
// Initialiser le tableau de comptage Phase 3 : Tri final
←
L[1..m] 0
// Tri par insertion
// Compter les éléments par classe Pour i de 1 à n-1:
Pour i de 0 à n-1: ←
temp A[i]
←
k 1 + (m-1) × (A[i] - min) / (max - min) ←
j i-1
←
L[k] L[k] + 1 Tant que j ≥ 0 et A[j] > temp:
←
A[j+1] A[j]
// Calculer les positions cumulatives ←
j j-1
Pour k de 2 à m:
←
L[k] L[k] + L[k-1]
←
A[j+1] temp
⚡ FlashSort Expliqué Simplement
📊 Phase 1 : Classification
But : Diviser le tableau en groupes (classes) pour répartir les éléments.
Étape 1.1 : Trouver le minimum et le maximum
min ←A[0], max ←A[0]
Pour i de 1 à n-1:
Si A[i] < min alors
min ← A[i]
Si A[i] > max alors
max ← A[i]
Étape 1.2 : Calculer le nombre de classes
On détermine combien de groupes créer. La formule magique : environ 43% du nombre d'éléments.
m ← 0.43 × n // ou n/10 pour simplifier
💡 Pourquoi 0.43 ? C'est le résultat de calculs mathématiques qui optimisent la
performance. Pour 8 éléments, on aurait environ 3-4 classes.
Étape 1.3 : Compter les éléments par classe
On détermine à quelle classe appartient chaque élément et on compte combien il y en a dans chaque classe.
// Initialiser le compteur L[1..m] ←
0 // Compter
Pour i de 0 à n-1:
k ←
1 + (m-1) × (A[i] - min) / (max - min) L[k] ← L[k] + 1
💡 La formule expliquée :
- On soustrait min pour ramener tout à partir de 0
- On divise par la plage totale (max - min) pour obtenir une proportion
- On multiplie par le nombre de classes pour trouver la classe appropriée
Étape 1.4 : Calculer les positions cumulatives
On transforme les comptages en positions finales dans le tableau
Pour k de 2 à m: L[k] ← L[k] + L[k-1]
💡 Exemple :
Si Classe 1 a 3 éléments, Classe 2 a 3 éléments, Classe 3 a 2 éléments
L[1] = 3,
L[2] = 6 (3+3),
L[3] = 8 (6+2)
Cela nous dit où chaque classe se termine dans le tableau final.
🔄 Phase 2 : Permutation
But : Déplacer chaque élément vers sa classe en une seule passe efficace.
Le processus de permutation
On parcourt le tableau et on place directement chaque élément à sa position finale en
utilisant des échanges intelligents.
Pour i de 0 à n-1:
Tant que i < L[classe(A[i])]:
k ←
classe(A[i])
Échanger A[i] et A[L[k]] L[k] ←
L[k] - 1 - 1
💡 Comment ça marche ?
- On regarde l'élément actuel
- On trouve sa classe et sa position finale
- On l'échange avec l'élément qui occupe cette position
- On continue jusqu'à ce que tous soient bien placés
✨ Phase 3 : Tri final
But : Finaliser le tri avec un tri par insertion, très rapide sur des données presque triées.
Tri par insertion classique
Chaque élément est inséré à sa bonne place dans la partie déjà triée.
Pour i de 1 à n-1: temp ← A[i] j ← i - 1 Tant que j ≥ 0 et A[j] > temp: A[j+1] ←
A[j] j ← j - 1 A[j+1] ← temp
✅ Pourquoi c'est rapide ici ?
Grâce aux phases 1 et 2, le tableau est PRESQUE trié. Le tri par insertion est extrêmement efficace dans ce
cas, car il y a très peu de déplacements à faire !
Meilleur cas cas moyen pire cas
O(n) O(n) O(n²)
Distribution uniforme Donnée aléatoires Distribution déséquilibrée
complexité spatiale
O(1)
trie en place - mémoire constante supplémentaire
performance optimale : n +m (n element , m classes)
Propriétés de base
Propriété Flashsort
==>Ne préserve pas l’ordre relatif des
Stabilité Non
éléments égaux
==>Permutation sans tableau auxiliaire
In-place Oui
pour les éléments
Déterministe Oui ==>Mêmes entrées → même résultat
Avantages
Très rapide en pratique Efficace en mémoire
Complexité linéaire O(n) pour des Tri en place avec O(1) mémoire
données uniformément distribuées supplémentaire
Simplicité d'implémentation Adaptatif
Algorithme relativement simple à Performance excellente sur des
comprendre et à coder données quasi-triées
Limites
Limité aux données
Sensible à la distribution numériques
Performance dégradée (O(n²)) si les Nécessite des valeurs min/max
données ne sont pas uniformément clairement définies
distribuées
Non stable Peu connu
Ne préserve pas l'ordre relatif des Moins utilisé et documenté que
éléments égaux les algorithmes classiques
Applications pratiques
📊 Bases de données 💰 Finance
Tri de grandes tables avec distribution Tri de transactions ou de prix
uniforme
🎮 Jeux vidéo 📈 Analyse de données
Tri de scores ou classements Prétraitement de datasets numériques
Conclusion
✅ Excellent choix pour des données numériques uniformément distribuées
✅ Très efficace en termes de mémoire et de vitesse dans le cas optimal
⚠️ À éviter si la distribution est inconnue ou très déséquilibrée
🎯 Alternative performante aux tris comparatifs classiques dans des contextes spécifiques
Merci
Pour votre attention