Tri par sélection
Dernière mise à jour
Le tri par sélection divise le tableau en une région triée à gauche et une région non triée à droite. À chaque passe, il parcourt la région non triée pour trouver le plus petit élément, puis l'échange à la première position non triée, agrandissant la région triée d'une unité. Appuyez sur lecture ci-dessus pour observer le balayage et l'échange, ou avancez comparaison par comparaison.
Le tri par sélection effectue toujours le même nombre de comparaisons quel que soit l'entrée, mais réalise au plus n-1 échanges - bien moins que le tri à bulles - ce qui compte lorsque les écritures sont coûteuses.
Complexité temporelle et spatiale
| Cas | Complexité | Notes |
|---|---|---|
| Meilleur cas | O(n²) | Les comparaisons ont lieu même si le tableau est trié |
| Cas moyen | O(n²) | Ordre aléatoire |
| Pire cas | O(n²) | Ordre inverse |
| Espace | O(1) | En place |
| Stable | Non | Les échanges peuvent réordonner les éléments égaux |
Étape par étape
| Étape | Ce qui se passe |
|---|---|
| 1 | Considérer tout le tableau comme non trié. |
| 2 | Parcourir la région non triée pour trouver l'élément minimum. |
| 3 | Échanger ce minimum à la première position non triée. |
| 4 | Déplacer la frontière d'un cran vers la droite (cette position est désormais triée). |
| 5 | Répéter jusqu'à ce qu'il ne reste qu'un seul élément non trié. |
Exemple détaillé
Tri de [5, 2, 4, 1] :
| Passe | Tableau | Action |
|---|---|---|
| Début | [5, 2, 4, 1] | Tout le tableau est non trié. |
| 1 | [1, 2, 4, 5] | On parcourt [5, 2, 4, 1], le minimum est 1 à l'indice 3 ; on l'échange avec l'indice 0. |
| 2 | [1, 2, 4, 5] | On parcourt [2, 4, 5], le minimum est 2 déjà à l'indice 1 ; il s'échange avec lui-même. |
| 3 | [1, 2, 4, 5] | On parcourt [4, 5], le minimum est 4 déjà à l'indice 2 ; aucun déplacement nécessaire. |
| Fin | [1, 2, 4, 5] | Il ne reste que 5, il est donc déjà à sa place. |
Quand utiliser le tri par sélection
| À utiliser quand | À éviter quand |
|---|---|
Les écritures sont coûteuses - il effectue au plus n-1 échanges. | Le tableau est grand - les O(n²) comparaisons dominent. |
| Vous avez besoin d'un tri en place simple et facile à implémenter. | Vous avez besoin d'un tri stable qui préserve l'ordre des clés égales. |
La mémoire est limitée - il n'utilise que O(1) d'espace supplémentaire. | Les données sont presque triées - il ne peut pas terminer plus tôt comme le tri par insertion. |
| Le jeu de données est minuscule et une performance prévisible compte. | Le débit compte - les tris O(n log n) comme le tri rapide sont bien plus rapides. |
Code de Selection Sort
Une implémentation propre et exécutable de Selection Sort en Python, JavaScript, Java, C++, C. Choisissez un langage, copiez le code ou ouvrez-le préchargé dans le Playground Coddy.
Code de Selection Sort en Python
Python
1def selection_sort(a):2 n = len(a)3 for i in range(n - 1):4 # Find the smallest element in the unsorted tail5 min_idx = i6 for j in range(i + 1, n):7 if a[j] < a[min_idx]:8 min_idx = j9 a[i], a[min_idx] = a[min_idx], a[i]10 return a11
12
13nums = [64, 25, 12, 22, 11]14print("Before:", nums)15selection_sort(nums)16print("After: ", nums)Code de Selection Sort en JavaScript
JavaScript
1function selectionSort(a) {2 for (let i = 0; i < a.length - 1; i++) {3 let min = i;4 // Find the smallest element in the unsorted tail5 for (let j = i + 1; j < a.length; j++) {6 if (a[j] < a[min]) min = j;7 }8 if (min !== i) [a[i], a[min]] = [a[min], a[i]];9 }10 return a;11}12
13const data = [5, 2, 9, 1, 7, 3];14console.log("Before:", data);15console.log("Sorted:", selectionSort([...data]));Code de Selection Sort en Java
Java
1import java.util.Arrays;2
3public class Main {4 static void selectionSort(int[] arr) {5 for (int i = 0; i < arr.length - 1; i++) {6 int minIndex = i;7 // Find the smallest value in the unsorted part8 for (int j = i + 1; j < arr.length; j++) {9 if (arr[j] < arr[minIndex]) minIndex = j;10 }11 int tmp = arr[i];12 arr[i] = arr[minIndex];13 arr[minIndex] = tmp;14 }15 }16
17 public static void main(String[] args) {18 int[] arr = {29, 10, 14, 37, 13, 5};19 System.out.println("Before: " + Arrays.toString(arr));20 selectionSort(arr);21 System.out.println("After: " + Arrays.toString(arr));22 }23}Code de Selection Sort en C++
C++
1#include <iostream>2#include <utility>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void selectionSort(std::vector<int>& a) {11 for (size_t i = 0; i + 1 < a.size(); ++i) {12 // Find the smallest element in the unsorted suffix13 size_t minIdx = i;14 for (size_t j = i + 1; j < a.size(); ++j) {15 if (a[j] < a[minIdx]) minIdx = j;16 }17 std::swap(a[i], a[minIdx]);18 }19}20
21int main() {22 std::vector<int> data = {29, 10, 14, 37, 13, 5};23 std::cout << "Before: ";24 printVec(data);25 selectionSort(data);26 std::cout << "After: ";27 printVec(data);28 return 0;29}Code de Selection Sort en C
C
1#include <stdio.h>2
3void printArr(const int a[], int n) {4 for (int i = 0; i < n; i++) printf("%d ", a[i]);5 printf("\n");6}7
8void selectionSort(int a[], int n) {9 for (int i = 0; i < n - 1; i++) {10 // Find the smallest element in the unsorted suffix11 int minIdx = i;12 for (int j = i + 1; j < n; j++) {13 if (a[j] < a[minIdx]) minIdx = j;14 }15 int tmp = a[i];16 a[i] = a[minIdx];17 a[minIdx] = tmp;18 }19}20
21int main(void) {22 int data[] = {29, 10, 14, 37, 13, 5};23 int n = sizeof(data) / sizeof(data[0]);24 printf("Before: ");25 printArr(data, n);26 selectionSort(data, n);27 printf("After: ");28 printArr(data, n);29 return 0;30}FAQ sur le tri par sélection
Quelle est la complexité temporelle du tri par sélection ?
Le tri par sélection est en
O(n²) dans tous les cas - meilleur, moyen et pire - car il parcourt toujours toute la région non triée pour trouver chaque minimum. Il utilise O(1) d'espace supplémentaire.Le tri par sélection est-il stable ?
La version standard en place n'est pas stable, car échanger un minimum éloigné à sa position peut faire passer un élément égal devant un autre. Une variante stable existe, mais elle nécessite de décaler plutôt que d'échanger.
Quand le tri par sélection est-il utile ?
Il est utile lorsque le coût d'écriture en mémoire est élevé, car il réalise au plus
n-1 échanges - le minimum possible pour un tri par comparaison qui déplace des éléments.Quelle est la différence entre le tri par sélection et le tri à bulles ?
Les deux sont des tris par comparaison en
O(n²), mais le tri par sélection effectue au plus n-1 échanges tandis que le tri à bulles peut en faire jusqu'à O(n²). Le tri à bulles peut aussi détecter un tableau déjà trié et s'arrêter plus tôt, alors que le tri par sélection exécute toujours toutes les passes.Dois-je utiliser le tri par sélection ou le tri par insertion ?
Dans la plupart des cas, préférez le tri par insertion - il est stable, s'exécute en
O(n) sur des données presque triées et est plus rapide en moyenne. Choisissez le tri par sélection uniquement lorsque minimiser le nombre d'écritures est la priorité, car il garantit au plus n-1 échanges.Pourquoi le tri par sélection s'exécute-t-il toujours en O(n²), même sur un tableau trié ?
Le tri par sélection n'a aucun moyen de savoir qu'un élément est déjà le minimum sans parcourir le reste de la région non triée, il effectue donc toutes les comparaisons à chaque passe quel que soit l'ordre d'entrée. C'est pourquoi le meilleur cas égale le pire en
O(n²) - contrairement au tri par insertion ou à bulles, qui peuvent s'arrêter court.Ressources associées
Plus de visualisations
