algorithm - team - Clasificación en el lugar
ranking elo futbol clubes (5)
La clasificación in situ significa la clasificación sin necesidad de espacio adicional. Según wiki , dice
un algoritmo in situ es un algoritmo que transforma la entrada utilizando una estructura de datos con una pequeña cantidad constante de espacio de almacenamiento adicional.
Quicksort es un ejemplo de clasificación in situ.
¿Qué significa "ordenar en el lugar"?
La idea de un algoritmo in situ no es exclusiva de la clasificación, pero la clasificación es probablemente el caso más importante, o al menos el más conocido. La idea es sobre la eficiencia del espacio: usar la cantidad mínima de RAM, disco duro u otro tipo de almacenamiento que pueda utilizar. Esto fue especialmente relevante en algunas décadas, cuando el hardware era mucho más limitado.
La idea es producir una salida en el mismo espacio de memoria que contiene la entrada transformando sucesivamente esos datos hasta que se produzca la salida. Esto evita la necesidad de utilizar dos veces el almacenamiento: un área para la entrada y un área de igual tamaño para la salida.
La clasificación es un caso bastante obvio para esto porque la clasificación se puede realizar intercambiando artículos repetidamente, ya que la clasificación solo reorganiza los elementos. Los intercambios no son el único enfoque; por ejemplo, la clasificación de inserción utiliza un enfoque ligeramente diferente que equivale a realizar una serie de intercambios, pero más rápido.
Otro ejemplo es la transposición matricial : una vez más, esto se puede implementar intercambiando elementos. La adición de dos números muy grandes también se puede hacer in situ (el resultado reemplaza a una de las entradas) comenzando por el dígito menos significativo y propagando hacia arriba.
Volviendo a la clasificación, las ventajas de reorganizarse "en el lugar" se vuelven aún más obvias cuando se piensa en pilas de tarjetas perforadas : es preferible evitar copiar las tarjetas perforadas solo para ordenarlas.
Algunos algoritmos de clasificación permiten este estilo de operación in situ mientras que no lo hacen.
Sin embargo, todos los algoritmos requieren algún almacenamiento adicional para las variables de trabajo. Si el objetivo es simplemente producir la salida modificando sucesivamente la entrada, es bastante fácil definir algoritmos que lo hagan al reservar una gran cantidad de memoria, usarla para producir una estructura de datos auxiliar, y luego usarla para guiar esas modificaciones. Aún está produciendo la salida al transformar la entrada "en su lugar", pero está derrotando todo el punto del ejercicio: no está aprovechando el espacio.
Por esa razón, la definición normal de una definición en el lugar requiere que se logre algún estándar de eficiencia de espacio. Es absolutamente inaceptable usar espacio adicional proporcional a la entrada (es decir, O (n) espacio adicional) y aún llamar a su algoritmo "in situ".
La página de Wikipedia sobre algoritmos in situ reclama actualmente que un algoritmo in situ solo puede usar una cantidad constante de espacio adicional (O (1)).
En informática, un algoritmo in situ (o en latín in situ) es un algoritmo que transforma la entrada utilizando una estructura de datos con una pequeña cantidad constante de espacio de almacenamiento adicional.
Hay algunos aspectos técnicos especificados en la sección En complejidad computacional , pero la conclusión es que, por ejemplo, Quicksort requiere espacio O (log n) (verdadero) y, por lo tanto, no está en su lugar (lo que creo que es falso).
O (log n) es mucho más pequeño que O (n); por ejemplo, el registro de base 2 de 16,777,216 es 24.
Normalmente, ambos, Quicksort y heapsort se consideran in situ, y heapsort se puede implementar con O (1) espacio adicional (antes me equivoqué). Mergesort es más difícil de implementar en el lugar, pero la versión fuera de lugar es muy fácil de almacenar en caché. Sospecho que las implementaciones en el mundo real aceptan la sobrecarga de espacio O (n). por lo tanto, la memoria de trading para la eficiencia y la velocidad de la memoria caché suele ser un buen negocio.
[ EDITAR Cuando escribí lo anterior, asumo que estaba pensando en una clasificación en el lugar de una matriz. La clasificación en el lugar de una lista enlazada es muy simple. La diferencia clave está en el algoritmo de combinación: hacer una combinación de dos listas vinculadas sin copiar o reasignar es fácil, hacer lo mismo con dos subarreglos de una matriz más grande (y sin O (n) almacenamiento auxiliar) AFAIK no es .]
Quicksort también es eficiente en caché, incluso en el lugar, pero puede ser descalificado como un algoritmo en el lugar apelando a su peor comportamiento. Hay un caso degenerado (en una versión no aleatoria, generalmente cuando la entrada ya está ordenada) donde el tiempo de ejecución es O (n ^ 2) en lugar de la O (n log n) esperada. En este caso, el requisito de espacio adicional también se incrementa a O (n). Sin embargo, para conjuntos de datos grandes y con algunas precauciones básicas (principalmente selección aleatoria de pivote), este comportamiento en el peor de los casos se vuelve absurdamente improbable.
Mi opinión personal es que el espacio adicional O (log n) es aceptable para los algoritmos in situ, no es trampa, ya que no anula el punto original de trabajar in situ.
Sin embargo, mi opinión es, por supuesto, sólo mi opinión.
Una nota adicional: a veces, la gente llamará a una función en el lugar simplemente porque tiene un solo parámetro para la entrada y la salida. No necesariamente se sigue que la función fue eficiente en el espacio, que el resultado se produjo al transformar la entrada, o incluso que el parámetro aún hace referencia a la misma área de la memoria. Este uso no es correcto (o, por lo tanto, los prescriptivists reclamarán), aunque es lo suficientemente común como para que sea mejor estar consciente pero no estresarse por ello.
No creo que estos términos estén estrechamente relacionados:
Ordenar en el lugar significa ordenar una lista existente modificando el orden de los elementos directamente dentro de la lista. Lo contrario es dejar la lista original tal como está y crear una nueva lista con los elementos en orden.
El orden natural es un término que describe cómo los objetos completos pueden ordenarse de alguna manera. Por ejemplo, puede decir que 0 es inferior a 1 (orden natural para enteros) o que A está antes que B en orden alfabético (orden natural para cadenas). Sin embargo, difícilmente se puede decir que Bob sea mayor o menor que Alicia en general, ya que depende en gran medida de atributos específicos (alfabéticamente por nombre, por edad, por ingreso, ...). Por lo tanto, no hay un orden natural para las personas .
No estoy seguro de que estos conceptos sean lo suficientemente similares para compararlos como se sugiere. Sí, ambos implican una clasificación, pero uno se trata de un orden de clasificación que es humano comprensible (natural) y el otro define un algoritmo para una clasificación eficiente en términos de memoria al sobrescribir en la estructura existente en lugar de usar una estructura de datos adicional (como una ordenamiento de burbuja)
se puede hacer usando la función de intercambio, en lugar de crear una estructura completamente nueva, implementamos ese algoritmo sin siquiera saber su nombre: D