Algorithme de tri optimal en nombre de swaps

Étant donné une séquence de nombres, peut-elle être triée avec des comparaisons et swaps / mouvements? Tout pointeur vers des publications à ce sujet ou contre-arguments montrant une borne inférieure serait utile. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

cc.complexity-theory ds.algorithms Jesse Zixi Zhang
la source

Tout algorithme de tri basé sur la comparaison devra effectuer des comparaisons

et des échanges

dans le pire des cas (cf. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

Kaveh

Trivialement, vous pouvez réaliser des mouvements

si vous triez d'abord une table qui contient les index des éléments, et seulement après ce tri la table qui contient les éléments.

O (n)

$O(n)$

Jukka Suomela

@jukka bien c'est tricher car vous avez déplacé des éléments lorsque vous avez trié la table ...

Jesse Zixi Zhang

Réponses:

Il existe un algorithme de tri sur place stable avec des comparaisons et des mouvements . $O(n \log n)$ $O(n)$

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

Snowie
la source