Algoritmo de actualización. ¿Por qué heapsort es un algoritmo insort?

15

No puedo ver por qué el montón se considera un algoritmo de clasificación in situ .

Me refiero a una estructura de datos adicional poblada con los elementos de la matriz que se va a clasificar, es decir, un montón, que se utiliza para ayudar en la extracción del valor mínimo y el proceso de clasificación.

Entonces, ¿puedo estar entendiendo mal la definición de lugar aquí?

Pero el tipo de inserción, por ejemplo, es obvio que es un algoritmo in situ, es decir, no se necesita memoria adicional para los elementos.

Entonces, ¿por qué se considera in situ?

usuario10326
fuente

Respuestas:

12

Me refiero a una estructura de datos adicional poblada con los elementos de la matriz a clasificar, es decir, un montón, que se utiliza para ayudar en la extracción del valor mínimo y el proceso de clasificación.

No. La matriz se transforma para ajustarse a la restricción de almacenamiento dinámico sin utilizar más de O (1) memoria adicional. (De hecho, todo lo que necesita es memoria adicional suficiente para contener un elemento de la matriz, para fines de intercambio, más un booleano o dos y una variable de bucle o dos).

Ok, en un aspecto técnico puede ser que el montón se explique generalmente como el uso de un montón separado, pero es perfectamente posible implementarlo en el lugar.

Peter Taylor
fuente
3
El único lugar en el que esperaría ver "montón" con un montón separado (en código) es en un lenguaje funcional como Haskell, por la misma razón que el "Quicksort" funcional habitual tampoco está en su lugar: los programadores funcionales como sus listas mucho, y una ordenación in situ tiene estado: cambia el estado de la matriz / lo que sea que contenga los datos. Citas de miedo porque realmente no acepto que un ordenamiento rápido fuera de lugar sea un ordenamiento rápido en absoluto, o que un montón ordenado fuera de lugar sea un montón, al menos no sin decir claramente que no es sitio.
Steve314
1
@ Steve314, creo que he visto material didáctico que dice algo en el sentido de "ponerlo en un montón y luego extraer los elementos uno por uno y ponerlos en una matriz". Pero después de comprobar CLR , puedo informar que muestran una versión in situ.
Peter Taylor
2
@PeterTaylor: Sí, el libro que estaba revisando (Skiena) presentó un montón al construir un montón adicional.
usuario10326
4

Puede estar perdiendo la comprensión fundamental de que una matriz se puede utilizar para especificar el diseño de un árbol.

Suponga que tiene un árbol binario y un nodo interior está en el índice i de la matriz. Luego, el índice de matriz de los padres e hijos de ese nodo se puede encontrar de la siguiente manera:

Parent(i) = floor(i/2)
Left child(i) = 2i
Right child(i) = 2i + 1

Ver:

http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/Sorting/heapSort.htm

Dado que el montón se puede mantener y organizar completamente en una matriz, entonces el montón puede ejecutarse en el lugar moviendo elementos dentro de la matriz de entrada. De hecho, el montón se construye y manipula utilizando la matriz de entrada original.

stackoverflowuser2010
fuente
: Sé acerca de esto. Parece que el problema es que el libro que estoy leyendo presenta un montón de información utilizando un montón separado. No entendí ni pensé que esta presentación fuera para facilitar la comprensión del algoritmo (¿tal vez? ¿No estoy seguro de por qué? presentado así)
user10326
Recomiendo encarecidamente que compre el libro "Introducción a los algoritmos" de Cormen, et al. Responde claramente todas las preguntas relacionadas con algoritmos. Si te tomas en serio una carrera como científico de computadoras o ingeniero de software, entonces necesitas tener este libro.
stackoverflowuser2010
1

Si, como usted dice, uno realmente necesita una estructura adicional para construir el montón, entonces el montón no sería un algoritmo de clasificación in situ.

Sin embargo, éste no es el caso. Puede construir el montón en la misma matriz que desea ordenar, y después de eso aplica el algoritmo de ordenamiento dinámico, por lo que se ordena en el lugar.

Daniel Scocco
fuente
Básicamente, hay un algoritmo "heapify" que se usa para reordenar datos en una matriz para que cumpla con las reglas de un montón en el tiempo IIRC O (n). Consulte el pseudocódigo en programmers.stackexchange.com/questions/116904/… . Después de eso, se trata principalmente de realizar extractos de raíz de montón repetidos y realizar un seguimiento de la cantidad de la matriz que todavía está "montón" y cuánto se ordena el resultado final.
Steve314
0

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. La entrada generalmente se sobrescribe con la salida a medida que se ejecuta el algoritmo. Un algoritmo que no está en el lugar a veces se llama no en el lugar o fuera de lugar.

Wikipedia - Algoritmo en el lugar

Rein Henrichs
fuente
Entonces, ¿por qué mergesort se considera un algoritmo in situ?
user10326
3
Esta no es una respuesta útil. No tiene nada que ver con el montón y no responde la pregunta.
stackoverflowuser2010
Por supuesto que tiene algo que ver con el montón. Heapsort es un algoritmo de ordenación in situ, como debería quedar claro a partir de la definición. De hecho, estaba vinculado desde la página del montón.
Rein Henrichs
0

Se considera en su lugar porque sus requisitos de espacio son insignificantes (constantes o ninguno si está utilizando operaciones bit a bit para intercambiar elementos). MergeSort, por ejemplo, no está en su lugar porque el conjunto de entrada no se modifica en cada iteración del ejemplo de búsqueda.

La mejor manera de ilustrar las diferencias entre los algoritmos en el lugar y los algoritmos fuera del lugar es probablemente mirar el siguiente código de inversión de cadena C / C ++ que lo hace en su lugar (de K&R):

void reverse(char s[])
{
      int c, i, j;

      for (i = 0, j = strlen(s)-1; i < j; i++, j--) {
         c = s[i];
         s[i] = s[j];
         s[j] = c;
      }
}

Si, por ejemplo, estuviera leyendo la cadena de entrada desde el final y colocando los caracteres en otro búfer, sería un algoritmo de inversión de cadena fuera de lugar.

rdasxy
fuente
1
Mergesort es muy molesto: es fácil convencerse erróneamente de que tiene una estrategia en el lugar. Por lo general, solo funciona para matrices pequeñas. Sin embargo, creo que descargué un documento una vez en el que alguien resolvió una variante in situ del algoritmo de clasificación por fusión. Veré si puedo encontrarlo de nuevo.
Steve314