¿Cómo puedo ordenar rápidamente una matriz de elementos que ya está ordenada, excepto por un pequeño número de elementos, por ejemplo, hasta 1/4 del total, cuyas posiciones se conocen, por ejemplo, 1,2,3,4,8,6 , 7,8,2,10,11,3,13,14,15,16. Este conjunto se ordena guardar 4,8,11?

Ordene los elementos fuera de orden [math] k [/ math] usando su algoritmo favorito [math] O (k \ log k) [/ math], luego haga una fusión [math] O (n) [/ math] operación para combinar estos elementos recién ordenados [math] k [/ math] con los otros elementos [math] n – k [/ math] ya ordenados en una gran matriz ordenada.

Este tiempo de ejecución [matemática] O (n + k \ log k) [/ matemática] es demostrablemente óptimo en el modelo de comparación, incluso bajo su restricción de dirección hipotética.

(Según el comentario de su pregunta, parece que ya conoce este algoritmo, pero todas las otras respuestas parecían sugerir un tipo de inserción, que tiene un tiempo de ejecución estrictamente peor [matemáticas] O (nk + k ^ 2) [/ matemáticas]. Vamos chicos , CS 101: todos deberían saber que los algoritmos de clasificación cuadrática apestan. No puedo creer que los desarrolladores sigan cometiendo este error, pero lo están haciendo).

Utilice la selección de reemplazo bidireccional ya que conserva el orden de clasificación cuando los lotes ordenados tienen un orden, sin importar si son hacia adelante o hacia atrás, y todavía hay algunos elementos sin clasificar. Este fue un trabajo realizado por Data Management Group. DAMA-UPC

Aquí hay algunos pensamientos más.

1. ¿Sus datos son dinámicos? ¿Aparece como una secuencia? En este caso, la ordenación por inserción funciona mejor como un algoritmo en línea. Como señaló Prateek Sharma, la ordenación por inserción funciona bien en matrices casi ordenadas. Generalmente, la ordenación por inserción y la ordenación rápida se combinan para obtener mejores resultados. Cuando la recursividad de ordenación rápida alcanza un tamaño de matriz menor que el tamaño M predefinido, optamos por la ordenación por inserción, ya que es más eficiente. En promedio, la ordenación por inserción toma [matemática] O (N ^ 2/4) [/ matemática].

2. Basado en búsqueda binaria y clasificación de inserción.

A) Busque en la matriz de izquierda a derecha para encontrar el “primer elemento que es mayor que el siguiente” A [x]> A [x + 1].

B) Nuevamente, busque la matriz de derecha a izquierda para encontrar “el primer elemento que es más pequeño que el anterior” A [y]

C) Encuentre los elementos máximos y mínimos en la matriz secundaria A [x … y].

1. Si insiste en que debe usar una matriz, no un árbol, entonces combine como señala Anders.

Así que no los guardes en una matriz. Guárdelos directamente en un árbol e insértelos directamente en él. No se desequilibrará mucho

Si usó un árbol (equilibrado) con N elementos y, por lo tanto, la profundidad promedio D = log2 (N) y Dmax = ⌈log2 (N) ⌉, y había M elementos fuera de lugar para insertar, esperaría O ( MD), eso es NlogN. (Aproximadamente de primer orden, descuidando que las inserciones lo desequilibran y la profundidad promedio un poco más; pero también algunas inserciones no necesitan ir a D.)
El montón de latidos de árbol en este caso porque como sabes que ya tienes 3/4 de la estructura construida, no quieres burbujear mucho durante las inserciones.

2. ¿Sería más fácil el problema si los elementos fuera de orden estuvieran fuera de orden en la misma dirección, por ejemplo, demasiado temprano en la secuencia?

Para el caso del árbol, no tendría mucho sentido ajustar el algoritmo ya que si se extendieran al azar, esperaría ahorrar solo ~ una profundidad por inserción. Eso es un ahorro de O (M).

> La aplicación práctica es esta: tengo una matriz en la que ocasionalmente cambian los valores de una fracción de los elementos.

¿Tiene algún conocimiento a priori sobre qué elementos pueden cambiar y cuánto pueden cambiar sus valores? Si lo hiciera, podríamos llegar a una estructura de datos más especializada.

En 1985 desarrollé y publiqué un algoritmo de clasificación único que denominé UnShuffle Sort. Se puede demostrar que UnShuffle es la forma más eficiente de ordenar una lista que contiene elementos ordenados. El rendimiento es lineal en el tamaño de la lista y proporcional a la entropía (o aleatoriedad) en los datos (el orden es: O (kN) donde k es la constante del factor de entropía). Para una lista completamente ordenada, funciona en O (1N)

Aquí hay un enlace a un nuevo artículo que he escrito y estoy planeando publicar sobre una versión actualizada del algoritmo: http://www.askdbmgt.com/uploads/ …

El método de inserción es el algoritmo más eficiente para ordenar arreglos parcialmente ordenados .

Insertion Sort exhibe muy poca sobrecarga, ordena una matriz ya ordenada en un solo barrido y es fácil de codificar.

Puede consultar: http://stackoverflow.com/questio …

Dado que su matriz está casi ordenada, normalmente le recomendaría que pruebe Insertar Clasificación, ya que casi obtendrá el mejor comportamiento del algoritmo de clasificación.

Pero ha mencionado que el tamaño de su matriz puede extenderse hasta 200k elementos, donde usar Insertion Sort puede no parecer una idea factible. En su lugar, puede intentar usar la búsqueda binaria en el orden de inserción en lugar de usar la búsqueda lineal tradicional. O si todo falla, puede intentar usar algunos algoritmos de clasificación O (n lg n) como Merge Sort, Quick Sort u Heap Sort

Use una matriz de memoria empaquetada.