Optimaler Sortieralgorithmus in Anzahl der Swaps

Kann es bei einer gegebenen Folge von Zahlen mit Vergleichen und Swaps / Moves sortiert werden ? Alle Verweise auf Veröffentlichungen zu diesem Thema oder Gegenargumente, die eine Untergrenze von , wären hilfreich. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

cc.complexity-theory ds.algorithms Jesse Zixi Zhang
quelle

Jeder vergleichsbasierte Sortieralgorithmus muss im schlimmsten Fall Vergleiche und Swaps durchführen (vgl. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

Kaveh

Trivialerweise können Sie

-Moves erzielen, wenn Sie zuerst eine Tabelle sortieren, die die Indizes der Elemente enthält, und erst danach die Tabelle, die die Elemente enthält.

O (n)

$O(n)$

Jukka Suomela

@jukka Nun, das ist Betrug, weil Sie Elemente verschoben, als Sie die Tabelle sortiert ...

Jesse Zixi Zhang

Antworten:

$O(n \log n)$ $O(n)$

Snowie
quelle