algorithm
Oneven-even sorteren

Oneven-even sorteer basisinformatie

Een oneven-even sort of brick sort is een eenvoudig sorteeralgoritme, dat is ontwikkeld voor gebruik op parallelle processors met lokale interconnectie. Het werkt door alle oneven / even geïndexeerde paren van aangrenzende elementen in de lijst te vergelijken en, als een paar in de verkeerde volgorde staat, worden de elementen omgewisseld. De volgende stap herhaalt dit voor even / oneven geïndexeerde paren. Daarna wisselt het tussen oneven / even en even / oneven stappen totdat de lijst is gesorteerd.

Pseudo-code voor oneven-even sorteren:

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 heeft de beste illustratie van de even-oneven soort:

Voorbeeld van oneven-even sortering:

Implementatie:

Ik gebruikte C # -taal om een even of oneven sorteeralgoritme te implementeren.

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;
    }
}

Hulpruimte: O(n)
Tijd Complexiteit: O(n)