Chapitre 3 : Algorithmes de tri

Le tri est le processus de réorganisation d'une séquence d'objets afin de les mettre dans un certain ordre logique. Par exemple, votre relevé de carte de crédit présente les transactions par ordre chronologique, et vous rangez vos livres sur votre étagère par ordre alphabétique selon l'auteur et le titre. Le tri est une opération fondamentale en informatique et joue un rôle essentiel dans de nombreuses applications. Il existe une variété d'algorithmes de tri classiques qui incarnent différentes approches à ce problème.

Dans ce chapitre, nous examinons plusieurs méthodes de tri classiques et une structure de données importante connue sous le nom de file de priorité. Nous commençons par une discussion sur plusieurs méthodes de tri élémentaires, notamment le tri par sélection, le tri par insertion et le tri de Shell. Ces méthodes sont appropriées dans de nombreuses applications, mais pour les gros problèmes, nous nous tournons vers le tri fusion et le tri rapide, deux algorithmes de tri récursifs qui peuvent être utilisés pour trier un très grand nombre d'éléments. Nous concluons par une discussion sur les files de priorité et leur utilisation dans le tri et d'autres applications.

Tris élémentaires

Les algorithmes de tri les plus simples effectuent les opérations suivantes :

Tri par sélection : Trouver l'élément le plus petit et l'échanger avec la première entrée, puis trouver le deuxième plus petit élément et l'échanger avec la deuxième entrée, etc.
Tri par insertion : Prendre chaque élément à tour de rôle et l'insérer dans la position appropriée parmi ceux déjà considérés (en les gardant triés).

Ces opérations reflètent la façon dont les humains effectuent généralement les tâches de tri et sont efficaces pour les petites tailles de problèmes. Cependant, elles ne passent pas à l'échelle et deviennent impraticables pour trier de grands tableaux.

Tri par sélection

Le tri par sélection est un algorithme de tri simple qui fonctionne comme suit : Tout d'abord, trouver l'élément le plus petit du tableau et l'échanger avec la première entrée (lui-même si la première entrée est déjà la plus petite). Ensuite, trouver le deuxième plus petit élément et l'échanger avec la deuxième entrée. Continuer ainsi jusqu'à ce que tout le tableau soit trié.

La boucle interne du triVoici la traduction française du fichier Markdown avec la traduction des commentaires pour le code, mais sans traduire le code lui-même :

Le tri par sélection est utilisé pour trouver l'élément minimum dans le sous-tableau non trié a[i..N-1]. L'indice de l'élément minimum est stocké dans min. Ensuite, a[i] est échangé avec a[min], ce qui place l'élément minimum dans sa position finale. Lorsque l'indice i se déplace de gauche à droite, les éléments à sa gauche sont dans l'ordre trié dans le tableau et ne seront plus touchés.

Voici une implémentation du tri par sélection en Java :

public static void selectionSort(Comparable[] a) {
    // Taille du tableau
    int N = a.length;
    // Parcourir le tableau
    for (int i = 0; i < N; i++) {
        // Initialiser l'indice du minimum
        int min = i;
        // Trouver l'indice du minimum dans le sous-tableau non trié
        for (int j = i+1; j < N; j++) {
            // Si l'élément courant est plus petit que le minimum actuel
            if (less(a[j], a[min])) min = j;
        }
        // Échanger l'élément courant avec le minimum
        exch(a, i, min);
    }
}

Le tri par sélection utilise environ ~N^2/2 comparaisons et N échanges pour trier un tableau de longueur N. Le temps d'exécution n'est pas sensible aux données d'entrée - il faut à peu près autant de temps pour exécuter le tri par sélection sur un tableau déjà trié ou sur un tableau avec toutes les clés égales que sur un tableau aléatoire.

Tri par insertion

Le tri par insertion est un autre algorithme de tri simple qui fonctionne en construisant le tableau final trié un élément à la fois. Il est beaucoup moins efficace sur les grands tableaux que des algorithmes plus avancés comme le tri rapide, le tri par tas ou le tri fusion, mais il a quelques avantages :

Il est efficace pour les petits ensembles de données.
Il est plus efficace en pratique que le tri par sélection.
Il est stable, c'est-à-dire qu'il ne modifie pas l'ordre relatif des éléments ayant des clés égales.
Il est en place, c'est-à-dire qu'il ne nécessite qu'une quantité constante O(1) d'espace mémoire supplémentaire.
Il est en ligne, c'est-à-dire qu'il peut trier une liste au fur et à mesure qu'il la reçoit.

Voici une implémentation du tri par insertion en Java :

public static void insertionSort(Comparable[] a) {
    // Taille du tableau
    int N = a.length;
    // Parcourir le tableau à partir du deuxième élément
    for (int i = 1; i < N; i++) {
        // Insérer l'élément courant à sa place dans la partie triée
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--) {
            // Échanger l'élément courant avec l'élément précédent
            exch(a, j, j-1);
        }
    }
}

La boucle interne du tri par insertion déplace les éléments plus grands d'une position vers la droite, faisant de la place pour insérer l'élément courant.Voici la traduction française du fichier Markdown, avec les commentaires traduits mais le code non traduit :

Le temps d'exécution du tri par insertion dépend de l'ordre initial des éléments dans l'entrée. Par exemple, si le tableau est grand et ses éléments sont déjà en ordre (ou presque en ordre), alors le tri par insertion est beaucoup, beaucoup plus rapide que si les éléments sont aléatoirement ordonnés ou dans l'ordre inverse.

Tri de Shell

Le tri de Shell est une extension simple du tri par insertion qui gagne en vitesse en permettant des échanges d'entrées de tableau qui sont éloignées, pour produire des tableaux partiellement triés qui peuvent être efficacement triés, éventuellement par tri par insertion.

L'idée est de réorganiser le tableau pour lui donner la propriété que prendre chaque hème entrée (en commençant n'importe où) donne une sous-séquence triée. Un tel tableau est dit être h-trié. En d'autres termes, un tableau h-trié est h sous-séquences triées indépendantes, entrelacées ensemble. En h-triant pour certaines grandes valeurs de h, nous pouvons déplacer des éléments dans le tableau sur de longues distances et ainsi faciliter le h-tri pour des valeurs de h plus petites. En utilisant une telle procédure pour toute séquence de valeurs de h qui se termine par 1, on obtiendra un tableau trié : c'est le tri de Shell.

Voici une implémentation du tri de Shell en Java :

public class MaxPQ<Key extends Comparable<Key>> {
    private Key[] pq;
    private int N;
    
    public MaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity+1];
    }
   
    public boolean isEmpty() {
        return N == 0;
    }
   
    public void insert(Key key) {
        pq[++N] = key;
        swim(N);
    }
   
    public Key delMax() {
        Key max = pq[1];
        exch(1, N--);
        sink(1);
        pq[N+1] = null;
        return max;
    }
   
    private void swim(int k) {
        while (k > 1 && less(k/2, k)) {
            exch(k, k/2);
            k = k/2;
        }
    }
   
    private void sink(int k) {
        while (2*k <= N) {
            int j = 2*k;
            if (j < N && less(j, j+1)) j++;
            if (!less(k, j)) break;
            exch(k, j);
            k = j;
        }
    }
   
    private boolea
```Voici la traduction française du fichier Markdown, avec les commentaires traduits en français. Le code n'a pas été traduit.
 
```java
private boolean less(int i, int j) {
    return pq[i].compareTo(pq[j]) < 0;
}
 
private void exch(int i, int j) {
    Key t = pq[i];
    pq[i] = pq[j];
    pq[j] = t;
}
}

Ce code implémente un tas binaire orienté vers le maximum en utilisant un tableau pq pour stocker l'arbre binaire complet ordonné par tas. Les opérations insert() et delMax() maintiennent l'invariant de tas en utilisant les méthodes auxiliaires swim() et sink() pour restaurer l'ordre du tas en échangeant les clés avec un parent plus grand qu'un enfant ou un enfant plus grand que son parent, respectivement.

Chronomètre

Un type de données abstrait plus utile est une abstraction simple et efficace pour un chronomètre, présentée sur la page en face. Pour l'utiliser, créez un objet Chronomètre lorsque vous voulez démarrer le chronomètre, puis utilisez la méthode elapsedTime() pour obtenir le temps écoulé en secondes depuis la création de l'objet. L'implémentation utilise System.currentTimeMillis() de Java pour obtenir l'heure actuelle en millisecondes depuis minuit le 1er janvier 1970.

La variable d'instance start enregistre l'heure à laquelle le chronomètre a été créé, et elapsedTime() utilise start pour calculer le temps écoulé. Le client présenté est typique : il effectue un certain calcul et utilise un Chronomètre pour mesurer le temps que prend le calcul. Le type de données Chronomètre est une abstraction efficace car il sépare le concept de chronomètre (l'interface) de l'implémentation (en utilisant System.currentTimeMillis() de Java). Cette séparation de l'interface et de l'implémentation est une caractéristique fondamentale des types de données abstraits que nous verrons dans chaque ADT tout au long du livre.

Résumé

Les types de données abstraits sont un élément essentiel de la programmation orientée objet, largement utilisés dans la programmation moderne. Dans cette section, nous avons vu :

Définir un type de données abstrait comme une classe Java, avec des variables d'instance pour définir les valeurs du type de données et des méthodes d'instance pour mettre en œuvre les opérations sur ces valeurs.
Développer plusieurs implémentations du même API, en utilisant différentes représentations du même type de données abstrait.Voici la traduction française du fichier Markdown :

Type de données abstrait.

Distinguer les API, les clients et les implémentations d'un type de données abstrait.
Concevoir des API pour les types de données abstraits.
Développer des clients et des clients de test pour l'utilisation dans les tests et le débogage.
Raisonner sur la correction d'une implémentation de type de données abstrait, en utilisant des assertions.
Comparer les performances de différentes implémentations du même API.

Ces activités font partie intégrante du développement de tout programme Java. Chaque programme Java que nous écrivons impliquera l'utilisation de types de données abstraits provenant de bibliothèques ; de nombreux programmes impliqueront le développement de nouveaux types de données abstraits. Dans la prochaine section, nous examinons trois types de données abstraits fondamentaux qui sont des composants essentiels dans un grand nombre de programmes, et dans la Section 1.4, nous examinons en détail le processus d'analyse des caractéristiques de performance des implémentations.

Chapter 2 Algorithms Fundamentals Chapter 4 Searching Algorithms