algorithm
Ungerade-gerade Sortierung

Ungerade Sortierung Grundlegende Informationen

Eine Odd-Even Sort-Sortierung oder Ziegelsortierung ist ein einfacher Sortieralgorithmus, der für die Verwendung auf parallelen Prozessoren mit lokaler Verbindung entwickelt wurde. Dabei werden alle ungeraden / geraden indizierten Paare benachbarter Elemente in der Liste verglichen. Wenn ein Paar in der falschen Reihenfolge ist, werden die Elemente umgeschaltet. Im nächsten Schritt wird dies für gerade / ungerade indizierte Paare wiederholt. Dann wird zwischen ungeraden / geraden und geraden / ungeraden Schritten gewechselt, bis die Liste sortiert ist.

Pseudo-Code für ungerade gerade Sortierung:

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 hat die beste Illustration der Odd-Even-Sorte:

Beispiel für eine ungerade Sortierung:

Implementierung:

Ich habe die C # -Sprache verwendet, um den Odd-Even-Sortieralgorithmus zu implementieren.

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

Hilfsraum: O(n)
Zeitkomplexität: O(n)