domingo, 18 de abril de 2010

Algoritmo de ordenamientos recursivos

Bueno este fue un tema que quise dejar despues de la explicación de ordenamientos y de recursividad por que es una mezcla de los dos, es un algoritmo de ordenamiento recursivo.

Este tema se ve muy interesante, espero que en la practica sea de mucho agrado para todos ya que puede llegar a ser una gran fuente de ayuda.

El dia de hoy trataremos 2 de estos algoritmos:
  • Quicsort
  • Mergesort
Quicsort

Este algoritmo actualemente es el mas eficiente y veloz, su funcionamiento es de la siguiente manera:
  • tomamos un valor 'a' del arreglo.
  • buscamos la posición correcta del dato de tal forma que todos los que se encuentran a su izquierda seas menores o iguales que el y los de la derecha sean mayores o iguales a el.
  • nos damos cuenta que el valor 'a' ya se encuentra en la posición correcta, el problema si divide en dos (se basa en la tecnica de divide y venceras, muy utilizado en programación orientado a objetos), al final reunimos los resultados en un vector.
  • y repetimos el procedimiento inicial (usamos recursividad)
  • el proceso finaliza cuando cada dato encuentra su posición correcta.



Este metodo recibe un vector de enteros, el dato en la posición inicial y el ultimo dato valido del array(n-1). la elelección del pivote se puede decir que la promedio ya se suba el dato inicial mas dato final entre dos, es una manera de asegurarse que sea el valor medio.
Hasta que i sea menor que el ultimo valor que es j, se realizaran los while que hacen referencia a:
  • Mientras que el valor que se encuentre en la posición sea menor al que escogimos de pivote, se sumara a la posición mientras encontremos un valor igual o mayor al que se encuentre en el pivote.
  • En este caso es muy parecido solo con la diferencia que el valor que se encuentre en la posición es mayor mientras encontremos un valor que sea igual o menos al del pivote.
Dentro del if se hace el intercambio de valores dependiendo la situación, por ultimo en los dos if finales el metodo se vuelve recursivo pero en un lado actualiza el valor maximo, mientras que en el otro if se actualiza el valor inicial.

Mergesort

Es un algoritmo de ordenación tambien denominado ordenamiento por mezcla, se basa en la tecnica de divide y venceras; funciona de la siguiente manera:

  • Si el largo de un array es de 0 ó 1, entonces ya está ordenado.
  • Dividir el array desordenado en dos subarrays de aproximadamente la mitad del tamaño.
  • Ordenamos cada subarray recursivamente aplicando el ordenamiento por mezcla.
  • Mezclamos los dos subarrays en una solo array ordenado.

El algoritmo mergesort incorpora una idea principal para mejorar su tiempo de ejecución:

Siempre es mejor pequeños problemas que uno grande, es bueno aplicar la tecnica de divide y venceras. ya que es mas facil enlazar dos arrays previamente ordenados que desordenados.




Bibliografia

Publicado por en No hay comentarios:

Recursividad

Hasta ahora todas las clases que hemos tenido son geniales, aprendimos cosas interesantes en cada una y el ingeniero le pone mucho entusiasmo al enseñarnos, la verdad es que hemos asimilado mucho en esa clase. Pero definitivamente de todas esta fue la que mas me gusto.

Es una función que se llama a si misma, pero esta función no es necesaria utilizarla en todos los algoritmos, puede simplemente hacer que el consumo de recursos sea mayor que el algoritmo normal, puede llegar a ser eficiente o no. Ademas puede llegar a crear una función que no llegue a retornar un valor definitivo, este tipo de recursividad hace que se cree un bucle infinito.

A continuación un ejemplo de recursividad fue el primer ejercicio sobre el tema:

Recibimos un número entero, como sabemos tanto el factorial de 0 y 1 es igual a 1, por eso la condición. El factorial de un número es igual al factorial de el número anterior a el por el número base.

n!= (n-1)!*n

Ejemplo: 6!= 5!*6


Explicación grafica del algoritmo recursivo de un factorial















Bibliografia

Publicado por en No hay comentarios:

Algoritmos de ordenamiento

Algoritmo burbuja

Es un sencillo algoritmo de ordenamiento, este algoritmo compara cada uno de los elementos del array, lo compara con el siguiente y si el orden esta equivocado lo cambia y asi sucesivamente hasta que el array no necesite mas intercambios se dice que esta arreglado.












Algoritmo de Inserción

Es un metodo de ordenación, este toma cada dato del arreglo y lo compara con los que se encuentran en posiciones anteriores. Si resulta que el dato con el que se esta comparando es mayor que el dato base, se corre hacia la siguiente posición. Si por el contrario, resulta que el dato con el que se esta comparando es menor, se detiene el proceso de comparación ya que se encontró que esta ordenado y se coloca en su posición.
Es un algoritmo lento, pero puede ser de utilidad para listas semiordenada, pues en ese caso se realizan pocos desplazamientos.

Algoritmo de shell

Es un algoritmo de ordenamiento, se dice que es la generalización del metodo de inserción ya que el metodo de inserción es eficiente si el arreglo esta semiordenado, pero tambien ineficiente porque mueve un dato cada vez.




Este algoritmo es un simple ordenamiento por inserción, solo que este garantiza que los datos del vector estaran casi ordenados, ya que compara elementos separados por espacios de varias posiciones, esto que permite que sea mas rapido hacia la posición adecuada.















Bibliografia




Publicado por en No hay comentarios:

Ordenamientos

Entramos ahora en un tema un poco complejo para algunos pero de mucha ayuda en la solución de problemas complejos.

Empezemos con la pregunta basica.

¿Que es un ordenamiento?

Es la acción de arreglar los datos de un array en un orden secuencial de acuerdo a un criterio. El ordenamiento se lleva a cabo teniendo en cuenta algún campo en los datos y se hace con el fin de permitir una búsqueda fácil de datos.

El ordenar un grupo de datos significa mover los datos o sus referencias para que queden en una secuencia tal que represente un orden, el cual puede ser numérico, alfabético, de una manera ascendente o descendente.

Ejemplo:




¿Cuándo conviene usar un método de ordenamiento?

Cuando se requiere hacer una cantidad considerable de búsquedas y es importante el factor tiempo.

Existen diferentes algoritmos de ordenamiento entre los que encontramos:
  • Burbuja
  • Shell
  • Inserción
  • Quicsort
  • Mergesort
Bibliografia

Publicado por en No hay comentarios:

martes, 6 de abril de 2010

Arrays

Retomamos el tema visto de forma teorica hace mucho tiempo en una clase de algoritmica II, en aquella ocasión donde los problemas eran mas dificiles, estabamos empezando a conocer todo lo referente al mundo de los algoritmos y la programación. Espero que en la parte practica se nos haga mas divertido el aprendizaje y que asimilemos todo lo referente al tema para un futuro, tengo mucha expectativa en esta clase, ya que en cierto tiempo muchos no fuimos muy buenos en el tema. Pero yo se que cada dia todos pondremos de nuestra parte para que la clase sea la mas agradable y entendible.

Bueno ya entrando un poco en el tema, un Array es una estructura de datos que nos permite almacenar variables de un mismo tipo, nos permite tener un manejo mas organizado ya que la variable tiene una distinción numérica, el 0 es el índice del primer elemento mientras que n-1 es el del ultimo.

Los arrays pueden ser de cualquier tipo de dato incluyendo objetos, ya que a su vez, ese tipo de dato es un objeto, las variables de tipo arrays se declaran utilizando [].
Existen dos tipos de arrays:
  • Unidimensional (vectores)
  • Multidimensional (matrices)
En programación los arrays deben declararse, crearse, inicializarse para que podamos usarlos y realizar operaciones con ellos.

Unidimensional (vectores)

tipo_dato[] nombre_array; //declarar

nombre_array= new tipo_dato[tamaño];
// crear (asi reservamos un espacio en la memoria para los datos)


nombre_array[numero_elemento]= valor;
//inicialización(tambien se puede hacer por medio de un for)

for (int i=0; i<(numero_elemento); i++)
{
nombre_array[i]=s.nexttipo_dato();
}

variable= nombre_array[numero_elemento] //asignación

veamos un ejemplo:



int [] vector;
vector = new int [4];
vector[2]=3;
k= vector [2];

un arreglo llamando vector, tiene cuatro elementos de tipo entero, y a k le asignamos el valor del tercer elemento.

Multidimensional (matrices)

tipo_dato[][] nombre_array; //declarar

nombre_array= new tipo_dato[tamaño][tamaño];
// crear (asi reservamos un espacio en la memoria para los datos)

nombre_array[numero_elemento][numero_elemento1]= valor;
//inicialización (tambien se puede hacer por medio de un for)
el valor del numero_elemento1 es opcional solo cuando toda la matriz tiene el mismo tamaño, tenemos el ejemplo cuando es cuadrada, en caso contrario se deja vacio el espacio.

variable= nombre_array[numero_elemento][numero elemento1] //asignación

veamos un ejemplo:

double[][] matrizUnidad;
matrizUnidad= new double [4][4];
for (int i=0; i<4;i++)
{
for (int j=0; j<4;j++)
{

if (i==j)
matrizUnidad[i][j]=1.0;
else
matrizUnidad[i][j]=0.0;
}
}


ejemplo tomado de: http://www.sc.ehu.es/sbweb/fisica/cursoJava/fundamentos/clases1/arays.htm



int[][] matriz;
matriz= new int [4][ ];
matriz[2][0]=3;
k= matriz [2][0];





Bibliografia




Publicado por en No hay comentarios:
Suscribirse a: Entradas (Atom)