Maison > Article > développement back-end > Algorithme de tri par sélection
L'algorithme de tri par sélection divise le tableau en deux parties : la partie triée et la partie non triée. Initialement, la partie triée est vide, et la partie non triée contient tous les éléments. L'algorithme fonctionne en trouvant l'élément le plus petit (ou le plus grand, selon l'ordre de tri) de la partie non triée et en l'échangeant avec le premier élément de la partie non triée. Ce processus se poursuit jusqu'à ce que l'ensemble du tableau soit trié.
#Suppose we have the following array: arr = [64, 25, 12, 22, 11]
Tableau après le premier passage : [11, 25, 12, 22, 64]
Tableau après le deuxième passage : [11, 12, 25, 22, 64]
Tableau après le troisième passage : [11, 12, 22, 25, 64]
Tableau trié final : [11, 12, 22, 25, 64]
def selection_sort(arr): # Traverse through all array elements for i in range(len(arr)): # Find the minimum element in the remaining unsorted part min_index = i for j in range(i+1, len(arr)): if arr[j] < arr[min_index]: min_index = j # Swap the found minimum element with the first element of the unsorted part arr[i], arr[min_index] = arr[min_index], arr[i] # Example usage arr = [64, 25, 12, 22, 11] selection_sort(arr) print("Sorted array:", arr)
Tableau trié : [11, 12, 22, 25, 64]
Meilleur cas : O(n²)
Cas moyen : O(n²)
Pire des cas : O(n²)
Même si le tri par sélection fonctionne bien pour les petits ensembles de données, il n'est pas idéal pour les tableaux plus grands car sa complexité temporelle est O(n²). Cependant, il est facile à mettre en œuvre et peut être utile dans les cas où la mémoire est un problème, car le tri par sélection est en place (ne nécessite aucune mémoire supplémentaire).
Avantages :
Simple à comprendre et à mettre en œuvre.
Fonctionne bien sur les petites listes.
Ne nécessite pas de mémoire supplémentaire puisqu'il trie le tableau sur place.
Inconvénients :
Inefficace pour les grands ensembles de données en raison de sa complexité temporelle O(n²).
Ce n'est pas un algorithme de tri stable, ce qui signifie que des éléments égaux peuvent ne pas conserver leur ordre les uns par rapport aux autres.
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!