Tras unos cuantos algoritmos que cubren el uso de casi todas las funciones explicadas en la teoría. Paso a la explicación simple de algunos algoritmos estándar.

BUSQUEDA DE DATOS:

Búsqueda Lineal: Se trata de determinar si un elemento x está en un vector, para ello buscaremos una posición pos donde se encuentre ese elemento. (Dado un vector a de n elementos se debe cumplir que a(pos)==x)
La búsqueda lineal consiste en recorrer el vector a hasta que encuentre el elemento, o bien hasta que acabe el recorrido (si no está).

Programa: Búsqueda_Lineal

Datos:
n: valor constante.
a: vector de tamaño n, tipo T (debe tener el mismo tipo que x, para poder poner "x" como el dato que queremos buscar dentro del vector)
x: variable de tipo T
pos: número entero
encontrado: variable booleana.


Búsqueda lineal con centinela: Este método es parecido al anterior, y se basa en dimensionar el vector a una dimensión más que las definidas en el tamaño del vector. Esta posición se va a utilizar para introducir el elemento a buscar. De esta forma, nos aseguraremos que siempre va a estar, con el objeto de simplificar las condiciones del proceso repetitivo.

Programa: Busqueda_centinela

Datos:
n: valor constante
a: vector de tamaño n+1 de tipo T
x: variable de tipo T
encontrado: variable booleana


Búsqueda Dicotómica: Si los elementos del vector están ordenados bien de forma creciente o decreciente, no es necesario examinar todos los elementos, ya que comparando el valor buscado x con el valor central, se puede eliminar la búsqueda en una de las dos mitades, con lo cual el algoritmo resulta mucho más rápido. Supondremos que tenemos el vector ordenado en sentido creciente.
Si en cada paso del algoritmo comparamos el valor de x como el de la posición central (k), podemos obtener lo siguiente:

Caso 1: Que a(k) == x -> Acaba la búsqueda y el elemento está en k.
Caso 2: Que a(k) > x -> Eliminamos la parte del vector superior a k.
Caso 3: Que a(k) < x -> Eliminamos la parte del vector inferior a k.

Programa: Busqueda_Dicotomica

Datos:
izq, der: variables que delimitarán la dimensión del vector en la que estamos buscando. Servirán para ir recortando la búsqueda según el resultado de la comparación de a(k) con x.
a: vector de n elementos de tipo T
x: variable de tipo T


ORDENACIÓN DE DATOS:

Generalmente se considera ordenar con reorganizar un conjunto dado de objetos. Por ejemplo, los elementos de un vector en una secuencia especificada. El objetivo es facilitar la búsqueda de los elementos del conjunto ordenado. En particular vamos a practicar la ordenación a los elementos de un vector n>0 elementos de un tipo ordenable, así, los elementos del vector son a(n), deberemos encontrar una permutación de los mismos tal que: a(b1) <= a(b2) ... <= a(bn)

La primera condición a imponer a los métodos de ordenación de vectores es la utilización económica de la memoria disponible, esto implica que las permutaciones de elementos con vista a su ordenación, debe realizarse usando el espacio ocupado por el vector.

Los métodos que trasladan los elementos de un vector a otro no tienen interés (ya que implicaría duplicar el espacio necesario para realizar la operación).

Ordenación por inserción directa:
Para realizar este algoritmo partimos de la siguiente situación hipotética. (NOTA: Nunca se dará esta situación, esto solo sirve para considerar el programa tanto desde el comienzo, como durante el proceso intermedio)

La sección [1, i-1] está ordenada, pero no se asegura que los elementos estén en la posición final de ordenación, a esto se le llama ordenación no clasificada.

Para extender la ordenación al elemento i deberemos insertar el mismo en la posición correspondiente de la sección a(1...i)

Concluimos pues que necesitaremos:

** Extender la ordenación de la sección a**

Una posibilidad sería esta:

(Nótese que usamos uno de los algoritmos de búsqueda tratados anteriormente para buscar la posición correcta del elemento a ordenar.)


Esta disposición es correcta (y si no lo es, corregidme, que os lo agradeceré), pero no es lo más eficiente, aquí he introducido el algoritmo de búsqueda tal cual, para que pudieseis ver facilmente un ejemplo de su utilidad.

Ahora que ya tenemos el algoritmo planteado, vamos a hacerlo más eficiente. Para ello, intentaremos meter ambos bucles en uno. Para ello debemos tener en cuenta que la búsqueda y ordenación de los elementos se pueda hacer de forma simultánea y no en bucles separados. Para conseguir esto, ambos bucles deberían realizarse en el mismo sentido.

Teniendo en cuenta que el desplazamiento en sentido inverso es más simple en el proceso de desplazamiento de datos, mientras que las búsqueda se hace de forma análoga en un sentido u otro, es preferible modificar el algoritmo de ésta.


Si se compara este bucle con el desplazamiento de elementos, se puede observar lo siguiente.

1.- La variable de control de ambos comienza y termina con el mismo valor y i - 1, el correspondiente al valor de inserción.
2.- En ambos casos, la variable se modifica en cada paso de la misma forma, decrementándola, por tanto, ambos ejecutan el mismo númeor de veces. Con los mismos valores de la variable de control.
En consecuencia, las dos variables, y los dos algoritmos pueden combinarse en uno solo.


Quedándonos como resultado el programa final:

Programa: Ordenación_inserción_directa

Datos:
n: constante
a: vector de tamaño n tipo T
x: var de tipo T
encontrado: var lógica (booleana)
pos, i: nº enteros.


Ordenación por selección directa: Partimos del supuesto de que tenemos una sección (1 ... i-1) ordenada y clasificada (recordad que esto era para considerar ambos casos de algoritmo durante inicio y proceso).
El objetivo en ese caso sería extender la ordenación al elemento i del vector. Para ello buscamos el mínimo de la sección (i ... n)

Programa: Inserción_Directa

Datos:
n: cte
a: vec de n elementos tipo T
x: var tipo T
i,j,pos: nºentero

Algoritmo:


Ordenación por intercambio (o método de la burbuja):
Al igual que antes, suponemos que está ordenada y clasificada la sección a(1 ... i-1) y queremos extender la ordenación al elemento i.

La diferencia con el método anterior es que aquí no se busca el mínimo, sino que este se lleva hasta la posición i mediante intercambios de pares de elementos adyacentes del vector.

Si los elementos se consideran burbujas en un depósito de agua, con pesos acordes a sus valores, en cada pasada sobre el vector, asciende una burbuja hasta su posición correspondiente. (También hay la posibilidad de que otras se acerquen a su posición final, por ello hay casos en los que esta ordenación acelera el proceso)


A que éste ha parecido sencillito? Pues es lo que parece. (Cuando lo saqué por primera vez pensé que tenía que haber algo mal porque era demasiado sencillo. Pero no, es correcto. ^^

Actualizaré este post según tenga más material a mano. Nyaa! =3