Tris: Introduction
IFT 1025: Programmation 2
Jian-Yun Nie
Trier les données
• Créer un ordre dans les données– Ex. Ordre croissant, décroissant des valeurs
numériques– Ordre croissant des mots, …
• Pourquoi trier?– Faciliter la recherche (voir plus tard)– Faciliter la gestion en générale
Exemple
• Trier en ordre croisant:2, 56, 4, -7, 0, 78, -45, 10
• Une solution intuitive:– Prendre le plus petit– Prendre le plus petit suivant– …
-45, -7, 0, 2, 4, 10, 56, 78
• Selection sort (Tri par sélection)
Principe Selection Sort
• Pour un tableau:– Déterminer le plus petit élément p à partir de i– Échanger l’élément p avec i– Continuer à partir de i+1
2, 56, 4, -7, 0, 78, -45, 10-45, 56, 4, -7, 0, 78, 2, 10-45, 56, 4, -7, 0, 78, 2, 10-45, -7, 4, 56, 0, 78, 2, 10-45, -7, 4, 56, 0, 78, 2, 10-45, -7, 0, 4, 56, 78, 2, 10
…
Tri par insertion
• Pour un tableau – Prendre l’élément i– Insérer i dans l’ordre entre 0 et i– Continuer à partir de i+1
2, 56, 4, -7, 0, 78, -45, 102, 56, 4, -7, 0, 78, -45, 102, 56, 4, -7, 0, 78, -45, 102, 4, 56, -7, 0, 78, -45, 10-7, 2, 4, 56, 0, 78, -45, 10-7, 0, 2, 4, 56, 78, -45, 10
Tri par insertion (bis)
• Pour un tableau – Prendre l’élément i– Insérer i dans l’ordre entre i et la fin– Continuer avec i-1
2, 56, 4, -7, 0, 78, -45, 102, 56, 4, -7, 0, 78, -45, 102, 56, 4, -7, 0, 78, -45, 102, 56, 4, -7, 0, -45, 10, 782, 56, 4, 56, -45, 0, 10, 782, 56, 4, -45, 0, 10, 56, 78…
Principe général de tri
• Diviser pour régner
• Tri par sélection:– Diviser en deux parties (étape difficile)
• Le plus petit élément• Le reste
– Pour chaque partie divisée:• Trier séparément (récursion)
– Fusionner les résultats• Plus petit + reste trié
Principe général de tri (bis)
• Diviser pour régner
• Tri par insertion:– Diviser en deux parties:
• Le premier élément• Le reste
– Pour chaque partie divisée:• Trier séparément (récursion)
– Fusionner les résultats (étape difficile)• Insérer le premier élément dans le reste trié
Illustration
Sélection Insertion
6 3 2 9 4 5 6 3 2 9 4 5
2 3 4 5 6 9 2 3 4 5 6 9
6 3 9 4 5
3 4 5 6 9
2
2
3 2 9 4 5
2 3 4 5 9
6
6
Algorithme: par sélectionTri par sélection itératif: public void selectionSort(int[] array)• int minIndex, temp;// Itération• for (i=0; i<array.length-1; i++):
// Trouver le plus petit élément à partir de i– minIndex=i;– for (j=i+1; j<array.length; j++):
• if array[j]<array[minIndex] minIndex=j;
// échanger i et min (swap(array,i,minIndex))– if (minIndex != i) {temp=array[i];
array[i]=array[minIndex]; array[minIndex]=temp;}
Algorithme: par sélectionpublic void selectionSort(int[] array){
// Itérationfor (i=0; i<tab.length-1; i++){// Trouver le plus petit élément à partir de iint minIndex = min(array,i);// échanger i et minswap(array, i, minIndex)}
}
Tri par sélection (récursif)public void selectionSort(int[] array, int startIndex){ if ( startIndex >= array.length - 1 ) return;// Trouver min int minIndex = startIndex; for ( int index = startIndex + 1; index < array.length; index++ ) { if (array[index] < array[minIndex] ) minIndex = index; }// swap(array,startIndex, minIndex) swap(array, startIndex, minIndex)
// Récursion selectionSort(array, startIndex + 1);}
Trouver minIndex (récursif)// trouver l’indexe de l’élément minimalpublic int min(int[] array, int startIndex){
int minReste;if ( startIndex >= array.length - 1 )
return startIndex;// trouver min pour le reste
minReste = min(array, startIndex+1);
// choisir entre startIndex et minResteif (array[startIndex]<array[minReste])
return startIndex;else return minReste;
}
Tri par sélection (récursif)void selectionSort(int[] array, int startIndex){ if ( startIndex >= array.length - 1 ) return;// Trouver min int minIndex = min(array,startIndex);
// Swap swap(array, startIndex, minIndex);
// Récursion selectionSort(array, startIndex + 1);}
swap(array,startIndex, min(array,startIndex))
Illustration
selectionSort(array,0)
6 3 2 9 4 5
2 3 4 5 6 9
6 3 9 4 5
3 4 5 6 9
2
2
selectionSort(array,1)
swap(0,min(array,0))
Tri par insertion (itératif)void insertionSort(int[] array, int startIndex){
for (int i = 1; i < array.length; i++){
int next = array[i]; // de i-1 vers le début, décaler les éléments > a[i] int j = i; while (j > 0 && array[j - 1] > next) { array[j] = array[j - 1]; j--; } // Inserer l’élément array[j] = next;}
}
Illustration2, 56, 4, -7, 0, 78, -45, 10
2, 56, 4, -7, 0, 78, -45, 10
2, 4, 56, -7, 0, 78, -45, 10
2, 4, 56, -7, 0, 78, -45, 10
2, 4, 56*, 56, 0, 78, -45, 10
2, 4*, 4, 56, 0, 78, -45, 10
2*, 2, 4, 56, 0, 78, -45, 10
-7, 2, 4, 56, 0, 78, -45, 10
-7, 0, 2, 4, 56, 78, -45, 10...
// de i-1 vers le début, décaler les éléments > a[i]
i==3
a[i]==-7
next == -7
a[j] = next;
Tri par insertion (récursif)
void insertionSort(int[] array, int startIndex){
if ( startIndex >= array.length - 1 ) return;// Trier le reste
insertionSort(array, startIndex + 1); // Insérer startIndex dans le reste insert(array, startIndex);}
Insérer
// insérer l’élément index dans le reste qui est déjà trié
public void insert(int [] array, int index)
{
if (index >= array.length-1) return;
if (array[index] <= array[index+1]) return;
swap(array, index, index+1);//array[index]>array[index+1]
insert(array, index+1);
}
Arrêt de récursion
Illustration insert6, 2, 3, 4, 5, 9 insert(array, 0)2, 6, 3, 4, 5, 9 insert(array, 1)2, 3, 6, 4, 5, 9 insert(array, 2)2, 3, 4, 6, 5, 9 insert(array, 3)2, 3, 4, 5, 6, 9 insert(array, 4)
public void insert(int [] array, int index){
if (index >= array.length-1) return;if (array[index] < array[index+1]) return;swap(array, index, index+1);insert(array, index+1);
}
Illustration: insertionSort
insertionSort(array,1)
insertionSort(array,1)
insert(array,1)
6 3 2 9 4 5
2 3 4 5 6 9
3 2 9 4 5
2 3 4 5 9
6
6
mergeSort et quickSort
mergeSort quickSort
5 3 2 9 4 6 5 3 2 9 4 6
2 3 4 5 6 9 2 3 4 5 6 9
9 4 6 55 3 2
4 6 92 3 5
3 2 4 9 6
53 2 4 9 6
mergeSort
• Tri par fusion
• Principe– Séparer l’ensemble de données en 2 parties
de tailles comparables– Trier les 2 parties séparément– Fusionner les deux parties triées
quickSort
• Principe– Déterminer un pivot au hasard (e.g. premier
élément)– Séparer les données en 2 parties:
• <= pivot• >= pivot
– Trier les deux parties séparément– Mettre ensemble: <=pivot + (pivot) + >=pivot
mergeSortpublic int[] mergeSort(int [] array){
int [] array1, array2; // condition d’arrêt
if (array.length <= 1) return;
// séparer en 2 parties int[] first = new int[array.length / 2]; int[] second = new int[array.length - first.length]; System.arraycopy(array, 0, first, 0, first.length); System.arraycopy(array, first.length, second, 0, second.length);
// trier array1 = mergeSort(first); array2 = mergeSort(second);
// fusionner return merge(array1, array2);}
return merge(mergeSort(first), mergeSort(second))
Merge: fusionner deux ensembles triéspublic int [] merge(int[] array1, int[] array2){
int [] result = new int[array1.length+array2.length];int i=0, j=0, k=0;
// copier à chaque boucle celui qi est plus petitwhile (i<array1.length && j<array2.length){
if (array1[i] < array2[j]){
result[k]=array1[i];i++;
}else{
result[k]=array1[j];j++;
}k++;
}// copier ce qui reste dans array1 ou array2
if (i<array1.length) System.arraycopy(array1,i,result,k,array1.length-i);if (j<array2.length) System.arraycopy(array2,j,result,k,array2.length-j);return result;
}
quickSort
public void quickSort(int[] array, int from, int to){if (from >= to) return;
int p = partition(array, from, to);quickSort(array, from, p);quickSort(array, p + 1, to);}
partition
partition
public int partition(int[] array, int from, int to){
int pivot = array[from];int i = from - 1;int j = to + 1;while (i < j){
i++; while (array[i] < pivot) i++;j--; while (array[j] > pivot) j--;if (i < j) swap(array,i, j);
}return j;
}
Partition (bis)public int partition(int[] array, int from, int to){
int pivot = array[from];int p = from;for (int r = from+1; r<=to; r++){
if (array[r] < pivot) {
array[p] = array[r]; array[r] = array[p+1];array[p+1] = pivot;p++;
}return p;
}
p
>=pivot<pivot
r12
3
pivot
4
Qualité d’un algorithme
• Efficacité– Utilisation de l’espace (octets, …)– Utilisation du temps (seconde, …)
• Complexité asymptotique– Imaginons qu’il y a n données à traiter– Déterminer l’ordre de grandeur pour le
nombre d’opérations et d’unité d’espace– Notation: O(n)
Complexité
• Temps– Moyen– Pire cas
• Ignorer la constante multiplicateur, constante et ordre inférieur– O(3n)=O(n)– Dans un boucle, une opération v.s. 3 opérations– O(3n+logn)=O(n)
• Important:– Nombre de fois qu’on fait des boucles
IllustrationSélection
n éléments
Pour choisir l’élément:
n-1 comparaisons
récursion
mettre ensemble:
1 opération
6 3 2 9 4 5
2 3 4 5 6 9
6 3 9 4 5
3 4 5 6 9
2
2
Selection sort (Décomposition)
(n-1) + 1 n éléments(n-2) + 1 n-1 éléments(n-3) + 1 n-2 éléments…1 + 1 2 éléments
• n(n-1)/2• O(n2)• temps moyen = pire cas• Espace: O(1)
Merge sort
• Séparer en 2 parties
– 1-2 opérations
• Trier les deux
• Merge:
– n comparaisons
5 3 2 9 4 6
2 3 4 5 6 9
9 4 65 3 2
4 6 92 3 5
Merge sort (décomposition)
1 (séparer) + n (merge) = n+12 (séparer) + 2*n/2 (merges) = n+24 (séparer) + 4*n/4 (merges) = n+4 logn…2logn (séparer) + 2logn*n/2logn (merges) = n+n
• Global: O(n logn)• Cas moyen = pire cas• Espace: O(n)
• Reflexions:– Temps pour insertionSort et quickSort?– Espace?
Temps typiques pour le tri
n
Timen2
n log n
n 10 100 1000
n2 100 10,000 1,000,000n log n 10 200 3000
Comparaison
n Merge sort (ms)
Selection sort (ms)
10,000 31 772
20,000 47 3,051
30,000 62 6,846
40,000 80 12,188
50,000 97 19,015
60,000 113 27,359
Comparaison
java.util.Arrays
• Provides static methods for dealing with arrays.
• Works for arrays of numbers, Strings, (and “comparable” Objects).
• Methods:
int pos = Arrays.binarySearch (arr, target);
Arrays.sort (arr);Arrays.sort (arr, from, to); //quicksort
Arrays.fill (arr, value); // fills arr with a given valueArrays.fill (arr, from, to, value);
Trier d’autres types de données
• Interface Comparable:– Méthode exigée: int compareTo(Object o)– Ordre:
<0, <=0, ==0, >=0, >0
• Les classes qui implentent Comparable:BigDecimal, BigInteger, Byte, ByteBuffer, Character, CharBuffer, Charset, CollationKey, Date, Double, DoubleBuffer, File, Float, FloatBuffer, IntBuffer, Integer, Long, LongBuffer, ObjectStreamField, Short, ShortBuffer, String, URI
• E.g. String s: if (s.compareTo("Montreal")<0) …
Pour trier d’autres données
class Donnee implements Comparable{
…public int comparaTo(Object d){ Donnee d1 = (Donnee) d;
…}
}
Trier d’autres données
• Donnee [ ] array;
• Arrays.sort(array)
• Reflexion: – Comment modifier les méthodes de tri pour
fonctionner sur tout tableau (Array) du type Comparable?
– public void insertionSort(Comparable [ ] array)