Tri : selection et insertion sort
Mettre un tableau en ordre
- Le tri signifie mettre les valeurs d'un tableau en ordre, généralement du plus petit au plus grand.
- Sur l'examen AP CSA, vous devez pouvoir écrire et tracer deux tris : selection sort et insertion sort.
- Vous devez aussi tracer (mais pas écrire) un troisième tri : merge sort. Nous regardons les trois ici.
Selection sort : l'idée
- Parcourir le tableau de gauche à droite.
- À chaque position
i, trouver la valeur la plus petite dans la partie non triée (deijusqu'à la fin). - Échanger cette valeur la plus petite à la position
i. Maintenant0..iest trié. - Répéter jusqu'à ce que tout le tableau soit en ordre.
public class Sorter {
public static void selectionSort(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
int min = i; // index of smallest so far
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[min]) {
min = j; // found a smaller value
}
}
int temp = a[min]; // swap a[i] and a[min]
a[min] = a[i];
a[i] = temp;
}
}
}
Selection sort : un exemple
- Trierons
{5, 2, 4, 1, 3}. La partie située à gauche de|est déjà triée. - Chaque passage choisit la valeur la plus petite du reste et l'échange vers l'avant.
start: [5, 2, 4, 1, 3]
i=0 smallest=1 → swap a[0],a[3]: [1 | 2, 4, 5, 3]
i=1 smallest is already 2 → no move: [1, 2 | 4, 5, 3]
i=2 smallest=3 → swap a[2],a[4]: [1, 2, 3 | 5, 4]
i=3 smallest=4 → swap a[3],a[4]: [1, 2, 3, 4 | 5]
done: [1, 2, 3, 4, 5]
Insertion sort : l'idée
- Pensez à tenir des cartes à jouer et à en ajouter une à la fois à la bonne place.
- Commencez à l'index
1. Appelez cette valeur la clé. - Faites glisser les valeurs plus grandes vers la gauche d'une case vers la droite, jusqu'à ce que la clé trouve sa place.
- Déposez la clé dans le vide. Maintenant tout ce qui est à gauche est trié.
public class Sorter {
public static void insertionSort(int[] a) {
for (int i = 1; i < a.length; i++) {
int key = a[i]; // the value to place
int j = i - 1;
while (j >= 0 && a[j] > key) { // shift bigger values right
a[j + 1] = a[j];
j = j - 1;
}
a[j + 1] = key; // drop key into the gap
}
}
}
Insertion sort : un exemple
- Trier
{5, 2, 4, 1, 3}à nouveau. La partie située à gauche de|reste triée au fur et à mesure que nous avançons. - Le
keyest la valeur que nous insérons à chaque passage.
start: [5, 2, 4, 1, 3]
i=1 key=2 → shift 5 right, place 2: [2, 5 | 4, 1, 3]
i=2 key=4 → shift 5 right, place 4: [2, 4, 5 | 1, 3]
i=3 key=1 → shift 5,4,2 right, place 1: [1, 2, 4, 5 | 3]
i=4 key=3 → shift 5,4 right, place 3: [1, 2, 3, 4, 5]
done: [1, 2, 3, 4, 5]
Merge sort : seulement le tracé
- Merge sort utilise la récursion (leçon 15). Vous ne l'écrivez pas à l'examen, mais vous devez le tracer.
- Diviser le tableau en deux encore et encore, jusqu'à ce que chaque morceau ait une seule valeur.
- Fusionner les paires de morceaux ensemble, toujours en les gardant en ordre.
Merge sort : un exemple
- Une valeur est déjà « triée ». Fusionner deux morceaux triés donne un plus grand morceau trié.
split: [5, 2, 4, 1]
[5, 2] [4, 1]
[5] [2] [4] [1]
merge: [2, 5] [1, 4]
merge: [1, 2, 4, 5]
- Selection sort et insertion sort sont lents sur les grands tableaux (ils font environ n² étapes).
- Merge sort est plus rapide sur les grands tableaux (environ n·log n étapes). C'est pourquoi cela compte.
Erreurs courantes
- Selection sort et insertion sort sont tous deux O(n²).
- Tracez un petit tableau à la main pour vérifier votre tri.
À vous maintenant
- Chaque tâche vous donne un squelette de méthode avec un TODO. Triez le tableau in place (modifiez
alui-même). - Un Harness caché trie plusieurs tableaux et vérifie le résultat.
- Utilisez Vérifier la réponse pour compiler votre code avec les tests fournis et voir les résultats. Conservez les interfaces de classe et de méthode montrées dans l'en-tête.
Selection / insertion sort
Le tri compare et échange jusqu'à ce que la liste soit ordonnée.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez selectionSort(int[] a) pour qu'elle trie le tableau en place de petit à grand, en utilisant selection sort. Le vérificateur teste plusieurs tableaux.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez insertionSort(int[] a) pour qu'elle trie le tableau en place de petit à grand, en utilisant insertion sort. Le vérificateur teste plusieurs tableaux.
Cliquez sur Exécuter pour voir le résultat ici.
Difficulté 4/5 · 280 pièces + un petit bonus lors de la première réussite aujourd'hui
Complétez isSorted(int[] a) retournant true si le tableau est dans l'ordre de petit à grand (chaque élément est <= le suivant), sinon false. Un tableau vide ou à un seul élément compte comme trié.
Cliquez sur Exécuter pour voir le résultat ici.