Structures de données IFT-2000 Abder Alikacem Semaine 14 Les algorithmes de tri Département dinformatique et de génie logiciel Édition septembre 2009

Structures de données

IFT-2000

Abder AlikacemAbder Alikacem

Semaine 14Les algorithmes de tri

Département d’informatique et de génie logiciel

Édition septembre 2009

! +

Plan

• Définitions et propriétés• Les algorithmes de tri simples et leur complexité• Les algorithmes de tri complexes et leur complexité

• Le tri rapide (QuickSort)• Le tri-fusion (MergeSort)• Le tri par arbre (TreeSort)• Le tri par monceau (HeapSort)

Traitement de données triées

• Le traitement de données déjà triées est plus rapide.

• Nécessaire pour le traitement séquentiel d’intervalles.

• Il faut trier des données à bas coût !• nb de comparaisons• nb de déplacements d’éléments• espace mémoire requis

Tri selon une relation d’ordre

Besoin :• attribut de tri (clé) : <nom,…>, <nom,prénom,...>• que l’on peut comparer {<,=,>} (c.-à-d. ordre total)

déplacer toute l’information : <clé,...>ou <clé,indirection>, + indirection vers l’information

Il faut trier des données à bas coût !

• nb de comparaisons• nb de déplacements d’éléments• espace mémoire requis

Critères d'analyse

Complexité en temps : 2 critères de base• nombre de comparaisons entre clés• nombre de transferts (ou d’échanges) d'éléments

Complexité en place mémoire : nécessaire au tri• tri sur place (in situ) : en O(1)• tri à côté : en O(n) • tri récursif : utilise une pile

Stabilité• conserve l'ordre originel pour éléments de clés égales

Progressivité• à l'étape k trie les k premiers éléments de la liste

Configuration particulière des données : aléatoires, triées, inversées, égales, presque triées

Critères d'analyse

• Meilleur cas: tableau déjà trié

• Cas moyen: tableau aléatoire

• Pire cas: tableau trié à l’envers

1 3 5 7 9 10

13

18

21

25

7 10

21

9 1 25

18

3 5 13

25

21

18

13

10

9 7 5 3 1

Les algorithme de tri

Les algorithmes de tri «classiques»:• Tris élémentaires

• tri insertion;• tri sélection;• Etc..

• Tris dichotomiques• tri rapide (Quick Sort);• tri fusion;

• Tris par structure• tri par arbre (Tree Sort);• tri par monceau (Heap Sort)• tri pigeonnier (Pigeon Hole).• tri basique

• Tri aléatoire• … et le Bogo tri

Méthodes simples de tri

Intérêts pédagogiques (terminologie et mécanismes fondamentaux)

Tris simples plus efficaces • sur des petites listes (moins de 50 éléments)• sur des listes presque triées• sur des listes contenant un grand nombre de clés égales

Certains tris complexes• sont améliorés en faisant appel à des tris simples sur une partie des

données

Tris simples

Algorithme#1 :

insérer chacun des n éléments à la bonne place dans le tableau créé jusqu’ici

Tri par insertion :

44,55,12,42,94,18,06,67

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

44

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

44

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,55

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,55

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,55

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,55

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,55

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,55

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,9412,18,42,44,55,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,9412,18,42,44,55,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,9412,18,42,44,55,9406,12,18,42,44,55,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,9412,18,42,44,55,9406,12,18,42,44,55,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,9412,18,42,44,55,9406,12,18,42,44,55,9406,12,18,42,44,55,67,94

Tris simples

tri par insertion :

44,55,12,42,94,18,06,67

4444,5512,44,5512,42,44,5512,42,44,55,9412,18,42,44,55,9406,12,18,42,44,55,9406,12,18,42,44,55,67,94

Tris simples

Tri par insertion

template template < < typenametypename T>T>voidvoid TriInsertion(vector<T>& Tableau, int n) TriInsertion(vector<T>& Tableau, int n){{

intint j; j;T Tmp;T Tmp;forfor ( (intint i=1;i<n; i++ ) i=1;i<n; i++ ){ {

//Placer l'element courant dans la variable tampon//Placer l'element courant dans la variable tamponTmp = Tableau[i];Tmp = Tableau[i];j=i;j=i;

//Tant que la position d'insertion n'est pas atteinte...//Tant que la position d'insertion n'est pas atteinte...whilewhile ( (--j>=0) && (Tmp<Tableau[j]) ) ( (--j>=0) && (Tmp<Tableau[j]) )

Tableau[j+1]=Tableau[j];Tableau[j+1]=Tableau[j];Tableau[j+1]=Tmp;Tableau[j+1]=Tmp;

}}}}

Tris simples

tri stable?tri in situ?progressif?

Meilleur cas : séquence triée•nb de comparaisons ? •nb de déplacements ?

Pire cas : séquence triée inverse•nb de comparaisons ? •nb de déplacements ?

Tri par insertion• insérer chacun des n éléments à la bonne place dans le tableau créé

jusqu’ici

Tris simples

Tri par insertion :

• insérer chacun des n éléments à la bonne place dans le tableau créé jusqu’ici …


Meilleur cas : séquence triée•nb de comparaisons ? O(n) O(n log n)•nb de déplacements ? O(1)

Pire cas : séquence triée inverse•nb de comparaisons ? O(n2) O(n log n)•nb de déplacements ? O(n2)

Tris simples

Tri par insertion dichotomique :

• Idée • au lieu de parcourir les i premiers éléments triés pour faire l'insertion

du i + 1 ième, rechercher la place où insère par dichotomie.

• Complexité• nb de transferts est identique à celui de l'insertion séquentielle O(n2)

dans le pire des cas et en moyenne• nb de comparaisons en O(n log n) (au pire et en moyenne)

• En pratique : n'améliore pas vraiment les performances

Tri shell, Donald Shell

• Une variante du tri par insertion • Lenteur du tri par insertion

• les échanges ne portent que sur des voisins si le plus petit élément est à la fin il faut n étapes pour le placer définitivement

• Principe du tri shell • éliminer les plus grands désordres pour abréger le travail aux étapes

suivantes• Idée

• ordonner des séries d'éléments éloignés de h, h prenant de valeurs de plus en plus petites (jusqu'à 1)

• Exemple (suite déterminée empiriquement)

• hn = (1093, 384, 121, 40, 13, 4, 1)

• Hn+1 = 3 hn +1

Tris simples

Tri shell

template <typename T>void triShell(vector<T> & Tableau, int n) { … while (p <= n) { p = (3 * p) + 1; } while (p > 0) { ….

p = p/3; }

}

Tri shell

• On a démontré que la complexité dans le pire des cas est O(n3/2 ).

• En choisissant pour suite d'incréments

1, 3, 7, 15, 31 ( hi+1 = 2hi + 1) on obtient expérimentalement une complexité en O(n1,2 ).

• Très efficace jusqu'à 5000 éléments que les données soient aléatoires, triées ou en ordre inverse, code facile et compact, conseillé quand on n'a aucune raison d'en choisir un autre.

Tris simples


Tris simples

Algorithme#2

• remplir les cases de 1 à n avec le minimum des éléments du tableau restant

3154

6478

1742

3154

6418

7742

123456789

101112

123456789

101112

reste à classerMIN

échange

Tris simples

Algorithme#2

Recherche du minimum par balayage séquentiel

Tris simples

Tri par sélection :

44,55,12,42,94,18,06,67

Algorithme :• remplir les cases de 1 à n avec le minimum des

éléments du tableau restant

Tris simples

tri par sélection :

44,55,12,42,94,18,06,67

Tris simples


44,55,12,42,94,18,06,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,67

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,6706,12,18,42,44,55,67,94

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,6706,12,18,42,44,55,67,94

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,6706,12,18,42,44,55,67,94

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,6706,12,18,42,44,55,67,9406,12,18,42,44,55,67,94

Tris simples


44,55,12,42,94,18,06,67

06,55,12,42,94,18,44,67 06,12,55,42,94,18,44,67 06,12,18,42,94,55,44,67 06,12,18,42,94,55,44,6706,12,18,42,44,55,94,67 06,12,18,42,44,55,94,6706,12,18,42,44,55,67,9406,12,18,42,44,55,67,94

Tri par sélection

templatetemplate<<typenametypename T> T>voidvoid TriSelection( vector<T>& Tableau, int n) TriSelection( vector<T>& Tableau, int n){ { int min;int min; T Tmp;T Tmp; forfor ( (intint i=0 ; i<n-1 ; i++ ) { i=0 ; i<n-1 ; i++ ) {

////RechercheRecherche de l'ind de l'indiceice du plus petit element du plus petit element min = i;min = i; forfor ( (intint j=i+1 ; j<n ; j++ ) { j=i+1 ; j<n ; j++ ) { if if ( Tableau[j]<Tableau[min] )( Tableau[j]<Tableau[min] ) min = j;min = j; }} //Permutation des elements//Permutation des elements Tmp = Tableau[i];Tmp = Tableau[i]; Tableau[i]Tableau[i] == Tableau[min];Tableau[min]; Tableau[min]Tableau[min] == Tmp;Tmp;

}}}}

Tris simples

Tri par sélection



tri in situ?progressif?

Stable?

21,17,21,5,2,9,2,7

Tri sélection • remplir les cases de 1 à n avec le minimum des éléments du tableau restant

Tris simples

Tri par sélection• remplir les cases de 1 à n avec le minimum des éléments du tableau

restant

Meilleur cas : séquence triée•nb de comparaisons ? O(n2)•nb de déplacements ? O(1)

Pire cas : séquence triée inverse•nb de comparaisons ? O(n2)•nb de déplacements ? O(n)

tri in situ ?progressif ?stable ?

Stable?

21,17,21,5,2,9,2,7

Tris simples

Tri par sélection

21,17,21,5,2,9,2,7

stable ?

Tris simples

14

235

54

123

45

123

45

123

45

123

Les balayages

peuvent être éliminés

Algorithme#3

remonter les plus petites valeurs à la surface, et ce, à chaque itération

Tris simples

Tri à bulles (« Bubblesort »)

44,55,12,42,94,18,06,67

Algorithme :• remonter les plus petites bulles à la surface, et ce, à chaque itération

Tris simples

tri à bulles (« Bubblesort ») :

44,55,12,42,94,18,06,67

Tris simples


44,55,12,42,94,18,06,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

06,12,18,44,55,42,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

06,12,18,44,55,42,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

06,12,18,44,55,42,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

06,12,18,44,55,42,67,94

06,12,18,42,44,55,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

06,12,18,44,55,42,67,94

06,12,18,42,44,55,67,94

Tris simples


44,55,12,42,94,18,06,6706,44,55,12,42,94,18,67

06,44,55,12,18,42,94,67

06,12,44,55,18,42,94,67

06,12,44,55,18,42,67,94

06,12,18,44,55,42,67,94

06,12,18,42,44,55,67,94


templatetemplate<<typenametypename T> T>voidvoid TriBulle( TriBulle(vector<T>& Tableauvector<T>& Tableau, , int int n)n){ {

T Tmp;T Tmp;forfor ( (intint i=0; i<n-1; i++)i=0; i<n-1; i++)

forfor ( (intint j=n-1; j>i; j--) j=n-1; j>i; j--)ifif ( Tableau[j-1]> Tableau[j]) ( Tableau[j-1]> Tableau[j]){ {

Tmp = Tableau[j-1];Tmp = Tableau[j-1];Tableau[j-1] = Tableau[j];Tableau[j-1] = Tableau[j];Tableau[j] = Tmp;Tableau[j] = Tmp;

}}}}

Tris simples

Tri à bulles




Tri à bulles (« Bubblesort ») • remonter les plus petites bulles à la surface, et ce, à chaque itération

Tris simples

Tri à bulles (« Bubblesort ») • remonter les plus petites bulles à la surface, et ce, à chaque

itération

Meilleur cas : séquence triée•nb de comparaisons ? O(n2)•nb de déplacements ? O(1)

Pire cas : séquence triée inverse•nb de comparaisons ? O(n2)•nb de déplacements ? O(n2)


Tris simples


Première amélioration Une première amélioration consiste à arrêter le processus s'il n'y a aucun échange dans une passe.

Deuxième amélioration : ShakerSortUne deuxième amélioration consiste à alterner le sens des passes.

Troisième amélioration Une troisième qui consiste à reprendre au début chaque fois qu’il y a une

permutation.

Complexité • en temps : en O(n2) en moyenne et au pire des cas

• en nombre de transferts • ou en nombre de comparaisons en O(n²).

• en espace : en O(1) (tris sur place)

Sauf tri shell • ne conviennent pas pour un nombre important de données

Faciles à comprendre et à mettre en œuvre

Tris simples

Tri rapide (« Quicksort »)

Tri dichotomique appelé aussi tri des bijoutiers Idée :

trier les perles avec des tamis plus ou moins fins pour chaque tamis

on sépare les perles en deux sous-ensembles (celles qui passent et celles qui restent dans le tamis)

puis on trie celles qui sont passées avec un tamis plus fin et les autres avec un tamis plus gros

Tris complexes

Tris complexes


44,55,12,42,94,18,06,67

Algorithme • choisir un pivot p (élément médian)• partager le tableau en 2 :

• sous-tableau de gauche : éléments ≤ p• sous-tableau de droite : éléments > p• l’élément entre les 2 le pivot est à sa place définitive

• appel récursif avec le sous-tableau de gauche• appel récursif avec le sous-tableau de droite

Tris complexes


Partage avec pivot = 3

32 4 1 7 2 3 6

32 2 1 7 4 3 6

32 2 1 3 4 7 6

31 2 2 3 4 6 7

TRI TRI

< 3 3

Suite du tri

Tris complexes


44,55,12,42,94,18,06,67

Tris complexes


44,55,12,42,94,18,06,67

Tris complexes


44,55,12,42,94,18,06,67

Tris complexes


44,55,12,42,94,18,06,67

Tris complexes


06,55,12,42,94,18,44,67

Tris complexes


06,55,12,42,94,18,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,18,12,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,94,55,44,67

Tris complexes


06,12,18,42,44,55,94,67

Tris complexes


06,12,18,42,44,55,94,67

Tris complexes


06,12,18,42,44,55,94,67

Tris complexes


06,12,18,42,44,55,94,67

Tris complexes


06,12,18,42,44,55,94,67

Tris complexes


06,12,18,42,44,55,94,67

Tris complexes


06,12,18,42,44,55,67,94

Tris complexes


06,12,18,42,44,55,67,94

Tris complexes


06,12,18,42,44,55,67,94

Tris complexes


06,12,18,42,44,55,67,94

Tris complexes


06,12,18,42,44,55,67,94

Tris complexes

tri rapide (« Quicksort ») :

06,12,18,42,44,55,67,94

Meilleur cas :•nb de comparaisons ? •nb de déplacements ?

Pire cas :•nb de comparaisons ? •nb de déplacements ?

tri stable ?tri in situ ?progressive?

Tris complexes

Meilleur cas : pivot = médiane•nb de comparaisons ? •nb de déplacements ?



06,12,18,42,44,55,67,94

Tris complexes


06,12,18,42,44,55,67,94 n/2 n/2



Tris complexes

06,12,18,42,44,55,67,94



n/4 n/4n/4 n/4


06,12,18,42,44,55,67,94 n/2 n/2

Tris complexes

06,12,18,42,44,55,67,94

Meilleur cas : pivot = médiane•nb de comparaisons ? O(n log n)

•nb de déplacements ?


n/4 n/4n/4 n/4


06,12,18,42,44,55,67,94 n/2 n/2

Tris complexes

06,12,18,42,44,55,67,94

Meilleur cas : pivot = médiane•nb de comparaisons ? O(n log n)•nb de déplacements ? O(1)


n/4 n/4n/4 n/4


06,12,18,42,44,55,67,94 n/2 n/2

Tris complexes


06,12,18,42,44,55,67,94



Tris complexes


Pire cas : pivot = min. ou max.•nb de comparaisons ? •nb de déplacements ?


06,12,18,42,44,55,67,94

Tris complexes



n-1


06,12,18,42,44,55,67,94

Tris complexes

06,12,18,42,44,55,67,94



n-2

n-1


06,12,18,42,44,55,67,94

Tris complexes

n-3

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

n-2

n-1


06,12,18,42,44,55,67,94



Tris complexes

n-4

n-3

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

n-2

n-1


06,12,18,42,44,55,67,94



Tris complexes

n-4

n-3

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

n-2

n-1


06,12,18,42,44,55,67,94


Pire cas : pivot = min. ou max.•nb de comparaisons ? O(n2)•nb de déplacements ?

Tris complexes

n-4

n-3

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

06,12,18,42,44,55,67,94

n-2

n-1


06,12,18,42,44,55,67,94


Pire cas : pivot = min. ou max.•nb de comparaisons ? O(n2)•nb de déplacements ? O(n2)

Problèmes du « Quicksort »

Algorithme récursif :• taille de la pile = ?

• meilleur cas :• pire cas :• en moyenne :



• meilleur cas : O(log n)• pire cas :• en moyenne :



• meilleur cas : O(log n)• pire cas : O(n)• en moyenne :



• meilleur cas : O(log n)• pire cas : O(n)• en moyenne : O(log n)




• Comment faire pour minimiser la taille de la pile ?




• Comment faire pour minimiser la taille de la pile ?• empiler toujours le plus grand des 2 sous-tableaux

• O(1) ≤ taille de la pile ≤ O(log n) plutôt que :• O(1) ≤ taille de la pile ≤ O(n)


Algorithme récursif • taille de la pile = ?


• Comment faire pour minimiser la taille de la pile ?• empiler toujours de sous-tableaux de taille optimum• Tout dépend du choix du pivot

• du pire cas : O(n2) au meilleur cas : O(n log n)• Comment choisir un bon pivot ?

la solution idéale est de trouver à chaque fois la valeur médiane du sous-tableau à trier, mais sa recherche précise rend le tri plus lent que sans elle. Une solution quelquefois utilisée est de prendre par exemple trois valeurs, pour en prendre la valeur médiane, par exemple tab[droite], tab[gauche] et tab[(droite+gauche)/2] (dans le cas d'un tableau parfaitement mélangé, le choix de trois positions n'a pas d'importance, mais dans des tableaux presque triés le choix ci-dessus est plus judicieux). La totalité de ces améliorations peut apporter un gain de l'ordre de 20% par rapport à la version de base.


Choix du pivot :• du pire cas : O(n2) au meilleur cas : O(n log n)• Comment choisir un bon pivot ?


Attention aux bornes :

06,18,12,42,94,55,44,67


06,12,18,42,94,55,44,67



06,12,18,42,94,55,44,67




06,12,18,42,94,55,44,67

Choix du pivot :• du pire cas : O(n2) au meilleur cas : O(n log n)• Comment choisir un bon pivot ?

Attention aux constantes cachées : O(n log n)• n doit être grand !!!• tri doit être in situ !

Mais…

• Très bien compris, étudié tant au niveau théorique qu’expérimental.

• Très bonnes performances s'il est optimisé• dérécursivé• tri par insertion sur les petites listes

Tris complexes



En moyenne•nb de comparaisons ? O(n log n)•nb de déplacements ? O(n log n)

Pire cas : pivot = min. ou max.•nb de comparaisons ? O(n2) •nb de déplacements ? O(n2)


Ce qu’il faut retenir de ce tri:

Tris complexes


templatetemplate < <typenametypename T> T>voidvoid QuickSort(vector<T>& tableau, QuickSort(vector<T>& tableau, intint inf, inf, intint sup) sup){{

intint milieu; milieu;if if (sup>inf)(sup>inf) // s'il y a au moins 2 éléments// s'il y a au moins 2 éléments{{

milieu = Partition(tableau,milieu = Partition(tableau, inf,inf, sup);sup);

// trier la partie de gauche// trier la partie de gaucheQuickSort(tableau,QuickSort(tableau, inf,inf, milieu);milieu);// trier la partie de droite// trier la partie de droiteQuickSort(tableau,QuickSort(tableau, milieu+1, sup);milieu+1, sup);

}}}}

Tris complexes


templatetemplate < <typenametypename T>T>intint Partition(vector<T>& tableau, Partition(vector<T>& tableau, int int inf,inf, int int sup) sup){{

T pivot, tempo;T pivot, tempo;intint i,j; i,j;pivot = tableau[(sup+inf)/2];pivot = tableau[(sup+inf)/2];i = inf-1;i = inf-1;j = sup+1;j = sup+1;

// Suite a la page suivante// Suite a la page suivante

Tris complexes


while while ( i<j ) ( i<j ) // tant que les index ne croisent pas// tant que les index ne croisent pas { { // conserver les éléments plus petits ou égaux // conserver les éléments plus petits ou égaux //au pivot à sa gauche//au pivot à sa gauche dodo { i++;{ i++; } } whilewhile (tableau[i]<pivot); (tableau[i]<pivot); // conserver les éléments plus grands ou // conserver les éléments plus grands ou //égaux au pivot à sa droite//égaux au pivot à sa droite dodo { j--;{ j--; } } whilewhile (tableau[j]>pivot); (tableau[j]>pivot); // Permuter les éléments qui ne sont pas// Permuter les éléments qui ne sont pas // à leur place// à leur place ifif ( i<j) ( i<j) {{ tempo = tableau[i];tempo = tableau[i];

tableau[i]= tableau[j];tableau[i]= tableau[j];tableau[j]= tempo;tableau[j]= tempo;

}} }}

returnreturn j; } j; }

Tri par fusion

Diviser• Diviser la séquence de n éléments à trier en 2 sous-séquences de taille n/2

Régner• Trier les 2 sous-séquences

Combiner• Fusionner les 2 sous-séquences triées

Tris complexes

Tri par fusion "descente" division"remontée" fusion

5 2 4 6 1 3 2 61 2 2 3 4 5 6 6

5 2 4 62 4 5 6

1 3 2 61 2 3 6

5 22 5

4 64 6

1 31 3

2 62 6

5 2 4 6 1 3 2 6

divisionfusion fusion

division divisionfusion fusion

f f f f f f f fd d d d

fusion fusion

1 n 1 mTrié Trié

1 n+mTrié

t1

t3

t2

template template <<typename typename T>T>voidvoid triFusion( triFusion(TT * t, * t, int int debut, debut, intint fin) fin) {{

ifif(debut<fin) (debut<fin) {{

int int milieu=(debut+fin)/2;milieu=(debut+fin)/2;

triFusion(t, debut, milieu);triFusion(t, debut, milieu);triFusion(t, milieu+1, fin);triFusion(t, milieu+1, fin);fusionner(t, debut, milieu, fin);fusionner(t, debut, milieu, fin);

}}}}

void fusionner(T * t, int debut, int milieu, int fin) { int i1=debut; // indice courant dans t[debut..milieu] int i2=milieu+1; // indice courant dans t[milieu+1..fin] int i3=0; // indice courant dans t3 (tableau auxiliaire) T *t3; // tableau auxiliaire dynamique de longueur fin-debut+1

t3= new T[fin-debut+1];

while((i1<=milieu)&&(i2<=fin)) {

if(t[i1]<t[i2]) { t3[i3]=t[i1]; i1++;} else { t3[i3]=t[i2]; i2++; } i3++; }

if(i1>milieu) // on a epuisé t[debut..milieu] for(;i2<=fin;i2++,i3++) t3[i3]=t[i2]; else // on a epuisé t[milieu+1..fin] for(;i1<=milieu;i1++,i3++) t3[i3]=t[i1];

// il faut transférer t3 à sa place dans t for(i1=0;i1<i3;i1++) { t[i1+debut]=t3[i1]; }

delete [] t3;}

Tri par fusion

Comparaison avec le tri QuickSort

Tris complexes

Stabilité?in situ?Progressivité?

Complexité?

Tris complexes

Tri par arbre (« Treesort »)

44,55,12,42,94,18,06,67

Algorithme utiliser une structure d’arbre pour trier la séquence de clés

faire un nouvel arbre ? O(n log n) mais n nouveaux éléments + ptrs : trop d’espace !!!

Tris complexes

Tri par arbre (« Treesort »)

• utiliser une structure d’arbre pour trier la séquence de clés• utiliser les éléments de base comme feuilles

44

55

12

42

18

06

67

94

Tris complexes

44

55

12

42

18

06

67

94

44

12

06

18

44

55

12

42

18

06

67

94

44

12

06

18

12

06

Tris complexes

44

55

12

42

18

06

67

94

44

12

06

18

12

06

06

Tris complexes

44

55

12

42

18

06

67

94

44

12

06

18

12

06

06

Tris complexes

44

55

12

42

18

67

94

44

12

67

18

12

18

12

Tris complexes

44

55

12

42

18

67

94

44

12

67

18

12

18

12

Tris complexes

44

55

42

18

67

94

44

42

67

18

42

18

18

Tris complexes

44

55

42

18

67

94

44

42

67

18

42

18

18

Tris complexes

44

55

42

18

67

94

44

42

67

18

42

18

18

Tris complexes

Tri par arbre (« Heapsort »)

44,55,12,42,94,18,06,67

Algorithme • bâtir une structure d’arbre sur place

• hi h2i

• hi h2i+1

• structure appelée « monceau » (« heap »)

Tris complexes

Monceau - définition

Tris complexes

• Un arbre complet tel que pour chaque noeud N dont le parent est P, la clé de P est plus grande que celle de N

• Normalement implémenté dans un tableau• Insertion et retrait sont O(log N) dans le pire cas• Insertion est O(1) en moyenne• Recherche du plus petit élément est O(1) dans le pire cas

Tris complexes

Tri par arbre (« Heapsort »)

44

55

9442

67

12

18 06

55 12 42 94 18 06 67442 3 4 5 6 7 81

Tris complexes

Création du monceau

44

55

9442

67

12

18 06

55 12 42 94 18 06 67442 3 4 5 6 7 81

Tris complexes

44

55

9442

67

12

18 06

55 12 42 94 18 06 67442 3 4 5 6 7 81

Tris complexes

44

55

9467

42

12

18 06

55 12 67 94 18 06 42442 3 4 5 6 7 81

Tris complexes

44

55

9467

42

12

18 06

55 12 67 94 18 06 42442 3 4 5 6 7 81

Tris complexes

44

55

9467

42

12

18 06

55 12 67 94 18 06 42442 3 4 5 6 7 81

Tris complexes

44

55

9467

42

18

12 06

55 18 67 94 12 06 42442 3 4 5 6 7 81

Tris complexes

44

55

9467

42

18

12 06

55 18 67 94 12 06 42442 3 4 5 6 7 81

Tris complexes

44

94

5567

42

18

12 06

94 18 67 55 12 06 42442 3 4 5 6 7 81

Tris complexes

44

94

5567

42

18

12 06

94 18 67 55 12 06 42442 3 4 5 6 7 81

Tris complexes

94

44

5567

42

18

12 06

44 18 67 55 12 06 42942 3 4 5 6 7 81

Tris complexes

94

67

5544

42

18

12 06

67 18 44 55 12 06 42942 3 4 5 6 7 81

Tris complexes

94

67

5544

42

18

12 06

67 18 44 55 12 06 42942 3 4 5 6 7 81

Tris complexes

Monceaux dans la STL

• Fonction pour créer un monceau:make_heap(Iterator deb, Iterator fin)

• Fonctions pour insérer et retirer un élémentpush_heap(Iterator deb, Iterator fin)pop_heap(Iterator deb, Iterator fin)

• Toutes ces fonctions ont une seconde version avec un troisième argument qui est un prédicat qui permet de redéfinir l’opérateur de comparaison utilisé

• Note: l’itérateur doit être un itérateur à accès direct, ce qui limite les possibilités de conteneurs (vector et deque)

Tris complexes

Monceaux dans la STL

•Il existe aussi un adaptateur priority_queue•On peut choisir le type de conteneur et de fonction de comparaison•Offre les fonctions suivantes:

– push()– top()– pop()

•Voir les exemples fournis en annexe (MonceauSTL.cpp)

Tris complexes

Tri par monceau – Principe

•La procédure est la suivante:– On met dans le tableau les n valeurs à trier– On crée le monceau initial (de type Parent > Fils)– On retire la racine du monceau (qui est la plus grande valeur) et

on la permute avec le dernier item du monceau– On rétablit le monceau avec les (n-1) valeurs, s’il y a lieu– On répète le processus avec le monceau obtenu qui contient

maintenant un élément de moins

Tris complexes

Le tri

94

67

5544

42

18

12 06

67 18 44 55 12 06 42942 3 4 5 6 7 81

Tris complexes

42

67

5544

94

18

12 06

67 18 44 55 12 06 94422 3 4 5 6 7 81

Tris complexes

42

67

5544

94

18

12 06

67 18 44 55 12 06 94422 3 4 5 6 7 81

Tris complexes

42

67

5544

94

18

12 06

67 18 44 55 12 06 94422 3 4 5 6 7 81

Tris complexes

67

42

5544

94

18

12 06

42 18 44 55 12 06 94672 3 4 5 6 7 81

Tris complexes

67

55

4244

94

18

12 06

55 18 44 42 12 06 94672 3 4 5 6 7 81

Tris complexes

67

55

4244

94

18

12 06

55 18 44 42 12 06 94672 3 4 5 6 7 81

Tris complexes

06

55

4244

94

18

12 67

55 18 44 42 12 67 94062 3 4 5 6 7 81

Tris complexes

55

06

4244

94

18

12 67

06 18 44 42 12 67 94552 3 4 5 6 7 81

Tris complexes

55

44

4206

94

18

12 67

44 18 06 42 12 67 94552 3 4 5 6 7 81

Tris complexes

55

44

4206

94

18

12 67

44 18 06 42 12 67 94552 3 4 5 6 7 81

Tris complexes

12

44

4206

94

18

55 67

44 18 06 42 55 67 94122 3 4 5 6 7 81

Tris complexes

44

12

4206

94

18

55 67

12 18 06 42 55 67 94442 3 4 5 6 7 81

Tris complexes

44

42

1206

94

18

55 67

42 18 06 12 55 67 94442 3 4 5 6 7 81

Tris complexes

44

42

1206

94

18

55 67

42 18 06 12 55 67 94442 3 4 5 6 7 81

Tris complexes

12

42

4406

94

18

55 67

42 18 06 44 55 67 94122 3 4 5 6 7 81

Tris complexes

42

12

4406

94

18

55 67

12 18 06 44 55 67 94422 3 4 5 6 7 81

Tris complexes

42

12

4406

94

18

55 67

12 18 06 44 55 67 94422 3 4 5 6 7 81

Tris complexes

06

12

4442

94

18

55 67

12 18 42 44 55 67 94062 3 4 5 6 7 81

Tris complexes

18

12

4442

94

06

55 67

12 06 42 44 55 67 94182 3 4 5 6 7 81

Tris complexes

18

12

4442

94

06

55 67

12 06 42 44 55 67 94182 3 4 5 6 7 81

Tris complexes

06

12

4442

94

18

55 67

12 18 42 44 55 67 94062 3 4 5 6 7 81

Tris complexes

12

06

4442

94

18

55 67

06 18 42 44 55 67 94122 3 4 5 6 7 81

Tris complexes

12

06

4442

94

18

55 67

06 18 42 44 55 67 94122 3 4 5 6 7 81

Tris complexes

06

12

4442

94

18

55 67

12 18 42 44 55 67 94062 3 4 5 6 7 81

Tris complexes

06

12

4442

94

18

55 67

12 18 42 44 55 67 94062 3 4 5 6 7 81

Tris complexes

« Heapsort »

Algorithme • créer le monceau en descendant les clés• trier en échangeant le maximum et le dernier + redescendre

complexité ? stabilitéin situprogressivité

Tris complexes

« Heapsort »

Algorithme • créer le monceau en descendant les clés• trier en échangeant le maximum et le dernier + redescendre

complexité ?• O(n log n) en tout temps!• aucun espace additionnel requis !!!

stabilitéin situprogressivité

Quicksort, tri-fusion versus Heapsort

En moyenne, Quicksort a de meilleurs constantes cachées

que le tri-fusion et le Heapsort (par évaluations empiriques)

Stabilité?in situ?Progressivité?

Conclusion

Quelques comparaisons

• tri par tas (monceau): meilleure complexité• tri rapide et tri fusion: efficaces• tri par insertion excellent si liste initiale presque triée• et

• tri par sélection donne le début de liste trié avant la fin du tri• tri par insertion peut débuter sans liste initiale complète

Doit-on toujours trier complètement ?

Autres tris

Si le tableau contient un grand nombre de valeurs similaires:

algorithme par comptage ou tri par pigeonnier.

Conclusion

• Aucun tri qui compare des clefs peut s’exécuter en moins de temps que O(n lg n)• D’autres algorithmes peuvent se faire plus rapidement mais ils ne comparent des

clefs et ils fonctionnent dans des conditions particulières.• Le tri par pigeonnier est un de ces cas. Il fait l’hypothèses que les clefs à trier sont

des entiers entre 1 et R (rang)• On l'appelle également le tri par comptage (Counting sort en anglais)• c'est l'algorithme LE PLUS performant en terme d'utilisation CPU.

Tri par pigeonnier

1 6 3Tableau ETableau E

Tableau UTableau U

6

0 1 2 3 4 5 6

1 3 6 6

Tri par pigeonnier

1 6 3 6

0 1 0 1 0 0 2

1 3 6 6

Tri par pigeonnier

U[k] = U[k] - 1

T[i] k

i i+1

tant que U[k] 0

pour k à rang

i

pour i à n

U[k] U[k] + 1

pour k à rang

k T[i]

U[k] 0

TriPigeonnier(T[1..n])

Complexité spatiale?

Complexité temporel?

Tri par pigeonnier

U[k] = U[k] - 1

T[i] k

i i+1

tant que U[k] 0

pour k à rang

i

pour i à n

U[k] U[k] + 1

pour k à rang

k T[i]

U[k] 0

TriPigeonnier(T[1..n])

Complexité spatiale: O(n+rang)

Complexité temporelle: O(n+rang)) siaucun doublon

Tri par pigeonnier

Cependant de GROS inconvénients : 1) Si l'écart entre la valeur min et la valeur max de ton tableau initial est énorme, le tableau de distribution sera lui aussi énorme

=> complexité mémoire TROP importante. 2) Aucune comparaison n'est faite entre les valeurs => impossible de rendre ce tri GENERIQUE s'appliquant à tout type de données (par exemple trier un tableau de structure)car aucune fonction de comparaison n'est utilisée. Ce type de tri est donc réservé que dans cas bien précis connue de l'utilisateur: par exemple en imagerie, trié un tableau contenant les différents niveau de gris d'une image : les valeurs seront comprises entre 0 et 255

=> le tableau de distribution sera petit, le tri sera en un temps linéaire.

Tri pigeonnier

Le meilleur quand:• peu de valeurs possibles pour les clés et/ou• enregistrements petits ou réduits à la clé• pas de collisions

Dans les deux derniers cas, il existe des implémentations très simples.

Impraticable dans tous les autres cas • mémoire occupée en N + R.

Dans la cas où les clefs sont bornées (c'est à dire comprises entre un minimum et un maximum connus à l'avance) et en nombre fini: algorithme de tri basique (tri par bacs).

Tri basique

n=10 L = (26, 9, 0, 25, 1, 29, 64, 16, 81, 4)

après 1(0, 1, 81 ,64 ,4 ,25, 26, 16, 9, 29)

après 2(0, 1, 4, 9, 16, 25, 26, 29, 64, 81)

Classer L = (a1, …, an) clés Î (0, 1, 2, ..., n2 -1)

Tri en O(nxnbChiffresMax). Exemple: nbChiffreMax = 21. tri par bacs avec clé : clé(ai) mod n2. tri par bacs avec clé : clé(ai) / n

Équivalent à un tri lexicographique avec la clé (q, r) telle que clé(ai) = q.n + r

n=10 L = (26, 9, 0, 25, 1, 29, 64, 16, 81, 4)

après 1(0, 1, 81 ,64 ,4 ,25, 26, 16, 9, 29)

après 2(0, 1, 4, 9, 16, 25, 26, 29, 64, 81)

Tri basique

Tri basique

• Pour trier des clefs alphabétiques, on peut effectuer un tri en base 26

• Lorsque le tableau est presque trié, il est plus efficace d'effectuer un tri par insertion (passe de finition) plutôt que de répéter le tri basique jusqu'à tri complet.

Le bogo tri!

Le bogo tri est basé sur le paradoxe du singe savant . Il s'agit sans nul doute de l'algorithme de tri le plus inefficace jamais créé.

Son principe est très simple. Il consiste à permuter aléatoirement les éléments du tableau tant que celui-ci n'est pas trié. Si tous les éléments du tableau sont distincts, la complexité est de O(n * n!).

Comme les ordinateurs utilisent des générateurs de nombres pseudo-aléatoires, il se peut que le tri ne se finisse jamais pour un ensemble donné.

Variante

Le bozo tri est une variante de cet algorithme. Il consiste à choisir aléatoirement 2 éléments et à les échanger. On répète cette opération tant que tous les éléments ne sont pas trié. Tout comme son compatriote, étant donné qu'on utilise des générateurs de nombres pseudo-aléatoires, il se peut que le tri ne se termine jamais.

Le bozo tri

triAleatoire (E[0..N[)essais = 0tant que essais < A

i = indice aléatoire dans [0..N-1[j = indice aléatoire dans ]i..N[si E [i].cle > E [j].cle

permuter(E[i],E[j]), essais = 0sinon incrémenter essais

• ne trie pas complètement le tableau.• Dans quelle circonstance voudrait-on utiliser le tri aléatoire?• Est-ce que le tri aléatoire diminue le degré de désordre?

Le paradoxe du singe savant est un théorème selon lequel un singe qui tape au hasard sur le clavier d’une machine à écrire pourra presque sûrement écrire tous les livres de la Bibliothèque nationale de France. Dans l’adaptation du théorème en langue anglaise, le singe pourra presque sûrement dactylographier tous les travaux réunis de William Shakespeare.

Le résultat fut présenté par Émile Borel en 1909 dans son livre de probabilités. Ces « singes » ne sont pas des singes réels, et ne se comportent pas comme de vrais singes ; ils sont plutôt une métaphore vivante pour une machine abstraite à produire des lettres dans un ordre aléatoire, par exemple un ordinateur ou un générateur aléatoire connecté à une imprimante.

Le paradoxe du singe savant

•sort():–Doit garantir un temps moyen dans O(n lg n)–Le tri rapide (quicksort) répond à ce critère

•stable_sort():–Doit garantir O(n lg n) dans le pire cas–Peut utiliser de la mémoire supplémentaire–Le tri par fusion (mergesort) répond à ce critère

•partial_sort()–Doit garantir un temps moyen dans O(n lg n)–Doit permettre le tri partiel–Le tri par monceau (heapsort) répond à ce critère

Les tris dans la STL

• Tous les tris présentés supposent que toutes les données à trier sont présentes en mémoire centrale.

• éléments volumineux : pour ne pas avoir à déplacer les éléments• trier une liste où le stockage est indirect (tri indirect) on trie

une listes de pointeurs sur les éléments• trier une liste de couples (clé, référence) si les clés ne sont pas

trop grosses

• Si le nombre d’objets à trier est trop grand: tri externe

• le fichier est chargé en mémoire par morceaux • pb : minimiser les entrées sorties• pb algorithmique mais surtout matériel

Tri externe

Documents

Structures de données IFT-2000 Abder Alikacem Semaine 14 Les algorithmes de tri Département dinformatique et de génie logiciel Édition septembre 2009