Optimisation du tri par tas

Dans le tri par tas de la section précédente, nous avons alloué de l'espace supplémentaire pour construire le tas et le trier. Dans cette section, nous optimisons cela en utilisant un tri par tas en place.

Pour un tas max, échangez d'abord les données à la position de départ avec la valeur à la fin du tableau, de sorte que la fin du tableau devienne l'élément maximal. Effectuez ensuite une opération de descente (shift down) sur l'élément W pour régénérer le tas max. Ensuite, échangez la valeur maximale nouvellement générée avec l'avant-dernière position du tableau entier, de sorte que l'avant-dernière position contienne la deuxième plus grande donnée. Ce processus se poursuit par analogie.

L'ensemble du processus peut être illustré par le diagramme suivant :

Exemple de code Java

Téléchargement du paquet de code source :Télécharger

Code du fichier src/example/heap/HeapSort.java :

package example.heap;

import example.sort.SortTestHelper;

/**
Tri par tas en place
 */

public class HeapSort<T extends Comparable> {


    public static void sort(Comparable[] arr) {

        int n = arr.length;

        // Notez que notre tas est indexé à partir de 0 à ce stade
        // Commencez à partir de (indice du dernier élément - 1) / 2
        // L'indice du dernier élément est n-1
        for (int i = (n - 1 - 1) / 2; i >= 0; i--)
            shiftDown(arr, n, i);
       
        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            shiftDown(arr, i, 0);
        }
    }

    // Échanger les deux éléments aux indices i et j dans le tas
    private static void swap(Object[] arr, int i, int j) {
        Object t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }

    // Processus shiftDown d'origine
    private static void shiftDown(Comparable[] arr, int n, int k) {

        while (2 * k + 1 < n) {
            // Nœud enfant gauche
            int j = 2 * k + 1;
            // Le nœud enfant droit est plus grand que le nœud enfant gauche
            if (j + 1 < n && arr[j + 1].compareTo(arr[j]) > 0)
                j += 1;
            // Plus grand que les deux nœuds enfants
            if (arr[k].compareTo(arr[j]) >= 0) break;
            // Échanger les valeurs du nœud d'origine et du nœud enfant
            swap(arr, k, j);
            k = j;
        }
    }

    // Test de HeapSort
    public static void main(String[] args) {

        int N = 100;
        Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
        sort(arr);
        // Extraire progressivement les données dans heapify à l'aide de extractMax
        // L'ordre d'extraction doit être du plus grand au plus petit
        for (int i = 0; i < N; i++) {
            System.out.print(arr[i] + " ");
        }
        // S'assurer que le tableau arr est trié du plus grand au plus petit
        for (int i = 1; i < N; i++)
            assert arr[i - 1] >= arr[i];
    }
}
autres extensions