Clasificación casi matriz ordenada en $O(n)$ tiempo

Question

¿Cuál es la mejor manera de ordenar una matriz que tiene al menos la mitad de sus elementos en su posición final? Es posible lograr la $O(n)$ el tiempo de ejecución?

Answer 1

$O(n)$ no es posible ya que su posición inicial podría ser $\frac n2$ de pequeños elementos en el orden correcto seguido por $\frac n2$ elementos en orden aleatorio. La clasificación de la última toma $O(n\ln n)$.

Answer 2

Yo creo que se puede conseguir una mejora en el tiempo lineal si sólo $\frac{n}{\log{n}}$ artículos están fuera de lugar. En primer lugar, elegir los elementos fuera de lugar (que se producirá en carreras donde los extremos no se pueden comparar correctamente con un vecino), esto lleva tiempo lineal. A continuación, utilice una búsqueda binaria en el resto correctamente ordenados los elementos para encontrar la posición correcta para cada elemento fuera de lugar, esto se lleva a $O(\log{n})$ tiempo para cada elemento, por lo que el tiempo total es:$O(n)$.