Algoritmo de ordenación óptimo en número de intercambios

Dada una secuencia de números, ¿se puede ordenar con comparaciones y intercambios / movimientos? Cualquier puntero a publicaciones sobre ese tema o contraargumentos que muestren un límite inferior ayudaría. $n$ $O(n \ln n)$ $O(n)$ $\Omega(n \ln n)$

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

Cualquier algoritmo de clasificación basado en la comparación necesitará realizar comparaciones

e intercambios

en el peor de los casos (cf. CLRS).

Ω (n \log n)

$\Omega(n \log n)$

Ω (n)

$\Omega(n)$

Kaveh

Trivialmente, puede lograr movimientos

si primero ordena una tabla que contiene los índices de los elementos, y solo después de eso ordena la tabla que contiene los elementos.

O (n)

$O(n)$

Jukka Suomela

@jukka bueno, eso es trampa porque moviste elementos cuando

ordenaste

Respuestas:

Existe un algoritmo de clasificación in situ estable con comparaciones y movimientos . $O(n \log n)$ $O(n)$

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

Snowie
fuente