Investigación Método de ordenación HeapSort

[pic 1]

[pic 2]

Portada

Facultad de Informática y Ciencias Aplicadas

Asignatura:

Métodos de Programación II

(Modalidad Virtual)

Catedrático:

Ingeniero Orlando Girón

Sección:

01

Tema:

Investigación Método de ordenación HeapSort

            Alumno:                                              Carné:

Fecha máxima de Entrega:

14 de octubre de 2018

INDICE

INTRODUCCIÓN        3

OBJETIVO GENERAL        3

I.        MARCO TEORICO        3

1.1 Descripción General de HeapSort        3

1.2 Definición algoritmo HeapSort        3

1.3 Ventajas y Desventajas        5

II.        FUNCIONAMIENTO        5

2.1 Funcionamiento algoritmo HeapSort        5

2.2 Aplicaciones        5

2.3 Ejemplo en JAVA        6

2.4 Comparaciones        7

III.        CONCLUSIONES        8

BIBLIOGRAFÍA        8

INTRODUCCIÓN

El HeapSort también llamado algoritmo de ordenamiento es una operación para ordenar una lista, mediante el arreglo de elementos a través de un criterio.

De tratarse números el criterio de orden podría ser “<”, es decir un ordenamiento de menor a mayor, aunque un ser humano es capaz de implementar una metodología propia para ordenar un conjunto de elementos, esta tarea se vuelve extremadamente complicada cuando el número de elementos es grande, puesto que se necesita mayor esfuerzo, tiempo y podría existir errores.

En este trabajo de investigación definiremos que es un HeapSort, aplicación y usos, ventajas y desventajas, algunos ejemplos y comparación con otros algoritmos de ordenamiento.

OBJETIVO GENERAL

Investigar el algoritmo de ordenamiento HeapSort, con el fin de obtener el conocimiento y la competencia para su aplicación.

1. MARCO TEORICO

1.1 Descripción General de HeapSort

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 como se defina contendrá el mayor o menor elemento del montículo. (Gomez, 2016)

1.2 Definición algoritmo HeapSort

¿Qué es el HeapSort?

Es un método de ordenamiento basado con comparación. Usa el montículo (Heap) como estructura de datos, el cual representa un árbol. Mas lento que otros métodos, pero más eficaz en escenarios más rigurosos. Se defino como No Recursivo y No Estable. (Ibañez, 2014)        

El acceso a los elementos del Heap (montículo) en un arreglo se hace a través de operaciones aritméticas:

[pic 3]

Hijo izquierdo

Hijo Derecho

Padre

Es importante comprender en este algoritmo, la inserción y eliminación de los elementos, así mismo es indispensable conocer la estructura de este algoritmo la cual se define como la estructura basada en un árbol, donde cada nodo padre es mayor a sus nodos hijos y además toda la estructura esta balanceada.

Existen los montículos máximos y los montículos mínimos

Los hijos son mayores que el padre[pic 4][pic 5][pic 6]

1.3 Ventajas y Desventajas

1. FUNCIONAMIENTO

2.1 Funcionamiento algoritmo 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 estos 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 por el de menor valor
5. Tras el paso anterior la raíz vuelve a ser el mayor del montículo
6. Se repite el paso b hasta que quede el arreglo ordenado

(Gomez, 2016)

2.2 Aplicaciones

Una de las aplicaciones es la programación de intervalos, en donde se tiene una lista de tareas con un tiempo de inicio y in y deseamos hacer tantas tareas como sean posibles en un periodo de tiempo limitado.

En fin para toda aquella aplicación o algoritmos que trate de ordenar una lista de elementos, este método puede proveer ese fin.

2.3 Ejemplo en JAVA

public class heap_Sort
{
      public static void main(String a[])
      {
            int i;
            int arr[] = {1,3,4,5,2};
            System.out.println("Heap Sort");   
            System.out.println("\n---------------\n");
            System.out.println("\nUnsorted array\n\n");                        
            for (i = 0; i < arr.length; i++)
                  System.out.print(" "+arr[i]);
            for(i=arr.length; i>1; i--)
            {
                  fnSortHeap(arr, i - 1);
            }
            System.out.println("Sorted array");
            System.out.println("\n---------------\n");
            for (i = 0; i < arr.length; i++)
            {
                  System.out.print(" "+arr[i]);
            }
            public void fnSortHeap(int arr[], int arr2)
            {
                  int i, o;
                  int lCh, rCh, mCh, root, tmp;
                  root = (arr2-1)/2;

                  for(o = root; o >= 0; o--)
                  {
                        for(i=root;i>=0;i--)
                        {
                              lCh = (2*i)+1;
                              rCh = (2*i)+2;
                              if((lCh <= arr2) && (rCh <= arr2))
                              {
                                    if(arr[rCh] >= arr[lCh])
                                    {
                                          mCh = rCh;
                                    }
                                    else
                                    {
                                          mCh = lCh;
                                    }
                              }
                              else
                              {
                                    if(rCh > arr2)
                                    {
                                          mCh = lCh;
                                    }
                                    else
                                    {
                                          mCh = rCh;
                                    }
                              }

                              if(arr[i] < arr[mCh])
                              {
                                    tmp = arr[i];
                                    arr[i] = arr[mCh];
                                    arr[mCh] = tmp;
                              }
                        }
                  }
                  tmp = arr[0];
                  arr[0] = arr[arr2];
                  arr[arr2] = tmp;
                  return;
            }
      }
}

...