Algorithme de tri par sélection

Qu’est-ce que le 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é.

Étapes de l'algorithme

1. Commencez par le premier élément du tableau et supposez qu'il est le plus petit.
2. Comparez cet élément avec les autres éléments du tableau.
3. Si vous trouvez un élément plus petit, échangez-le avec le premier élément.
4. Passez à l'élément suivant du tableau et répétez le processus pour les éléments non triés restants.
5. Continuez ce processus jusqu'à ce que l'ensemble du tableau soit trié.

#Suppose we have the following array:

arr = [64, 25, 12, 22, 11]

Passe 1 :

• Le plus petit élément entre l'index 0 et le reste du tableau est 11.
• On échange 64 avec 11.

Tableau après le premier passage : [11, 25, 12, 22, 64]

Passe 2 :

• Maintenant, concentrez-vous sur le sous-tableau à partir de l'index 1. Le plus petit élément entre 25, 12, 22, 64 est 12.
• On échange 25 avec 12.

Tableau après le deuxième passage : [11, 12, 25, 22, 64]

Passe 3 :

• Le plus petit élément entre 25, 22, 64 est 22.
• On échange 25 avec 22.

Tableau après le troisième passage : [11, 12, 22, 25, 64]

Passe 4 :

• Le sous-tableau en contient désormais 25, 64. Comme ils sont déjà en ordre, aucun échange n'est nécessaire.

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]

Complexité temporelle du tri par sélection :

• 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 et inconvénients

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!