Derecho empleo

Algoritmo Heapsort

Definición

Un montículo es un árbol binario que cumple las siguientes condiciones:Es un árbol binario completo.Cada nodo es menor que todos sus descendientes.

Observación

El mínimo está en la raíz.

Observación

Si un montículo tiene altura  puede tener como mucho . Y como poco .

Observación

No necesitamos punteros.Si ordenamos los nodos en un vector como en el dibujo  pero dejando vacía la posición 0 podemos localizar al hijo izquierdo del nodo en la posición  buscando en la posición  del vector y el hijo derecho estará en la .

Insertar

Ponemos el nodo en la última posición posible, es decir, en el primer hueco que tenga del último nivel. Si quisiéramos insertar en nuestro ejemplopondríamos el nodo a insertar como hijo izquierdo de 20. Después comprobaríamos si  valor del nodo. Si lo es los cambiamos y comparamos el nodo con su nuevo padre etc. Si no lo es lo dejamos como está.

Ejercicio

: Señalar detalladamente la evolución de los siguientes árboles binarios construidos por el método de Heapsort durante la ordenación de la lista siguiente . Construyamos el montículo.Ya tenemos el montículo pero no la ordenación.Vamos a definir otra función:

Borrar Mínimo

Es lo mismo que borrar la raíz porque ésta es el mínimo. Tengo que recolocar el nodo que tengo más a la derecha en el último nivel. Tendría que recolocar el 7. Quiero borrar el 1. Muevo el hueco y mientras no pueda poner el nodo que tengo que recolocar (el 7) en el hueco, lo intercambio con el menor de sus hijos.Como ya no puedo bajar más he de poner el ahí. El resultado es:Así:

El algoritmo de Heapsort consta de dos pasos:Construir el montículo.Aplicamos borrar min hasta que borremos el montículo entero. Los elementos que vamos borrando están ordenados ergo los vamos imprimiendo.

Construir montículos

Podemos realizar la operación de insertar  veces seguidas o podemos realizar la siguiente operación:Construir un árbol binarioFor (i=N/2; i > 0; i --) Recolocar nodo i intercambiándolo con el menor de sus hijos.

Ejercicio

:Dado un árbol binario completo con  nodos ¿Cuántos nodos habrá que recolocar como máximo para convertirlo en un montículo?7.

Ejercicio

: Obtener el orden de la lista  por el método heapsort.Hay que recolocar los  primeros. El  el  el  y el .

Algoritmo de Mergesort

Divide la lista en dos mitades recursivamente. Hasta llegar a listas de tamaño 1 (que están ordenadas). Para combinar lo hacemos de la siguiente manera:Llamamos lista I a una de ellas y lista D a la otra. Un índice i recorrerá la lista I y un índice j recorrerá la lista D. Comparo I[i] con D[j]. Si I[i] es menor lo meto en una nueva lista R (resultado) y si D[j] es menor lo meto. Cuando acabo una lista añado lo que queda de la otra en R. Como están ordenados los añado. Sigo recursivamente hasta obtener la lista R de longitud inicial.Algoritmo Quicksort:Elegimos un pivote y ponemos a la izquierda todos los elementos menores que ese y a la derecha todos los mayores. Repetimos ese proceso de manera iterativa. ¿Cómo elegimos el pivote? Podríamos coger el elemento central o el primero o un número al azar pero no son buenas eleccionesSea V el vector que queremos ordenar y sean p y r las posiciones que hay que ordenar. Por ejemplo para la lista  deberíamos hacer Quicksort( ).Quicksort(V,p,r)Si (p){q>Ejemplo
:Sea la lista Supongamos que elegimos el punto medio: El pivote será . Podríamos utilizar otro método para calcularlo.En nuestro ejemplo pivote .Vamos a incrementar el índice  hasta encontrar un elemento mayor o igual que el pivote. Nos pararíamos en el , es decir, para .Vamos a descender el índice  desde el final hasta encontrar un elemento menor o igual que el pivote. Nos pararíamos en el , es decir, .Intercambiamos  por . Obtenemos . Los índices  y  siguen en la misma posición y siguen avanzando hasta encontrar dos nuevos elementos, uno menor que el pivote y uno mayor que el pivote. En nuestro ejemplo la  empezaría desde el  (porque es donde estaba) y se para en  porque encuentra el . La  estaba en  y baja hasta  porque encuentra el . Los intercambiamos. . Seguimos hacíendolo hasta que . (puede que se crucen).Llegamos finalmente a .AlgbusquedaLos algoritmos de búsqueda buscan un elemento (que llamaremos clave)
En una lista de elementos.

Búsqueda lineal

Es el algoritmo más básico. Compara cada elemento de la lista con la clave hasta que lo encuentra. Después devuelve su posición.

Código

Int buscar(int x,int A[]){For (i=0,i;i++){if> elementos de una lista hemos de hacer como máximo  comparaciones. Veamos otros algoritmos más eficientes.

Búsqueda binaria

La condición que le vamos a pedir a la lista es que esté ordenada. Es un algoritmo de divide y vencerás. Elegimos el punto medio. Si el elemento a buscar es el punto medio devolvemos su posición. Si es menor elegimos la lista de la izquierda y repetimos el proceso. Si es mayor elegimos la lista de la derecha y repetimos.