Le tri “Shaker”, également appelé tri “Cocktail”, tri “Shuttle”, tri “boustrophédon” ou “tri à bulles bidirectionnel” est une variante du tri à bulles.

Avec le tri à bulle classique on a des “lièvres” et des “tortues”. Les “lièvres”, sont les éléments de fin de liste qui migrent rapidement à leur place définitive et les “tortues” ceux de début de liste qui se déplacent lentement.

L’idée du tri shaker est d’accélérer les tortues en changeant de direction à chaque itération. Donc, à chaque changement de direction, les “lièvres” deviennent “tortues” et inversement. Il permet non seulement aux plus grands éléments de migrer rapidement vers la fin de la série mais également aux plus petits éléments de migrer plus vite vers le début.

L’animation ci-dessous détaille le fonctionnement du tri shaker :

Pascal Python C Basic Structogramme Ordinogramme
Normale Rapide Lente Très lente
Aléatoire Le pire des cas Le meilleur des cas

Vous trouverez ici une petite vidéo qui montre cet algorithme.

Vidéo du tri Shaker

Travaux pratiques

Le mini-jeu ci-dessous vous permet d’essayer de trier, par ordre de poids croissant, une suite de 5 tonneaux, avec juste une balance pour les comparer. Vous pouvez essayer de le résoudre avec cette méthode de tri.

Variantes

La version de cet algorithme que l’on rencontre le plus souvent est composée de deux boucles imbriquées.

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}
void shakersort(int vect[], int size) {
    int step, current;
    for (step = 1; step <= size / 2; step++)
    {
        for (current = step - 1; current < size - step; current++)
            if (vect[current] > vect[current+1])
                swap(&vect[current], &vect[current + 1]);
        for (current = size - step - 1; current >= step; current--)
            if (vect[current] < vect[current-1])
                swap(&vect[current], &vect[current - 1]);
    }
}

Comme pour le tri bulle, on peut s’arrêter après un parcours sans permutation, quelque soit le sens.

Complexité

Le tri shaker n’apporte pas grand chose au tri bulle.

Dans le pire des cas, avec des données triées à l’envers, les parcours successifs du tableau imposent d’effectuer (n2 - n) comparaisons et (n2 - n) / 2 échanges. Par exemple, pour une liste de 10 éléments, il faudra, dans le pire des cas, faire 45 comparaisons et 45 échanges [ (102 - 10) / 2 ]. La complexité en temps est donc quadratique, de l’ordre de O(n2).

En moyenne, lorsque l’ordre initial des éléments à trier est aléatoire, on considère qu’il faudra faire (n2 - 2*n) / 4 échanges. C’est un peu mieux que le tri bulle classique mais la complexité reste de l’ordre de O(n2).

Dans le meilleur des cas, quand la liste est déjà triée, il faudra (n - 1) comparaisons et aucune permutation. La complexité en temps est linéaire, en O(n).

En espace utilisé (coût en mémoire de l’algorithme), la complexité du tri bulle est linéaire. Elle croit à la même vitesse que le nombre de données en entrée. Elle est donc de O(n).

L’animation ci-dessous permet de vérifier, de manière empirique, cette évolution du nombre d’opérations en fonction du nombre d’éléments à trier.

Taille données Comparaisons Echanges Total

Pour vous faire une idée plus concrète des performances de cet algorithme, supposez que vous deviez trier par ordre alphabétique le répertoire des habitants de plusieurs grandes villes. Et que la machine dont vous disposez peut effectuer disons dix millions d’instructions par seconde. Voici le temps qui serait nécessaire avec cette méthode :


Ville Nombre d'habitants Durée du tri
Paimpol 7 172
Helsinki 631 695
Denver 705 576
Stockholm 975 551
Berlin 3 520 031
Nairobi 4 734 881
Barcelone 5 407 264
Rio 6 718 000
Moscou 12 655 050
Lagos 22 829 561
Shanghai 24 870 895
Séoul 26 000 782
Manille 28 644 207
Tokyo 42 796 714

Vous pouvez changer le nombre d’instructions par seconde, pour tester.

Comic Strip