Introducción Método Radix

Unidad 7

Bien, ya estudiamos en nuestras sesiones pasadas los métodos de ordenamiento interno. Ahora comenzaremos a analizar algunos de los métodos de ordenamiento externo.

Comenzando con el método de ordenamiento Radix. En esta entrada de nuestro blog, hablaremos un poco de el para que te des una idea de lo que trata.

Iniciemos entonces con un poco de los antecedentes históricos del mismo:

Se dice que este método nació de la idea de Herman Hollerith en 1890 al crear la máquina tabuladora, en la cual se empleaban tarjetas perforadas para realizar el censo de ese año en Estados Unidos.

Al final, después de unas horas, la maquina entregaba todo un grupo de hojas listas para ser procesadas en un computador.

En el censo de 1880 se tomaron 10 años para procesar toda la información, pero con las tarjetas perforadas, en la máquina que incluía un “card sorter” se tomaron cerca de 6 semanas.

La idea original de Hollerith era ordenar empezando por el digito más significativo.

Es de esta forma que surgio una maquina ordenadora de tarjetas. La cual, utilizando el método de Radix-Sort, concatenaba cada hoja dependiendo de la ubicación de las ultimas 3 columnas, que contenían las cifras para el acomodo de tarjetas, estando numerado del 0 al 9.

A este método también se le conoce como “ordenamiento de raíz”. Es un algoritmo de ordenamiento estable que puede ser usado para ordenar items identificados por llaves (o claves) únicas. Cada llave debe ser una cadena o un número capaz de ser ordenada alfanuméricamente.

Reglas para ordenar:

Empezar en el dígito más significativo y avanzar por los dígitos menos significativos mientras coinciden los dígitos correspondientes en los dos números. El número con el dígito más grande en la primera posición en la cual los dígitos de los dos números no coinciden es el mayor de los dos (por supuesto sí coinciden todos los dígitos de ambos números, son iguales). Este mismo principio se toma para Radix Sort.

A grandes rasgos este es el método Radix, en nuestra siguiente sesión analizaremos dicho método un poco más a fondo. Te comparto el siguiente video, para que dicho método te quede un poco más claro.

https://www.youtube.com/watch?v=nE2RVqC2mWQ

Bibliografía

IDHERR99. (08 de 10 de 2012). Youtube.com. Obtenido de https://www.youtube.com/watch?v=nE2RVqC2mWQ

Introducción QuickSort

Unidad 6

Una vez más, como en sesiones anteriores. En esta ocasión hablaremos un poco sobre otro método de ordenamiento de datos. Esta vez, estamos hablando quizá del método más efectivo para el ordenamiento de los mismos, el QuickSort.

Para comprenderlo mejor, les comparto el siguiente artículo:

“Quicksort es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar n elementos en un tiempo proporcional a n log n.

Quicksort es actualmente el más eficiente y veloz de los métodos de ordenación interna. Este método fue creado por el científico británico Charles Antony Richard Hoare, tambien conocido como Tony Hoare en 1960, su algoritmo Quicksort es el algoritmo de ordenamiento más ampliamente utilizado en el mundo.

Antecedentes

Este algoritmo nace como una necesidad para reunir datos estadísticos. 1945- Zuse desarrolla un programa de clasificación por inserción directa.

1946- John Mauchly mayor velocidad en procesos de clasificación. Demostró que a clasificación es útil con los cálculos numéricos.

A partir de aquí se desarrollan los algoritmos de clasificación binaria y por inserción directa.

1960 – Sir Charles Antony Richard Hoare, Tony Hoare o CAR Hoare, nacido 11 de enero 1934 es un científico informático británico, probablemente el más conocido para el desarrollo en 1960 de Quicksort (o Hoaresort),uno de los más utilizados algoritmos de ordenación del mundo.

El Algoritmo consiste en:

Elegir un elemento de la lista de elementos a ordenar, al que llamaremos pivote.

Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores.

Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.

La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.

Repetir este proceso de forma recursiva para cada sublista mientras éstas contengan más de un elemento.

Una vez terminado este proceso todos los elementos estarán ordenados”.

A grandes rasgos en esto consiste el método QuickSort, les comparto también el siguiente video para dejar un poco más claro el método.

https://www.youtube.com/watch?v=mRhy4wTlg0s

Bibliografía

Cardiel Salas Haran Jesus, V. V. (s.f.). Método QuickSort. Recuperado el 29 de 09 de 2014, de http://metodoquicksort.blogspot.mx/

Sierra, J. P. (08 de 02 de 2013). Youtube.com. Obtenido de https://www.youtube.com/watch?v=mRhy4wTlg0s

Métodos de ordenamiento MergeSort

Unidad 6

Venimos estudiando en sesiones pasadas, diversos métodos de ordenamiento como son, el método de la burbuja, shellsort, etc. En nuestra siguiente sesión analizaremos un nuevo método más, el cual es llamada MergeSort.

Pero antes, en esta entrada de nuestro blog. Te compartiré el siguiente artículo donde se habla y ejemplifica un poco dicho método.

“El algoritmo de ordenación por combinación o Merge Sort, basado en la técnica Divide y Vencerás, ordena recursivamente un conjunto de elementos dividiéndolo en dos, ordenando cada una de estas partes en forma independiente y combinando los dos resultados.

Este código en el lenguaje de programación JAVA 1.6 recibe como entrada un arreglo de números enteros denominado v, lo parte utilizando el método copyOfRange de la clase java.util.Arrays, se llama recursivamente con cada una de las dos partes como argumento y, una vez terminada la ordenación de dichas partes, invoca al proceso de combinación de las dos respuestas implementado en el método combinar, el cual recibe como entrada el arreglo original y las dos mitades del mismo previamente ordenadas que serán combinadas en el arreglo original.

// Algoritmo de ordenacion por combinacion: Merge Sort

public static void ordenacionCombinacion(int[] v) {

final int N = v.length;

if(N<=1) return;

int mitad=N/2;

int[] izq = Arrays.copyOfRange(v, 0, mitad);

int[] der = Arrays.copyOfRange(v, mitad, N);

ordenacionCombinacion(izq);

ordenacionCombinacion(der);

combinar(v, izq, der);

}

public static void combinar(int[] resp, int[] izq, int[] der) {

int i = 0;

int j = 0;

for(int k=0; k<resp.length;k++) {

if(i>=izq.length) { resp[k]=der[j++]; continue; }

if(j>=der.length) { resp[k]=izq[i++]; continue; }

resp[k]=(izq[i]<der[j])?izq[i++]:der[j++];

}

Este algoritmo tiene complejidad O(n log n), que se obtiene resolviendo la ecuación de recurrencias T(n) = k n + 2 T(n/2)”.

Esta es una pequeña introducción de lo que viene siendo el método MergeSort. No te preocupes si no lo comprendes del todo. En nuestra siguiente sesión, estudiaremos más a fondo dicho método.

Bibliografía

A, J. E. (28 de 09 de 2010). Apuntes de Algoritmos y Programación. Obtenido de http://jorgep.blogspot.mx/2010/09/ordenacion-por-combinacion.html

Métodos de ordenamiento Shellsort

Unidad 6

En nuestra sesión anterior estudiamos el método de ordenamiento de la burbuja, el cual suele ser muy útil pero solo cuando la cantidad de elementos a ordenar no son demasiados. Cuando el número es considerable, es mejor utilizar otros métodos como el Shellsort, del cual hablaremos un poco en esta entrada de nuestro blog.

El método Shellsort, es una mejora del método de inserción directa que se utiliza cuando el número de elementos a ordenar es grande. El método se denomina “shell” –en honor de su inventor Donald shell – y también método de inserción con incrementos decrecientes.

En el método de clasificación por inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es más pequeño – por ejemplo -, hay que ejecutar muchas comparaciones antes de colocarlo en su lugar definitivamente. Shell modifico los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con eso se conseguía la clasificación más rápida. El método se basa en fijar el tamaño de los saltos constantes, pero de más de una posición.

Supongamos un vector de elementos

4 12 16 24 36 3

En el método de inserción directa, los saltos se hacen de una posición en una posición y se necesitaran cinco comparaciones. En el método de Shell, si los saltos son de dos posiciones, se realizaran comparaciones.

4 12 16 24 36 3

El método se basa en tomar como salto N/2 (siendo N el número de elementos) y luego reduciendo a la mitad en cada repetición hasta que el salto o distancia vale 1

Considerando la variable salto, se tendría para el caso de un determinado vector X los siguientes recorridos:

Vector X [X[1], X[3], …,X[N]]

Vector X1 [X[1], X[1] + salto, X[2], …]

Vector XN [salto1, salto2, salto3, …]

EJEMPLO :

Deducir las secuencias parciales de clasificación por el método de Shell para ordenar en ascendente la lista o vector.

6, 1, 5, 2, 3, 4, 0

RECORRIDO SALTO LISTA REORDENADA INTERCAMBIO

1 3 2,1,4,5,0,3,5,6 (6,2), (5,4), (6,0)

2 3 0,1,4,2,3,5,6 (2,0)

3 3 0,1,4,2,3,5,6 NINGUNO

4 1 0,1,2,3,4,5,6 (4,2),(4,3)

5 1 0,1,2,3,4,5,6 NINGUNO

Bien esta fue una pequeña introducción a lo que es el método de Shellsort, en nuestra siguiente sesión. Estudiaremos más a fondo dicho método.

Métodos de Ordenamiento

Unidad 6

A lo largo de nuestras sesiones, hemos estudiado diversas estructuras para el manejo de datos. Pero en ocasiones de acuerdo a nuestras actividades, es necesario tener algunos métodos para ordenar nuestros datos.

Es así como surgen algunos métodos de ordenamiento, de los cuales hablaremos un poco al respecto en esta entrada de nuestro blog.

Los algoritmos de ordenamiento nos permiten, como su nombre lo dice, ordenar. Por ejemplo, nos sirven para ordenar vectores o matrices con valores asignados aleatoriamente. En esta entrada hablaremos un poco de los más utilizados.

Para poder ordenar una cantidad determinada de números almacenadas en un vector o matriz, existen distintos métodos (algoritmos) con distintas características y complejidad.

Existe desde el método más simple, como el Bubblesort (o Método Burbuja), que son simples iteraciones, hasta el Quicksort (Método Rápido), que al estar optimizado usando recursión, su tiempo de ejecución es menor y es más efectivo.

Se pueden dividir en 2, métodos iterativos y métodos recursivos.

Métodos iterativos:

Estos métodos son simples de entender y de programar ya que son iterativos, simples ciclos y sentencias que hacen que el vector pueda ser ordenado.

Dentro de los Algoritmos iterativos encontramos:

– Burbuja

– Inserción

– Selección

– Shellsort

Métodos recursivos:

Estos métodos son aún más complejos, requieren de mayor atención y conocimiento para ser entendidos. Son rápidos y efectivos, utilizan generalmente la técnica Divide y vencerás, que consiste en dividir un problema grande en varios pequeños para que sea más fácil resolverlos. Mediante llamadas recursivas a sí mismos, es posible que el tiempo de ejecución y de ordenación sea más óptimo.

Dentro de los algoritmos recursivos encontramos:

– Ordenamiento por Mezclas (merge)

– Ordenamiento Rápido (quick)

Estos son solo por mencionar algunos métodos, pero existen muchos más. En nuestra siguiente sesión, veremos lo referente al método de la burbuja.

Árboles Binarios de Búsqueda

Unidad 5

Bien, ya estudiamos lo que es un árbol, un árbol binario. Ahora hablaremos un poco de lo que son los árboles binarios de búsqueda.

Para ello, recordemos un poco lo que son los árboles binarios.

Árbol binario: árbol ordenado de grado 2, que puede estar vacío o puede estar formado por un nodo raíz del que cuelgan dos subárboles binarios disjuntos, denominados subárbol izquierdo y subárbol derecho.

Un árbol binario se dice relleno si todos sus nodos o bien tienen dos hijos o bien son hojas, es decir, si no contiene nodos con un solo hijo.

El número de hojas en un árbol binario relleno es siempre igual al número de nodos internos más uno.

La aplicación más importante de los árboles es organizar la información de manera jerárquica para acelerar los procesos de búsqueda, inserción y borrado.

Normalmente, la clave de búsqueda se extrae de la propia información, directamente o mediante transformaciones adecuadas.

Para clasificar la información sin ambigüedad, es necesario establecer entre las claves de búsqueda un conjunto de condiciones mutuamente excluyentes, tal que una y sólo una de ellas sea cierta.

Así pues, un árbol binario de búsqueda (ABB) es un árbol binario en el que para cada nodo se definen dos condiciones mutuamente excluyentes, de forma que las claves de los nodos del subárbol izquierdo cumplen una de ellas, y las del subárbol derecho la otra.

Habitualmente estas condiciones determinan una relación de orden, de manera que el recorrido en orden simétrico del árbol produce una secuencia ordenada de nodos.

Un cierto conjunto de datos puede representarse mediante distintos ABB. El recorrido simétrico de estos ABB producirá la misma secuencia de nodos.

Sin embargo, tendrán diferentes alturas y por tanto el coste promedio de búsqueda será distinto. Suponiendo datos equiprobables, serán óptimos aquellos ABB cuya altura sea mínima. De ahí el interés de los ABB equilibrados.

Bien con esta pequeña introducción, nos damos una idea de lo que es un árbol binario de búsqueda. En nuestra siguiente sesión lo veremos un poco más a detalle y estudiaremos también la manera de implementarlo.

Árboles Binarios

Unidad 5

En nuestra entrada anterior tuvimos una pequeña introducción de lo que fueron los árboles, en esta ocasión hablaremos un poco de lo que son los árboles binarios.

Para comprender un poco al respecto, te comparto el siguiente artículo:

“Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3″, eso significa que tenemos un grafo donde cada nodo puede tener máximo 2 hijos ( o hojas ) y estas hojas no pueden tener como hijos a cualquier otra hoja anterior como podemos ver en la siguiente imagen:

Podemos ver en la imagen como “Raíz” es padre de “Hoja 1″ y “Hoja 2″ y estas a su vez también son la raíz de las “Sub hojas” y se vuelve un proceso recursivo hasta n cantidad de hojas.

¿Para qué sirve un árbol binario?

Como todos sabemos un árbol binario es una estructura de datos, y como todas, este sirve para organizar datos para facilitar su manipulación, ya sea el ingreso, borrado o búsqueda de datos, y precisamente una de las principales ventajas de los árboles binarios es la búsqueda, ya que como en muchos algoritmos de búsqueda necesitamos tener la información ordenada y en nuestros árboles binarios precisamente los datos van ingresando de forma ordenada.

Recorridos con los conocidos métodos recursivos:

Inorden

Postorden

Preorden”

A grandes rasgos esto es lo que llamamos un árbol binario, pudimos observar que contiene algunos métodos para recorrerlo. En nuestra siguiente sesión, veremos un poco más a fondo lo que es un árbol binario, sus recorridos y como implementarlo.

Bibliografía

PROGRAMADOR.ES, ©. C. (09 de 10 de 2012). Ser programadores. Obtenido de http://serprogramador.es/programar-arboles-binarios-parte-1-introduccionclasesagregar-nodo/

Arboles

Unidad 5

Hemos venido estudiando diferentes tipos de estructuras de datos, como son las pilas, colas, etc. Pero todos estos tipos de estructuras, son estructuras de datos lineales. Comenzaremos ahora estudiar otro tipo de estructuras de datos, un poco mas complejas. Este tipo de estructuras, son los árboles.

Para entender un poco al respecto de lo que son los árboles, les compartiré el siguiente artículo:

“Definición de árbol

Un árbol es una estructura de datos, que puede definirse de forma recursiva como:

– Una estructura vacía o

– Un elemento o clave de información (nodo) más un número finito de estructuras tipo árbol, disjuntos, llamados subárboles. Si dicho número de estructuras es inferior o igual a 2, se tiene un árbol binario.

Es, por tanto, una estructura no secuencial.

Otra definición nos da el árbol como un tipo de grafo: un árbol es un grafo acíclico, conexo y no dirigido. Es decir, es un grafo no dirigido en el que existe exactamente un camino entre todo par de nodos. Esta definición permite implementar un árbol y sus operaciones empleando las representaciones que se utilizan para los grafos. Sin embargo, en esta sección no se tratará esta implementación.

Formas de representación

– Mediante un grafo:

– Mediante un diagrama encolumnado:

En la computación se utiliza mucho una estructura de datos, que son los árboles binarios. Estos árboles tienen 0, 1 ó 2 descendientes como máximo. El árbol de la figura anterior es un ejemplo válido de árbol binario.

Nomenclatura sobre árboles

– Raíz: es aquel elemento que no tiene antecesor; ejemplo: a.

– Rama: arista entre dos nodos.

– Antecesor: un nodo X es antecesor de un nodo Y si por alguna de las ramas de X se puede llegar a Y.

– Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y se puede llegar a X.

– Grado de un nodo: el número de descendientes directos que tiene. Ejemplo: c tiene grado 2, d tiene grado 0, a tiene grado 2.

– Hoja: nodo que no tiene descendientes: grado 0. Ejemplo: d

– Nodo interno: aquel que tiene al menos un descendiente.

– Nivel: número de ramas que hay que recorrer para llegar de la raíz a un nodo. Ejemplo: el nivel del nodo a es 1 (es un convenio), el nivel del nodo e es 3.

– Altura: el nivel más alto del árbol. En el ejemplo de la figura 1 la altura es 3.

– Anchura: es el mayor valor del número de nodos que hay en un nivel. En la figura, la anchura es 3.

Aclaraciones: se ha denominado a a la raíz, pero se puede observar según la figura que cualquier nodo podría ser considerado raíz, basta con girar el árbol. Podría determinarse por ejemplo que b fuera la raíz, y a y d los sucesores inmediatos de la raíz b. Sin embargo, en las implementaciones sobre un computador que se realizan a continuación es necesaria una jerarquía, es decir, que haya una única raíz”.

Bien, con este pequeño artículo. Podemos darnos una idea de lo que es un árbol. En nuestra siguiente sesión, estudiaremos lo que es un árbol un poco más a detalle.

Bibliografía

Ejemplo de Recursividad

Unidad 4

Nuestra entrada anterior, vimos una pequeña introducción de lo que era la recursividad. En la entrada de hoy veremos un pequeño código de un ejemplo que ilustra un poco como aplicar dicha recursividad.

Problema:

Imprimir los números de 1 a 5 en pantalla utilizando recursividad.

Programa:

public class Recursividad {

void imprimir(int x) {

if (x>0) {

imprimir(x-1);

System.out.println(x);

}

public static void main(String[] ar) {

Recursividad re=new Recursividad(); re.imprimir(5);

}

Con este ejemplo se presenta una situación donde debe analizarse línea a línea la ejecución del programa y el porqué de estos resultados.

¿Por qué se imprime en pantalla 1 2 3 4 5?

Veamos cómo se apilan las llamadas recursivas:

En la primera llamada desde la función main el parámetro x recibe el valor 5.

Cuando llamamos desde la misma función le enviamos el valor de x menos 1 y la memoria queda de la siguiente forma:

Debemos entender que el parámetro x en la nueva llamada está en otra parte de la memoria y que almacena un 4, nosotros le llamaremos x prima.

Comienza a ejecutarse la función, la condición del if se valúa como verdadero por lo que entra al bloque y llama recursivamente a la función imprimir pasándole el valor 3 al parámetro.

Nuevamente la condición se valúa como verdadero y llama a la función enviándole un 2, lo mismo ocurre cuando le envía un 1 y un 0.

void imprimir(int x) {

if (x>0) {

imprimir(x-1);

System.out.println(x);

}

Cuando x vale 0 la condición del if se valúa como falsa y sale de la función imprimir.

¿Qué línea ahora se ejecuta?

Vuelve a la función main? NO.

Recordemos que la última llamada de la función imprimir se había hecho desde la misma función imprimir por lo que vuelve a la línea:

System.out.println(x);

Ahora si analicemos qué valor tiene el parámetro x. Observemos la pila de llamadas del gráfico:

x cuarta tiene el valor 1. Por lo que se imprime dicho valor en pantalla.

Luego de imprimir el 1 finaliza la ejecución de la función, se libera el espacio ocupado por el parámetro x y pasa a ejecutarse la siguiente línea donde se había llamado la función:

System.out.println(x);

Ahora x en esta instancia de la función tiene el valor 2.

Así sucesivamente hasta liberar todas las llamadas recursivas.

Es importante tener en cuenta que siempre en una función recursiva debe haber un if para finalizar la recursividad (en caso contrario la función recursiva será infinita y provocará que el programa se bloquee).

Bien, este fue un pequeño ejemplo de cómo utilizar la recursividad para la solución de problemas. Espero con esto haya quedado un poco más claro. La siguiente sesión, realizaremos más ejercicios al respecto.

Recursividad

Unidad 4

Cuando utilizamos estructuras de datos, en ocasiones es necesario utilizar algunas técnicas de programación para el manejo de los datos. Una de estas técnicas es el uso de la recursividad.

Esta técnica de programación nos permite que un bloque de instrucciones se ejecute n veces. Remplaza en ocasiones a estructuras repetitivas.

Este concepto será de gran utilidad por ejemplo, para el manejo de la estructura de datos tipo árbol.

La recursividad es un concepto difícil de entender en principio, pero luego de analizar diferentes problemas aparecen puntos comunes.

En Java los métodos pueden llamarse a sí mismos. Si dentro de un método existe la llamada a sí mismo decimos que el método es recursivo.

Cuando un método se llama a sí mismo, se asigna espacio en la pila para las nuevas variables locales y parámetros.

Al volver de una llamada recursiva, se recuperan de la pila las variables locales y los parámetros antiguos y la ejecución se reanuda en el punto de la llamada al método.

Ejemplo:

public class Recursividad {

void repetir() {

repetir();

}

public static void main(String[] ar) {

Recursividad re=new Recursividad();

re.repetir();

}

La función repetir es recursiva porque dentro de la función se llama a sí misma.

Cuando ejecuta este programa se bloqueará y generará una excepción: «Exception in thread «main» java.lang.StackOverflowError»

Analicemos como funciona:

Primero se ejecuta la función main, luego de crear un objeto llamamos a la función repetir.

Hay que tener en cuenta que cada vez que se llama a una función se reservan 4 bytes de la memoria que se liberarán cuando finalice su ejecución.

La primera línea de la función llama a la función repetir, es decir que se reservan 4 bytes nuevamente. Se ejecuta nuevamente una instancia de la función repetir y así sucesivamente hasta que la pila estática se colme y se cuelgue el programa.

Bien, espero que con esta pequeña introducción te des una idea de lo que es la recursividad. El ejemplo que analizamos anteriormente, es un ejemplo de cómo NO debe utilizarse la recursividad. En nuestra siguiente sesión abordaremos este tema un poco más a detalle y realizaremos algunos ejercicios más. Para dejar un poco más claro lo que es este concepto.