arrays - sort - Ordenar una matriz casi ordenada(elementos extraviados por no más de k)

ordenar array por valor php

Question

Me preguntaron esta pregunta de la entrevista recientemente:

Te dan una matriz que está casi ordenada, en el sentido de que cada uno de los N elementos puede estar fuera de lugar por no más de k posiciones del orden correcto ordenado. Encuentre un algoritmo eficiente en espacio y tiempo para ordenar la matriz.

Tengo una solución O(N log k) siguiente manera.

Digamos que arr[0..n) significa los elementos de la matriz desde el índice 0 (inclusive) hasta N (exclusivo).

• Sort arr[0..2k)
  • Ahora sabemos que arr[0..k) están en sus posiciones finales ordenadas ...
  • ... pero arr[k..2k) todavía puede estar fuera de lugar por k !
• Sort arr[k..3k)
  • Ahora sabemos que arr[k..2k) están en sus posiciones finales ordenadas ...
  • ... pero arr[2k..3k) aún puede estar fuera de lugar por k
• Sort arr[2k..4k)
• ....
• Hasta que arr[ik..N) , ¡ya terminó!
  • Este paso final puede ser más barato que los otros pasos cuando te quedan menos de 2k elementos

En cada paso, clasifica como máximo 2k elementos en O(k log k) , colocando al menos k elementos en sus posiciones finales ordenadas al final de cada paso. Hay O(N/k) pasos, por lo que la complejidad general es O(N log k) .

Mis preguntas son:

• ¿Es O(N log k) óptimo? ¿Se puede mejorar esto?
• ¿Puedes hacer esto sin (parcialmente) reorganizar los mismos elementos?

Answer 1

Como Bob Sedgewick mostró en su trabajo de disertación (y follow-ons), la ordenación por inserción aplasta absolutamente la "matriz casi ordenada". En este caso, sus asintóticos se ven bien, pero si k <12 apuesto a que la ordenación por inserción gana todo el tiempo. No sé si hay una buena explicación de por qué el tipo de inserción funciona tan bien, pero el lugar para buscar estaría en uno de los libros de texto de Sedgewick titulado Algorithms (ha realizado muchas ediciones para diferentes idiomas).

• No tengo idea de si O (N log k) es óptimo, pero más al grano, realmente no me importa; si k es pequeño, son los factores constantes los que importan, y si k es grande, también puede ser justo ordenar la matriz

• La ordenación por inserción resolverá este problema sin volver a ordenar los mismos elementos.

La notación de Big-O está muy bien para la clase de algoritmo, pero en el mundo real, las constantes importan. Es demasiado fácil perder de vista esto. (¡Y lo digo como profesor que ha enseñado la notación Big-O!)

Answer 2

Como aparentemente se supone que k es bastante pequeño, un tipo de inserción es probablemente el algoritmo más obvio y generalmente aceptado.

En una ordenación de inserción en elementos aleatorios, debe escanear N elementos, y debe mover cada uno un promedio de N / 2 posiciones, dando ~ N * N / 2 operaciones totales. La constante "/ 2" se ignora en una caracterización de O grande (o similar), dando complejidad O (N ² ).

En el caso que está proponiendo, el número esperado de operaciones es ~ N * K / 2 - pero como k es una constante, se ignora todo el término k/2 en una caracterización de O grande, por lo que la complejidad general es O (NORTE).

Answer 3

Si usa solo el modelo de comparación, O (n log k) es óptimo. Considere el caso cuando k = n.

Para responder a su otra pregunta, sí, es posible hacer esto sin ordenar, usando montones.

Use un montón mínimo de 2k elementos. Inserta 2k elementos primero, luego elimina el mínimo, inserta el siguiente elemento, etc.

Esto garantiza el tiempo de O (n log k) y el espacio de O (k) y los montones suelen tener constantes ocultas lo suficientemente pequeñas.

Answer 4

Su solución es buena si k es lo suficientemente grande. No hay mejor solución en términos de complejidad de tiempo; cada elemento puede estar fuera de lugar por k lugares, lo que significa que necesita aprender log2 k bits de información para colocarlo correctamente, lo que significa que necesita hacer comparaciones log2 k al menos, por lo que debe ser una complejidad de al menos O(N log k) .

Sin embargo, como otros han señalado, si k es pequeño, los términos constantes te van a matar. Utilice algo que sea muy rápido por operación, como ordenar por inserción, en ese caso.

Si realmente quisiera ser óptimo, implementaría ambos métodos, y cambiaría de uno a otro dependiendo de k .

Answer 5

Ya se señaló que una de las soluciones asintóticamente óptimas usa un montón mínimo y solo quería proporcionar código en Java:

public void sortNearlySorted(int[] nums, int k) {
  PriorityQueue<Integer> minHeap = new PriorityQueue<>();
  for (int i = 0; i < k; i++) {
    minHeap.add(nums[i]);
  }

  for (int i = 0; i < nums.length; i++) {
    if (i + k < nums.length) {
      minHeap.add(nums[i + k]);
    }
    nums[i] = minHeap.remove();
  }
}