Structure générique pour les algorithmes de tris


Commenter

Contenu du snippet

Tous les algorithmes de tris, du simple tri à bulles au tri fusion plus optimisé, peuvent trier n'importe quels types de valeurs dans n'importe quelles structures de données.

L'interface ci-dessous permet d'uniformiser la structure d'un algorithme de tri en Java, afin d'être suffisament générique pour pouvoir trier tous types de données.
NB. Seule la première méthode est à implémenter, les autres étant déduites de la première. 

import java.lang.reflect.Array;
import java.util.Comparator;
import java.util.List;

/** @author KX */
@FunctionalInterface
public interface Sorter {
    /**
     * Tri d'un objet quelconque.
     * @param container l'objet qui contient les valeurs à trier et qui sera trié à la fin de la méthode
     * @param sizer la méthode de calcul du nombre de valeurs à trier
     * @param getter la méthode d'accès à une des valeurs à trier
     * @param setter la méthode d'affectation d'une des valeurs triées
     * @param comparator la méthode de comparaison de deux valeurs à trier
     * @param <C> le type de l'objet qui contient les valeurs à trier
     * @param <V> le type des valeurs à trier
     */
    <C, V> void sort(C container, Sizer<C> sizer, Getter<C, V> getter, Setter<C, V> setter, Comparator<V> comparator);

    /** Tri d'une liste d'objets de type quelconque selon un Comparator */
    default <V> void sort(List<V> container, Comparator<V> comparator) {
        sort(container, List::size, List::get, List::set, comparator);
    }

    /** Tri d'une liste d'objets Comparable */
    default <V extends Comparable<V>> void sort(List<V> container) {
        sort(container, V::compareTo);
    }

    /** Tri d'un tableau d'objets de type quelconque selon un Comparator */
    default <V> void sort(V[] container, Comparator<V> comparator) {
        sort(container, c -> c.length, (c, i) -> c[i], (c, i, v) -> c[i] = v, comparator);
    }

    /** Tri d'un tableau d'objets Comparable */
    default <V extends Comparable<V>> void sort(V[] container) {
        sort(container, V::compareTo);
    }

    /** Tri d'un tableau de boolean */
    default void sort(boolean[] container) {
        sort(container, Array::getLength, Array::getBoolean, Array::setBoolean, Boolean::compare);
    }

    /** Tri d'un tableau de byte */
    default void sort(byte[] container) {
        sort(container, Array::getLength, Array::getByte, Array::setByte, Byte::compare);
    }

    /** Tri d'un tableau de char */
    default void sort(char[] container) {
        sort(container, Array::getLength, Array::getChar, Array::setChar, Character::compare);
    }

    /** Tri d'un tableau de int */
    default void sort(int[] container) {
        sort(container, Array::getLength, Array::getInt, Array::setInt, Integer::compare);
    }

    /** Tri d'un tableau de long */
    default void sort(long[] container) {
        sort(container, Array::getLength, Array::getLong, Array::setLong, Long::compare);
    }

    /** Tri d'un tableau de float */
    default void sort(float[] container) {
        sort(container, Array::getLength, Array::getFloat, Array::setFloat, Float::compare);
    }

    /** Tri d'un tableau de double */
    default void sort(double[] container) {
        sort(container, Array::getLength, Array::getDouble, Array::setDouble, Double::compare);
    }

    @FunctionalInterface
    static interface Getter<C, V> {
        V get(C container, int index);
    }

    @FunctionalInterface
    static interface Setter<C, V> {
        void set(C container, int index, V value);
    }

    @FunctionalInterface
    static interface Sizer<C> {
        int size(C container);
    }
}

Exemple d'implémentation avec un tri à bulles : 
import java.util.Arrays;
import java.util.Comparator;

/** @author KX */
public class BubbleSorter implements Sorter {

    @Override
    public <C, V> void sort(C container, Sizer<C> sizer, Getter<C, V> getter, Setter<C, V> setter, Comparator<V> comparator) {
        int size = sizer.size(container);
        for (int i = size - 1; i > 0; i--) {
            V vi = getter.get(container, i);
            for (int j = 0; j < i; j++) {
                V vj = getter.get(container, j);
                if (comparator.compare(vi, vj) < 0) {
                    setter.set(container, i, vj);
                    setter.set(container, j, vi);
                    vi = vj;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] tab = { 7, 4, 1, 8, 5, 2, 9, 6, 3 };
        new BubbleSorter().sort(tab);
        System.out.println(Arrays.toString(tab));
    }
}

Exemple d'implémentation avec un tri fusion : 
import java.util.Arrays;
import java.util.Comparator;

/** @author KX */
public class MergeSorter implements Sorter {

    @Override
    public <C, V> void sort(C container, Sorter.Sizer<C> sizer, Getter<C, V> getter, Setter<C, V> setter, Comparator<V> comparator) {
        int size = sizer.size(container);
        sort(container, 0, size, getter, setter, comparator, new Object[size]);
    }

    private <C, V> void sort(C container, int start, int end, Getter<C, V> getter, Setter<C, V> setter, Comparator<V> comparator, Object[] temp) {
        int middle = (start + end) / 2;
        if (middle == start)
            return;
        sort(container, start, middle, getter, setter, comparator, temp);
        sort(container, middle, end, getter, setter, comparator, temp);
        V vi = getter.get(container, start);
        V vj = getter.get(container, middle);
        for (int i = start, j = middle, k = 0;;) {
            if (comparator.compare(vi, vj) < 0) {
                temp[k++] = vi;
                if (++i == middle) {
                    while (j < end) {
                        temp[k++] = getter.get(container, j++);
                    }
                    break;
                } else {
                    vi = getter.get(container, i);
                }
            } else {
                temp[k++] = vj;
                if (++j == end) {
                    while (i < middle) {
                        temp[k++] = getter.get(container, i++);
                    }
                    break;
                } else {
                    vj = getter.get(container, j);
                }
            }
        }
        for (int i = start, k = 0; i < end; i++, k++) {
            setter.set(container, i, (V) temp[k]);
        }
    }

    public static void main(String[] args) {
        int[] tab = { 7, 4, 1, 8, 5, 2, 9, 6, 3 };
        new MergeSorter().sort(tab);
        System.out.println(Arrays.toString(tab));
    }
}

Compatibilité : 1

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (KX)