Sortieralgorithmus, so dass jedes Element

Gibt es bekannte Vergleichs-Sortieralgorithmen, die sich nicht auf das Sortieren von Netzwerken reduzieren, sodass jedes Element -mal verglichen wird ? $O(\log n)$

Soweit ich weiß, besteht die einzige Möglichkeit, mit -Vergleich für jedes Element zu sortieren, darin, ein AKS-Sortiernetz für Eingaben zu erstellen und die Eingabe im Sortiernetz auszuführen. $O(\log n)$ $n$

AKS ist nicht einfach zu implementieren und hat einen unpraktischen konstanten Faktor. Daher gibt es Gründe, nach anderen Algorithmen zu suchen.

Ein Algorithmus mit Vergleiche pro Element , das scheint nicht eine Sortier Netzwerk zu implizieren , präsentiert hier . (iirc, dies wurde zuerst von Rob Johnson auf dem Algorithmus-Seminar von Stony Brook vorgestellt). $O(\log^2 n)$

ds.algorithms sorting sorting-network Chao Xu
quelle

Ich verstehe die Frage nicht: Viele sequentielle Algorithmen scheinen Ihrer Anfrage zu entsprechen. zB Merge Sort ist ein klassischer Sortieralgorithmus, der nicht mehr als

Vergleiche pro Element durchführt. Vielleicht fragen Sie nach parallelen Sortieralgorithmen?

\log n

$\log n$

Jeremy

@ Jeremy: Wenn zwei Listen fusionieren,

und

, kann man am Ende Vergleich

gegen jede der

Vergleiche pro Element. Und dies war nur ein "Zusammenführungs" -Schritt. Natürlich der Durchschnitt

(a_{1}, . . ., a_{n})

$(a_1, ..., a_n)$

(b_{1}, . . ., b_{n})

$(b_1, ..., b_n)$

a_{1}

$a_1$

b_{1}, . . ., b_{n}

$b_1, ..., b_n$

Ω (n)

$\Omega(n)$ Die Anzahl der Vergleiche ist notwendigerweise gering, aber die Frage ist nach der Komplexität im schlimmsten Fall .

Jukka Suomela

Ich glaube das ist möglich. Sortiernetzwerke sind datenunabhängig und verfügen über vorgegebene Vergleiche. Ein Sortieralgorithmus kann jedoch abhängig von den Daten zwischen verschiedenen Operationen wählen. Man kann Merge-Sortierung in einen Algorithmus mit

-Vergleich für jedes Element ändern und scheint kein Sortierungsnetzwerk zu implizieren. Reddit.com/comments/9jqsi/…

O (\log^{2} n)

$O(\log^2 n)$

Chao Xu

(a_{1}, \dots, a_{n})

$(a_1,\ldots,a_n)$

(b_{1}, \dots, b_{n})

$(b_1,\ldots,b_n)$

n

$n$

\lg n

$\lg n$

Jetzt gibt es eine neue verwandte (aber hoffentlich viel einfachere) Frage: cstheory.stackexchange.com/questions/8073/…

Jukka Suomela

Sortieralgorithmus, so dass jedes Element

Antworten: