Recursos Del Web

Continuando con los métodos de búsqueda, seguimos con la búsqueda binaria. Este método es el que habitualmente utilizamos los humanos para encontrar un determinado elemento en una lista previamente ordenada.

El algoritmo es el siguiente:

1. Se compara el valor buscado con el del elemento central del vector
   • Si coinciden, se ha encontrado el numero y se finaliza la búsqueda.
   • Si no coinciden, se determina si el valor buscado debe estar en la mitad izquierda o derecha del vector, dependiendo de si es inferior o superior, respectivamente, del elemento central.

La posición del elemento central del vector es calculado con la siguiente formula:

pMitad = int((pInicial + pFinal)/2)

Donde pInicial y pFinal son las posiciones inicial y final del subVector que se está considerando.

2. En la mitad donde se deba continuar la búsqueda, se continua de la misma manera, es decir; se compara el valor buscado con el elemento central de esa mitad.
   • Si coinciden, se ha encontrado el numero y se finaliza la búsqueda.
   • Si no coinciden, se determinaen cúal de las dos mitades de esta subMitad debe estar el valor buscado.

3. Se continua de este modo (dividiendo el vector en subMitades) hasta que la búsqueda:
   • Finalice con exito (se encuentre el elemento)
   • Se finalice sin exito (no se encontro el elemento)

4. Cuando pInicial sea mayor o igual a pFinal y su contenido sea diferente del valor buscado, entonces se considera que el valor buscado no existe en el vector.

Este es el algoritmo:

Aquí está el código en VB.Net
(continue reading…)

Tweet

bb1c8e8699bdfa071d34312466986a38

Continuando con los métodos de búsqueda, seguimos con la busqueda secuencial pero ahora en un vector ordenado, lo cual tiene mas eficiencia que el mismo método pero en vector desordenado. Aquí la ventaja es de que como tu ya sabes que el vector ya esta ordenado de antemano, es más fácil y rapido detectar cuando el elemento no se encuentra dentro del vector. Pero esto no significa que este método sea el más rápido.

El algoritmo es el siguiente:

Se toma el elemento a buscar y se compara con cada una de las posiciones del vector donde esta el conjunto de datos.
Esto se hace dentro de un ciclo el cual dejará de girar cuando se encuentre un numero igual al buscado o cuando se termine el vector o cuando se detecte que un elemento dentro del vector es mayor que el buscado (en un vector ordenado ascendente).
Sí no se encontró el numero buscado, se envía un mensaje indicando que el elemento buscado no fue encontrado, de lo contrario haces lo que tu decidas con el elemento encontrado.

Aquí está el codigo en VB.Net
(continue reading…)

Tweet

89ebdfcb3a4f26e1caa059ea384f1dc0

Un tema importante en la estructura de datos, es la búsqueda de estos. Muchas veces se pueden tener cantidades enormes de datos y su manipulación se vuelve cada vez mas complicada y tardada, es por esto que los métodos de búsquedas deben ser bastante eficaces para poder encontrar un dato especifico dentro de una gran cantidad de datos y en el menor tiempo posible.

Este método de búsqueda (secuencial) es sin duda el más sencillo y recomendable cuando tienes una cantidad de datos mínima, ya que es muy fácil de programar. La desventaja es que no es recomendable para bucar algun dato dentro de una cantidad muy grande de datos ya que su desempeño sería bastante lento.

El algoritmo es el siguiente:

Se toma el elemento a buscar y se compara con cada una de las posiciones del vector donde esta el conjunto de datos.
Esto se hace dentro de un ciclo el cual dejará de girar cuando se encuentre un numero igualal buscado o cuando se termine el vector.
Sí no se encontró el numero buscado, se envía un mensaje indicando que el elemento buscado no fue encontrado, de lo contrario haces lo que tu decidas con el elemento encontrado.

He aquí el diagrama de flujo:

Y aquí está el codigo en VB.Net
(continue reading…)

Tweet

aa2d4df51490fde1f26f53172aa3461f

Este día solo vengo de rapido para postear algunos programas que he estado haciendo de tareas en la escuela. Y pues lo hago de rápido ya que mañana tengo examen de desarrollo de proyectos y sinceramente no he estudiado nada :S jeje así que pues aquí esta algo rápido.

Este es el ordenamiento Quick Sort (en español ordenamiento rápido) y como su nombre lo indica, es el ordenamiento más eficiente y eficaz de todos, y por obviedad el más rápido. Este es un algoritmo algo sencillo, una vez que entiendes el tema de recursividad, se te hará fácil entender su funcionamiento.

Vamos con la explicación rápida:

1. El vector desordenado es enviado a la función “quicksort()”
2. Al llegarle el vector a la función, se toma el primer elemento del vector (o cualquiera; Nota: en nuestro caso tomamos el primero) y se considera ese elemento como “pivote” o “comodín”.
3. Después se recorre todo el vector; durante el recorrido, se va buscando los numeros menores que el pivote, sí el elemento del vector en una vuelta es menor que el pivote, entonces se manda a la izquierda del pivote, de lo contrario no se hace nada. Esto provocará que después de recorrer todo el vector, todos los elementos menores que el pivote quedarán a la izquierda de este y los mayores al pivote a la derecha.
4. Se envía recursivamente la mitad izquierda del vector (números menores que el pivote sin tomar en cuenta el mismo pivote) a la función quicksort
5. Se envía recursivamente la mitad derecha del vector (números mayores que el pivote sin tomar en cuenta el mismo pivote) a la función quicksort

Pero una imagen dice más que mil palabras:

Y este es el código:
(continue reading…)

Tweet

147577693785ca3ea229202308f9eaa9

Que onda.

Continuando con los métodos de ordenamiento (y aprovechando que me los están dejando de tarea jaja) aquí les traigo el Ordenamiento Shell.

Este es una “version mejorada” del ordenamiento por burbuja, ya que también compara dos valores del vector y dependiendo de si uno es mayor que el otro, se intercambian. En si lo que hace el método Shell es, primeramente semiordenar el vector, para despues ordenarlo de bien a bien.

Veamos su funcionamiento:

1. Únicamente al inicio se obtiene el numero de salto (largo del vector/2). Nota: la división es redondeada al entero próximo inferior.
2. Un ciclo externo girará mientras el Salto sea diferente de 0
3. Un ciclo interno irá pasando por cada posición del vector iniciando en 0 hasta que el contador del ciclo interno + el Salto sea igual al tamaño del vector.
4. Dentro del ciclo interno se irán comparando la posición del vector actual con la posición del vector actual + Salto. Si vec[contador] > vec[contador + salto] entonces se intercambian los números, y de esta manera van quedando los numero de menor valor a la izquierda y los de mayor valor a la derecha del vector.
5. Al final se checa si hubo algún intercambio, si sí entonces se vuelve a repetir el proceso con el mismo salto, de lo contrario el salto se decrementa y se repite el proceso nuevamente.

Gráficamente sería algo como esto:

y el codigo es el siguiente:
(continue reading…)

Tweet

199c93afd84b8005709a89d18b183627