Comme nous avons parlé de différents algorithmes de tri, nous allons aujourd'hui découvrir l'algorithme de tri par sélection. Un algorithme de tri qui permet le nombre minimum d'échanges possible dans un environnement à mémoire limitée.
Le tri par sélection est un algorithme de tri simple mais efficace qui fonctionne en sélectionnant à plusieurs reprises l'élément le plus petit (ou le plus grand) de la partie non triée de la liste et en le déplaçant au début (ou à la fin) de la partie triée. Ce processus est répété jusqu'à ce que la liste entière soit triée. Dans cet article, nous approfondirons les détails de l'algorithme de tri par sélection, son implémentation en JavaScript et ses applications pour résoudre des problèmes du monde réel.
L'algorithme de tri par sélection est un algorithme de tri par comparaison sur place. Il divise la liste d'entrée en deux parties :
L'algorithme sélectionne à plusieurs reprises le plus petit élément de la partie non triée et l'échange avec l'élément non trié le plus à gauche, déplaçant la limite entre les parties triées et non triées d'un élément vers la droite.
Parcourons un exemple utilisant le tableau [64, 25, 12, 22, 11] :
Le tableau est maintenant entièrement trié.
Le tri par sélection a une complexité temporelle de O(n^2) dans tous les cas (meilleur, moyen et pire), où n est le nombre d'éléments dans le tableau. C'est parce que :
Cela donne environ (n^2)/2 comparaisons et n échanges, ce qui se simplifie en O(n^2).
En raison de cette complexité temporelle quadratique, le tri par sélection n'est pas efficace pour les grands ensembles de données. Cependant, sa simplicité et le fait qu'il effectue le minimum de swaps possible peuvent le rendre utile dans certaines situations, notamment lorsque la mémoire auxiliaire est limitée.
Selection Sort a une complexité spatiale de O(1) car il trie le tableau sur place. Il ne nécessite qu'une quantité constante d'espace mémoire supplémentaire, quelle que soit la taille d'entrée. Cela le rend efficace en termes de mémoire, ce qui peut être avantageux dans les environnements où la mémoire est limitée.
Voici une implémentation JavaScript de l'algorithme de tri par sélection :
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
// Find the minimum element in the unsorted portion
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first unsorted element
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));
Décomposons le code :
Résolvons un problème d'algorithme leetcode en utilisant l'algorithme de tri par sélection. On y va ?
Problème : Étant donné un tableau de nombres entiers, triez le tableau par ordre croissant et renvoyez-le. Vous devez résoudre le problème sans utiliser de fonctions intégrées dans une complexité temporelle O(nlog(n)) et avec la plus petite complexité spatiale possible.
Approche : : Pour résoudre ce problème, nous pouvons appliquer directement l'algorithme de tri par sélection. Cela implique de parcourir le tableau, de trouver le plus petit élément dans la partie non triée et de l'échanger avec le premier élément non trié. Nous répétons ce processus jusqu'à ce que l'ensemble du tableau soit trié.
Solution :
function selectionSort(arr) {
const n = arr.length;
for (let i = 0; i < n - 1; i++) {
let minIndex = i;
// Find the minimum element in the unsorted portion
for (let j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// Swap the found minimum element with the first unsorted element
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
// Example usage
const unsortedArray = [64, 25, 12, 22, 11];
console.log("Unsorted array:", unsortedArray);
console.log("Sorted array:", selectionSort(unsortedArray));
Cette solution applique directement l'algorithme de tri par sélection que nous avons implémenté précédemment. Bien qu'elle résout correctement le problème, il convient de noter que cette solution peut dépasser la limite de temps pour les entrées volumineuses sur LeetCode en raison de la complexité temporelle O(n^2) du tri par sélection. L'image ci-dessous montre que la solution est correcte mais pas efficace.
En conclusion, Selection Sort est un algorithme de tri simple et intuitif qui constitue une excellente introduction au monde des techniques de tri. Sa simplicité le rend facile à comprendre et à mettre en œuvre, ce qui en fait un outil d'apprentissage précieux pour les débutants. Cependant, en raison de sa complexité temporelle quadratique O(n^2), il n'est pas efficace pour les grands ensembles de données. Pour les ensembles de données plus volumineux ou les applications critiques en termes de performances, des algorithmes plus efficaces tels que QuickSort, MergeSort ou des fonctions de tri intégrées sont préférés.
Pour vous assurer de ne manquer aucune partie de cette série et pour me contacter pour plus de détails
discussions sur le Développement Logiciel (Web, Serveur, Mobile ou Scraping/Automatisation), les données
structures et algorithmes, et d'autres sujets technologiques passionnants, suivez-moi sur :
Restez à l'écoute et bon codage ???
Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!
Classement des prestataires de services CDN étrangers
Quelle est la différence entre les vues et les tables de base de données
Comment obtenir un jeton
Raisons du trafic excessif sur les serveurs de sites Web à l'étranger
Que sont les variables d'environnement
rayon de frontière
Logiciel de modélisation mathématique
tutoriel python
![[Web front-end] Démarrage rapide de Node.js](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
