algorithm
Tri de coquille

Shell Trier les informations de base

Le tri de shell , également appelé tri par incrément décroissant, est l'un des plus anciens algorithmes de tri, nommé d'après son inventeur Donald. L. Shell (1959). C'est rapide, facile à comprendre et à mettre en œuvre. Cependant, son analyse de complexité est un peu plus sophistiquée.

L'idée du tri de Shell est la suivante:

1. Organiser la séquence de données dans un tableau à deux dimensions
2. Trier les colonnes du tableau

Le tri shell améliore le tri par insertion. Il commence par comparer des éléments éloignés les uns des autres, puis des éléments moins éloignés, et finalement en comparant des éléments adjacents (en fait, un tri par insertion).

L'effet est que la séquence de données est partiellement triée. Le processus ci-dessus est répété, mais chaque fois avec un tableau plus étroit, c'est-à-dire avec un nombre de colonnes plus petit. Dans la dernière étape, le tableau ne comprend qu’une seule colonne.

Exemple de tri Shell:

Pseudo code pour Shell Sort:

input
foreach element in input
{
    for(i = gap; i < n; i++)
    {
        temp = a[i]
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        a[j] = temp
    }
}

Espace auxiliaire: O(n) total, O(1) auxiliary
Complexité temporelle: O(nlogn)

Implémentation C #

public class ShellSort
{
    static void SortShell(int[] input, int n)
    {
        var inc = 3;
        while (inc > 0)
        {
            int i;
            for (i = 0; i < n; i++)
            {
                var j = i;
                var temp = input[i];
                while ((j >= inc) && (input[j - inc] > temp))
                {
                    input[j] = input[j - inc];
                    j = j - inc;
                }
                input[j] = temp;
            }
            if (inc / 2 != 0)
                inc = inc / 2;
            else if (inc == 1)
                inc = 0;
            else
                inc = 1;
        }
    }

    public static int[] Main(int[] input)
    {
        SortShell(input, input.Length);
        return input;
    }
}