Comprendre l'algorithme de tri par sélection (avec des exemples en Java)

Tri par sélection : un guide étape par étape

Selection Sort est un algorithme de tri simple. Il recherche à plusieurs reprises l'élément minimum dans la partie non triée de la liste et le place au début. Ce processus se poursuit jusqu'à ce que toute la liste soit triée.

Fonctionnement du tri par sélection

Illustrons avec un exemple, en triant ce tableau par ordre croissant :

Itération 1 :

Le but est de placer le plus petit élément au début. Nous commençons par supposer que le premier élément est le minimum.

Nous comparons le minimum actuel avec chaque élément suivant, mettant à jour le minimum si un élément plus petit est trouvé.

Cela continue jusqu'à ce que le minimum réel soit identifié.

Enfin, on échange l'élément minimum avec le premier élément.

Le premier élément est maintenant trié. Les itérations suivantes ne prendront en compte que la partie non triée.

Itérations ultérieures :

Ce processus se répète pour chaque élément non trié restant.

L'algorithme itère n-1 fois (où n est la longueur du tableau). Après la cinquième itération (pour un tableau de six éléments), le dernier élément est implicitement trié.

Implémentation du tri par sélection (Java) :

import java.util.Arrays;

public class SelectionSortTest {
    public static void main(String[] args) {
        int[] arr = {8, 2, 6, 4, 9, 1};
        System.out.println("Unsorted array: " + Arrays.toString(arr));
        selectionSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }

    public static void selectionSort(int[] arr) {
        int size = arr.length;

        // Iterate through the array size-1 times
        for (int i = 0; i < size - 1; i++) {
            int minIndex = i;
            // Find the minimum element in the unsorted part
            for (int j = i + 1; j < size; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the minimum element with the first unsorted element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }
}

Sortie :

Tableau non trié : [8, 2, 6, 4, 9, 1] Tableau trié : [1, 2, 4, 6, 8, 9]

Analyse de complexité :

• Complexité temporelle : O(n²) dans tous les cas (meilleur, moyen, pire). Les boucles imbriquées s'exécutent toujours un nombre fixe de fois quel que soit l'ordre de saisie.
• Complexité spatiale :O(1). C'est un algorithme sur place, nécessitant un espace supplémentaire constant.

Conclusion :

La complexité temporelle O(n²) du tri par sélection le rend inefficace pour les grands ensembles de données. Il est mieux adapté aux petites baies ou aux situations où la simplicité prime sur les performances.

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!