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?
fuente
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:
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.
fuente
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.
fuente
Wikipedia - Algoritmo en el lugar
fuente
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):
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.
fuente