algorithm
Sort étrange

Informations élémentaires

Un tri impair ou un tri de briques est un algorithme de tri simple, développé pour être utilisé sur des processeurs parallèles avec interconnexion locale. Cela fonctionne en comparant toutes les paires d'index adjacents impairs / pairs de la liste et, si une paire est dans le mauvais ordre, les éléments sont commutés. L'étape suivante répète ceci pour les paires indexées paires / impaires. Ensuite, il alterne les étapes impaires / paires et paires / impaires jusqu'à ce que la liste soit triée.

Pseudo code pour Odd-Even Sort:

if n>2 then
    1. apply odd-even merge(n/2) recursively to the even subsequence a0, a2, ..., an-2 and to the odd subsequence a1, a3, , ..., an-1
    2. comparison [i : i+1] for all i element {1, 3, 5, 7, ..., n-3}
else
    comparison [0 : 1]

Wikipedia a la meilleure illustration du genre Odd-Even:

Exemple de tri impair:

La mise en oeuvre:

J'ai utilisé le langage C # pour implémenter l'algorithme de tri Odd-Even.

public class OddEvenSort
{
    private static void SortOddEven(int[] input, int n)
    {
        var sort = false;

        while (!sort)
        {
            sort = true;
            for (var i = 1; i < n - 1; i += 2)
            {
                if (input[i] <= input[i + 1]) continue;
                var temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                sort = false;
            }
            for (var i = 0; i < n - 1; i += 2)
            {
                if (input[i] <= input[i + 1]) continue;
                var temp = input[i];
                input[i] = input[i + 1];
                input[i + 1] = temp;
                sort = false;
            }
        }
    }

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

Espace auxiliaire: O(n)
Complexité temporelle: O(n)