• Author / Uploaded
• Diego Sandoval

Citation preview

Métodos de Ordenamiento: Heapsort Métodos de Ordenamiento Los métodos de ordenamiento son ampliamente usados en el desarrollo de software, debido a que posibilitan tomar un grupo de datos (ya sean numéricos o alfabéticos) y ordenarlos de manera secuencial dentro de un tipo de datos de agrupación o arreglo, entro otros.

Heapsort El ordenamiento por montículos (heapsort en inglés) es un algoritmo de ordenamiento no recursivo, no estable, con complejidad computacional Este algoritmo consiste en almacenar todos los elementos del vector a ordenar en un montículo (heap), y luego extraer el nodo que queda como nodo raíz del montículo (cima) en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de los montículos, por la cual, la cima contiene siempre el menor elemento (o el mayor, según se haya definido el montículo) de todos los almacenados en él. El algoritmo, después de cada extracción, recoloca en el nodo raíz o cima, la última hoja por la derecha del último nivel. Lo cual destruye la propiedad heap del árbol. Pero, a continuación, realiza un proceso de "descenso" del número insertado de forma que se elige a cada movimiento el mayor de sus dos hijos, con el que se intercambia. Este intercambio, realizado sucesivamente "hunde" el nodo en el árbol restaurando la propiedad montículo del árbol y dejando paso a la siguiente extracción del nodo raíz. El algoritmo, en su implementación habitual, tiene dos fases. Primero una fase de construcción de un montículo a partir del conjunto de elementos de entrada, y después, una fase de extracción sucesiva de la cima del montículo. La implementación del almacén de datos en el heap, pese a ser conceptualmente un árbol, puede realizarse en un vector de forma fácil. Cada nodo tiene dos hijos y, por tanto, un nodo situado en la posición i del vector, tendrá a sus hijos en las posiciones 2 x i, y 2 x i +1 suponiendo que el primer elemento del vector tiene un índice = 1. Es decir, la cima ocupa la posición inicial del vector y sus dos hijos la posición segunda y tercera, y así, sucesivamente. Por tanto, en la fase de ordenación, el intercambio ocurre entre el primer elemento del vector (la raíz o cima del árbol, que es el mayor elemento del mismo) y el último elemento del vector que es la hoja más a la derecha en el último nivel. El árbol pierde una hoja y por tanto reduce su tamaño en un elemento. El vector definitivo y ordenado, empieza a construirse por el final y termina por el principio

DESCRIPCIÓN DEL MÉTODO DE HEAP SORT

ORIGEN Fue publicado originalmente por J.W.J. Williams llamándolo “Algorithm 232” en la revista “Communications of the ACM” en 1964

DESCRIPCIÓN GENERAL Este algoritmo consiste en ordenar en un árbol y luego extraer del nodo que queda como raíz en sucesivas iteraciones obteniendo el conjunto ordenado. Basa su funcionamiento en una propiedad de montículos, por la cual la cima siempre dependiendo de cómo se defina contendrá el mayor o menor elemento de montículo

VENTAJAS Y DESVENTAJAS Es usar este método de Ordenamiento trae consigo diversas ventajas y desventajas con respecto a los otros métodos, dichas características están en la tabla a continuación:

VENTAJAS   

Funciona efectivamente con datos desordenados. Su desempeño es en promedio tan bueno como el Quicksort No utiliza memoria adicional

DESVENTAJAS

 

No es estable, ya que se comporta de manera ineficaz con datos del mismo Este método es mucho más complejo que los demás

FUNCIONAMIENTO DEL MÉTODO HEAPSORT Este algoritmo consiste en almacenar todos los elementos en un montículo y luego extraer el nodo que queda como raíz en iteraciones sucesivas obteniendo el conjunto ordenado

Para esto el método realiza los siguientes pasos 1. Se construye el Heap/montículo a partir del arreglo original 2. La raíz se coloca en el arreglo 3. El último elemento del montículo se vuelve la raíz 4. La nueva raíz se intercambia con el elemento de mayor valor 5. Tras el paso anterior la raíz vuelve a ser el mayor del montículo 6. Se repite el paso 2 hasta que quede el arreglo ordenado

Algoritmo Se construye el montículo inicial a partir del arreglo original. Se intercambia la raíz con el último elemento del montículo. El último elemento queda ordenado. El último elemento se saca del montículo, no del arreglo. Se restaura el montículo haciendo que el primer elemento baje a la posición que le corresponde, si sus hijos son menores. 6. La raíz vuelve a ser el mayor del montículo. 7. Se repite el paso 2 hasta que quede un solo elemento en el montículo.

1. 2. 3. 4. 5.

RECOMENDACIONES   

Utilizar de manera correcta el algoritmo de búsqueda. Es recomendable aplicar este método cuando exista poca cantidad de elementos a ordenar. En un método recomendable para elementos aleatorios ya que es uno de los mas rápidos para N elementos.

Conclusión Este método es conveniente cuando se trata de ordenar arreglos estáticos grandes a diferencia de otros métodos con el Quicksort y el Mergesort. Heapsort compite primariamente con Quicksort, otro método de ordenamiento muy eficiente para propósitos en general.

Ejm: