Revue et test des méthodes de tri. Première partie

L'autre jour, dans les commentaires sur VKontakte, j'ai eu une dispute avec l'un des autres étudiants du projet. L'essence du différend était "qui gagnera" - une méthode sort()issue d'une classe java.util.Arraysou des implémentations auto-écrites d'algorithmes simples : bulle , insertion , sélection , shell (algorithme Shell). Pour certains, la réponse à cette question peut être évidente, mais depuis que le différend a éclaté, malgré le fait que chaque partie disposait de « sources respectées » en faveur de son point de vue, il a été décidé de mener une étude, étirant la matière grise dans le processus, mettant en œuvre divers algorithmes. TL;DR : java.util.Arrays.sort() elle est inconditionnellement leader sur les tableaux de 100 000 éléments ou plus ; avec une taille plus petite, la méthode Shell peut parfois la concurrencer. Le reste des algorithmes considérés sont complètement vides et ne peuvent être utiles que dans certaines conditions exotiques. Voyons maintenant comment les tableaux sont triés dans nos uber-appareils en silicium.

Tri par sélection. Tri par sélection

Commençons par la méthode la plus simple et la plus évidente. L'essentiel nous en est parfaitement démontré par Robert Sedgwick dans sa conférence vidéo sur Coursera (je citerai l'animation de là que j'ai mal compressée en gif) : Vue Parcourant le tableau à partir du premier élément, à chaque étape nous recherchez l'élément minimum sur le côté droit, avec lequel nous échangeons l'élément actuel. De ce fait, nous réservons la version finale de notre tableau sous forme triée. Voici le code implémentant cet algorithme en Java :

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

L'analyse de l'algorithme montre qu'il est nécessaire de parcourir le reste du tableau à chaque passage, c'est-à-dire que nous aurons besoin exactement de N + (N-1) + (N-2) + ... + 1 = N^ Comparaisons 2/2. Ainsi, la complexité de l'algorithme est O(N^2). Qu'est-ce que cela signifie? Cela signifie qu'en augmentant le nombre d'éléments dans le tableau (N) de 2 fois, nous augmenterons le temps d'exécution de l'algorithme non pas de 2, mais de 2^2 = 4 fois. En augmentant N de 10 fois, nous augmenterons la durée de fonctionnement de 100 fois, et ainsi de suite. Sur mon ordinateur portable 2012 équipé d'un processeur Core i3 exécutant Ubuntu 14.4, j'ai obtenu la disponibilité suivante :

Tri par insertion. Tri par insertion

Ici, l'idée est légèrement différente. Revenons à nouveau à l'animation du docteur Sedgwick : Voir Ce qui nous attend n'a même pas encore été vu par nous, et tout ce que nous laissons derrière nous reste toujours en ordre. Le fait est que nous « renvoyons » chaque nouvel élément du tableau d’origine au début jusqu’à ce qu’il « repose » sur un élément plus petit. Ainsi, nous avons à nouveau N passes (pour chaque élément du tableau d'origine), mais à chaque passe, dans la plupart des cas, nous ne regardons pas tout le reste, mais seulement une partie. Autrement dit, nous obtiendrons l'option 1 + (N-1) + (N-2) + … + N = N^2/2 uniquement si nous devons renvoyer chaque élément suivant au tout début, c'est-à-dire dans le cas du tableau d’entrée trié « à l’envers » (malchanceux, malchanceux). Dans le cas d'un tableau déjà trié (c'est de la chance), il y aura un cadeau complet - à chaque passage, il n'y a qu'une seule comparaison et en laissant l'élément en place, c'est-à-dire que l'algorithme fonctionnera dans un temps proportionnel à N. La complexité de l’algorithme sera déterminé par le pire cas théorique, c’est-à-dire O( N^2). En moyenne, le temps de fonctionnement sera proportionnel à N^2/4, soit deux fois plus rapide que l'algorithme précédent. Dans mon implémentation, en raison de l'utilisation non optimale de la permutation, le temps d'exécution était plus long que celui de Selection. Je prévois de corriger et de mettre à jour le message bientôt. Voici le code et le résultat de son opération sur la même machine :

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Tri de coquille. Tri des coquilles

Un type intelligent, Donald Schell, a remarqué en 1959 que les cas les plus coûteux dans l'algorithme d'insertion sont ceux où l'élément revient très loin au début du tableau : lors d'un certain passage, nous ramenons l'élément au début de quelques positions. , et lors d'un autre passage, presque tout le tableau jusqu'au début est très long. Est-il possible de le faire en même temps, en passant par plusieurs éléments ? Et il a trouvé un tel moyen. Il consiste à effectuer séquentiellement des tris partiels spéciaux, généralement appelés tri-d ou, selon Sedgwick, tri-h (je soupçonne que h signifie hop). Le tri en 3, par exemple, comparera l'élément en question non pas avec le précédent, mais en sautera deux et comparera avec celui 3 positions en arrière. S'il est modifié, il le comparera à nouveau avec l'élément 3 positions en arrière et ainsi de suite. L'essentiel est que le tableau résultant sera « trié en 3 », c'est-à-dire que la position incorrecte des éléments sera inférieure à 3 positions. Travailler avec cet algorithme d'insertion sera facile et agréable. À propos, le « tri-1 » n'est rien de plus qu'un simple algorithme d'insertion =) En appliquant séquentiellement le tri-h au tableau avec des valeurs h décroissantes, nous pouvons trier un grand tableau plus rapidement. Voici à quoi cela ressemble : Afficher Le défi ici est de savoir comment choisir la bonne séquence de tris partiels. En fin de compte, les performances de l’algorithme en dépendent. La plus courante est la séquence proposée par Donald Knuth : h = h*3 + 1, soit 1, 4, 13, 40, ... et ainsi de suite jusqu'à 1/3 de la taille du tableau. Cette séquence offre des performances décentes et est également facile à mettre en œuvre. L'analyse de l'algorithme nécessite des tonnes de langage et dépasse mes capacités. L’étendue de l’analyse est également déterminée par les nombreuses variantes des séquences h. Empiriquement, on peut dire que la vitesse de l'algorithme est très bonne - voyez par vous-même : un million d'éléments en moins d'une seconde ! Et voici le code Java avec la séquence Knut.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Tri à bulles. Méthode des bulles

C'est un classique ! Presque tous les programmeurs débutants implémentent cet algorithme. C'est un tel classique que le Dr Sedgwick n'avait même pas d'animation pour cela, j'ai donc dû faire le travail moi-même. Afficher Ici, à chaque passage, nous parcourons le tableau du début à la fin, en échangeant les éléments voisins qui sont dans le désordre. En conséquence, les éléments les plus grands « flottent » (d’où le nom) jusqu’à la fin du tableau. Nous commençons chaque nouvelle passe avec optimisme en espérant que le tableau soit déjà trié ( sorted = true). A la fin du passage, si nous constatons que nous nous sommes trompés, nous commençons un nouveau passage. La difficulté ici est que, encore une fois, nous parcourons (presque) tout le tableau à chaque passage. La comparaison se produit à chaque étape, l'échange se produit à presque chaque étape, ce qui fait de cet algorithme l'un des plus lents (si l'on considère ceux mis en œuvre de manière rationnelle, et non le « tri secoué » et d'autres comme ça). Il est intéressant de noter que formellement, la complexité ici sera également égale à O(N^2), mais le coefficient est bien supérieur à celui des insertions et des sélections. Code de l'algorithme :

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Autonomie : Sentez la différence : plus d'une demi-heure sur un million d'éléments ! Conclusion : n'utilisez jamais cet algorithme !!!

Résumé de la première partie

En conséquence, je suggère de consulter le tableau général de ces algorithmes. Vous pouvez également comparer avec les résultats de la méthode intégrée java.util.Arrays.sort(). Cela ressemble à une sorte de magie : qu'est-ce qui pourrait être plus rapide que Shell ? J'écrirai à ce sujet dans la partie suivante. Nous y examinerons les algorithmes de tri rapide largement utilisés, ainsi que le tri par fusion, découvrirons la différence entre les méthodes de tri des tableaux à partir des types primitifs et de référence, et nous familiariserons également avec une interface très importante dans ce domaineComparable ;) Ci-dessous, vous pouvez étudier un graphique construit sur une échelle logarithmique à l'aide de tableaux de données. Plus la ligne est plate, meilleur est l'algorithme =) Pour ceux qui souhaitent télécharger l'intégralité du projet et lancer des tests par eux-mêmes, gardez le lien : Java Rendez-vous dans la prochaine partie ! =)