sort bubble best algorithms algorithm sorting list

algorithm - bubble - ¿Es más rápido ordenar una lista después de insertar elementos o agregarlos a una lista ordenada?



sorting algorithms comparison (13)

Si tengo una lista ordenada (digamos quicksort para ordenar), si tengo muchos valores para agregar, ¿es mejor suspender la ordenación y agregarla al final, luego ordenarla o usar chuleta binaria para colocar los elementos correctamente mientras agregarlos. ¿Hace una diferencia si los artículos son aleatorios, o ya están más o menos en orden?

(Si la lista de la que está hablando es como C # List<T> .) Agregar algunos valores a las posiciones correctas en una lista ordenada con muchos valores requerirá menos operaciones. Pero si el número de valores que se agrega se vuelve grande, requerirá más.

Sugeriría usar no una lista sino una estructura de datos más adecuada en su caso. Como un árbol binario, por ejemplo. Una estructura de datos ordenada con un tiempo de inserción mínimo.

En principio, es más rápido crear un árbol que ordenar una lista. Los insertos de árbol son O (log (n)) para cada inserción, lo que lleva a O (n log (n)) general. Clasificando en O (n log (n)).

Es por eso que Java tiene TreeMap, (además de las implementaciones TreeSet, TreeList, ArrayList y LinkedList de una lista).

  • Un TreeSet mantiene las cosas en orden de comparación de objetos. La clave está definida por la interfaz Comparable.

  • Una LinkedList mantiene las cosas en el orden de inserción.

  • Un ArrayList usa más memoria, es más rápido para algunas operaciones.

  • Un TreeMap, de manera similar, elimina la necesidad de ordenar por una clave. El mapa está construido en orden de clave durante las inserciones y se mantiene ordenado en todo momento.

Sin embargo, por alguna razón, la implementación Java de TreeSet es bastante más lenta que usar una ArrayList y una ordenación.

[Es difícil especular sobre por qué sería mucho más lento, pero lo es. Debería ser un poco más rápido con un pase a través de los datos. Este tipo de cosas a menudo es el costo de la administración de la memoria que supera el análisis algorítmico.]

En un nivel alto, es un problema bastante simple, porque puede pensar en clasificar como una búsqueda iterada. Cuando desee insertar un elemento en una matriz ordenada, lista o árbol, debe buscar el punto donde insertarlo. Luego lo pones, con la esperanza de que sea de bajo costo. Entonces, podrías pensar en un algoritmo de clasificación simplemente tomando un montón de cosas y, una por una, buscando la posición correcta e insertándolas. Por lo tanto, una ordenación de inserción (O (n * n)) es una búsqueda lineal iterada (O (n)). Árbol, montón, fusión, raíz y ordenación rápida (O (n * log (n))) se puede considerar como una búsqueda binaria iterada (O (log (n))). Es posible tener un orden O (n), si la búsqueda subyacente es O (1) como en una tabla hash ordenada. (Un ejemplo de esto es ordenar 52 cartas arrojándolas en 52 contenedores).

Entonces, la respuesta a su pregunta es, insertar cosas de una en una, en lugar de guardarlas y luego ordenarlas no debería hacer mucha diferencia, en un gran sentido de O. Por supuesto, podría tener factores constantes con los que lidiar, y esos podrían ser importantes.

Por supuesto, si n es pequeño, como 10, toda la discusión es tonta.

Es casi lo mismo. Insertar un ítem en una lista ordenada es O (log N), y al hacer esto para cada elemento en la lista, N (así construyendo la lista) sería O (N log N) que es la velocidad de quicksort (o merge sort que está más cerca de este enfoque).

Si en su lugar los inserta en el frente, sería O (1), pero al hacer un quicksort después, todavía sería O (N log N).

Me gustaría ir con el primer enfoque, porque tiene el potencial de ser un poco más rápido. Si el tamaño inicial de su lista, N, es mucho mayor que el número de elementos para insertar, X, entonces el enfoque de inserción es O (X log N). La ordenación después de insertar en el encabezado de la lista es O (N log N). Si N = 0 (IE: su lista está inicialmente vacía), la velocidad de inserción en orden ordenado o la clasificación posterior son las mismas.

Insertar un elemento en una lista ordenada es O (log n), mientras que ordenar una lista es O (n log N) Lo que sugeriría que siempre es mejor ordenar primero y luego insertar

Pero recuerde que la gran ''O'' solo se refiere al aumento de la velocidad con el número de elementos, puede ser que para su aplicación una inserción en el medio sea costosa (por ejemplo, si fuera un vector) y agregar y clasificar después podría ser mejor.

Insertar un elemento en una lista ordenada requiere O(n) tiempo, no O(log n) tiempo. Tienes que encontrar el lugar para ponerlo, tomando el tiempo O(log n) . Pero luego tienes que desplazarte sobre todos los elementos, tomando O(n) tiempo. Entonces, insertar mientras se mantiene la ordenada es O(n ^ 2) , donde al insertarlos todos y luego ordenar es O(n log n) .

Dependiendo de su implementación de clasificación, puede obtener incluso mejor que O(n log n) si la cantidad de insertos es mucho menor que el tamaño de la lista. Pero si ese es el caso, no importa de ninguna manera.

Entonces, inserte todo y ordene la solución si la cantidad de insertos es grande, de lo contrario, probablemente no importará.

Por lo general, es mucho mejor usar un heap . en resumen, divide el costo de mantener el orden entre el empujador y el selector. Ambas operaciones son O (log n), en lugar de O (n log n), como la mayoría de las otras soluciones.

Si agrega suficientes elementos para construir la lista desde cero, podrá obtener un mejor rendimiento clasificando la lista posteriormente.

Si los elementos están en su mayoría en orden, puede ajustar tanto la actualización incremental como la ordenación regular para aprovechar eso, pero, francamente, generalmente no vale la pena. (También debe tener cuidado con cosas como asegurarse de que un pedido inesperado no pueda hacer que su algoritmo tarde mucho más , por ejemplo, quicksort).

Tanto la actualización incremental como la ordenación regular de listas son O (N log N) pero puede obtener un mejor factor constante ordenando todo después (supongo que tiene alguna estructura de datos auxiliar para que su actualización incremental pueda acceder a los elementos de la lista más rápido que O (NORTE)...). En general, ordenar todo de una vez tiene mucha más libertad de diseño que mantener la ordenación de forma incremental, ya que la actualización incremental tiene que mantener un orden completo en todo momento, pero una clasificación masiva a la vez no lo hace.

Si nada más, recuerde que hay muchos géneros masivos altamente optimizados disponibles.

Si está agregando conjuntos, puede usar un tipo de fusión. Ordene la lista de elementos que se agregarán, luego copie de ambas listas y compare los elementos para determinar cuál se copiará a continuación. Incluso puede copiar en el lugar si cambia el tamaño de su matriz de destino y trabajar desde el final hacia atrás.

La eficiencia de esta solución es O (n + m) + O (m log m) donde n es el tamaño de la lista original, ym es el número de elementos que se insertan.

Editar: Dado que esta respuesta no está recibiendo ningún amor, pensé que lo desarrollaría con algún código de muestra C ++. Supongo que la lista ordenada se mantiene en una lista vinculada en lugar de una matriz. Esto cambia el algoritmo para que parezca más una inserción que una fusión, pero el principio es el mismo.

// Note that itemstoadd is modified as a side effect of this function template<typename T> void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd) { std::sort(itemstoadd.begin(), itemstoadd.end()); std::list<T>::iterator listposition = sortedlist.begin(); std::vector<T>::iterator nextnewitem = itemstoadd.begin(); while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end())) { if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition)) sortedlist.insert(listposition, *nextnewitem++); else ++listposition; } }

Si esto es .NET y los ítems son enteros, es más rápido agregarlos a un diccionario (o si está usando .Net 3.0 o superior, use el HashSet si no le importa perder duplicados). Esto le brinda clasificación automática.

Creo que las cadenas funcionarían de la misma manera también. La belleza es que obtienes O (1) inserción y clasificación de esta manera.

Si la lista es a) ya ordenada, yb) de naturaleza dinámica, la inserción en una lista ordenada siempre debe ser más rápida (encuentre el lugar correcto (O (n)) e inserte (O (1))).

Sin embargo, si la lista es estática, debe ocurrir una mezcla del resto de la lista (O (n) para encontrar el lugar correcto y O (n) para deslizar las cosas hacia abajo).

De cualquier manera, insertar en una lista ordenada (o algo así como un árbol de búsqueda binaria) debería ser más rápido.

O (n) + O (n) siempre debe ser más rápido que O (N log n).

Yo diría, ¡probemos! :)

Intenté con quicksort, pero ordenar una matriz de ordenación con quicksort es ... bueno, no es una buena idea. Intenté uno modificado, cortando en 7 elementos y usando la ordenación por inserción para eso. Aún así, actuación horrible. Cambié para fusionar el género. Puede necesitar bastante memoria para ordenar (no está en su lugar), pero el rendimiento es mucho mejor en arreglos ordenados y casi idéntico en los aleatorios (el orden inicial tomó casi el mismo tiempo para ambos, el quicksort fue solo un poco más rápido) )

Esto ya muestra una cosa: la respuesta a sus preguntas depende en gran medida del algoritmo de clasificación que utilice. Si tiene un rendimiento deficiente en las listas casi ordenadas, insertar en la posición correcta será mucho más rápido que agregar al final y luego volver a clasificarlo; y la clasificación por fusión podría no ser una opción para usted, ya que podría necesitar demasiada memoria externa si la lista es enorme. Por cierto, utilicé una implementación de tipo de combinación personalizada, que solo usa 1/2 de almacenamiento externo para la implementación ingenua (que necesita tanto almacenamiento externo como el tamaño de la matriz).

Si la ordenación por fusión no es una opción y la ruta rápida no es una opción segura, la mejor alternativa probablemente sea la ordenación en pila.

Mis resultados son: agregar los nuevos elementos simplemente al final y luego volver a ordenar la matriz fue varias magnitudes más rápido que insertarlos en la posición correcta. Sin embargo, mi matriz inicial tenía 10 mio elements (ordenados) y estaba agregando otro mio (sin clasificar). Entonces, si agrega 10 elementos a una matriz de 10 mio, insertarlos correctamente es mucho más rápido que volver a ordenar todo. Por lo tanto, la respuesta a su pregunta también depende de qué tan grande sea la matriz inicial (ordenada) y cuántos elementos nuevos desee agregar.