Ordenacion y Busqueda

Supongamos un vector, donde parte de sus elementos están ordenados y otros no. Los pasos a seguir para realizar la ordenación son los siguientes:

r	n	t	d	a	h	m	z	o	k	s	c
a1	a2	...	ak-1	ak	...	...	...	ai	...	...	an

Elementos desordenados

a) Para realizar la ordenación por selección se hacen varios barridos del vector. Primeramente cogemos el primer elemento del vector y lo comparamos con todos los elementos restantes buscando aquel elemento que posea el valor más pequeño.

r	n	t	d	a	h	m	z	o	k	s	c
a1	a2	...	ak-1	ak	...	...	...	ai	...	...	an

b) Una vez encontrado el elemento menor, se coloca en la posición correspondiente, realizando un intercambio de posiciones entre el elemento que hemos comparado y el que hemos encontrado.

c) Una vez ordenado el primer elemento, realizamos la misma operación con los restantes. Finalmente el vector quedará ordenado.

a	c	d	h	k	m	n	o	r	s	t	z
a1	a2	...	ak-1	ak	...	...	...	ai	...	...	an

El algoritmo de ordenación por selección es el siguiente.

Algoritmo Selección

constante n=...

variable entera i,j,k

real x ← variable de apoyo

vector de reales a(1..n)

Leer a

Para i de 1 a n-1 hacer

k ←i

Para j de i+1 a n hacer

si a(j) < a(k) entones

k Ü j

Finsi

Fin para

x ← a(i)

a(i) ← a(k)

a(k) ← x

Fin para

Escribir a

Final

Búsqueda Secuencial

Consiste en recorrer el vector, con sus datos no necesariamente ordenados, del principio hacia el final. Si se encuentra el valor buscado se da por finalizada la búsqueda en caso contrario, tras haber recorrido todo el vector se indica que el elemento no se encuentra almacenado en el vector.

Algoritmo búsqueda_secuencial

Var: A(1…n) Arrays, t: entero

Inicio

encontrado ←falso

i←1

mientras (i<=n) y (encontrado=falso) hacer

si t=A(i) entonces

escribir “se encontro el elemento buscado en la posición “,i

encontrado←verdadero

sino i←i+1

fin_si

fin_mientras

Si i=n+1 entonces

escribir “no se encontro el elemento “

fin si

fin

Búsqueda Lineal

Dado un vector que suponemos desordenado, localizar un elemento que tenga un valor determinado requerirá un barrido a lo largo del mismo hasta encontrar dicho elemento.

Algoritmo búsqueda_lineal

constante n= ...

variable entera i

real x

vector de reales a(1..n)

Leer a

Leer x

y ← 1

mientras (a(i)¹ x and i £ n) hacer

i ← i+1

fin mientras

si i £ n entonces

escribir ("Dato ";x;" Encontrado en la posición: ";i)

sino escribir ("Dato no encontrado")

finsi

Final

Búsqueda Binaria

Si el vector está ordenado, existen métodos de búsqueda mas eficientes. Uno de ellos es el de la búsqueda dicotómica. Veamos un ejemplo donde el vector está ordenado de forma ascendente (menor -> mayor).

Algoritmo Busqueda_Dicotómica

constante n=...

variable entera i,j,m

real x

vector a(1..n)

Leer a

Leer x

i ← 1

j ← n

repetir

m ← (i+j)/2

si x < a(m) entonces

j ← m-1

finsi

si x > a(m) entonces

i ← m+1

finsi

hasta que (a(m)=x or i>j)

si a(m) = x entonces

escribir ("Dato ";x;" Encontrado en la posición: ";m)

sino escribir ("Dato no encontrado")

finsi

Final

Cadenas

Se define como la secuencia de caracteres que se interpretan como un dato único, su longitud puede ser fija o variable, también pueden estar constituidas por caracteres alfanumérico.

Ejercicios

1.-Hacer un pseudocódigo que imprima los números del 1 al 100.

2.-Hacer un pseudocódigo que imprima los números pares entre 0 y 100.

3.-Hacer un pseudocódigo que imprima los números impares hasta el 100 y que imprima cuantos impares hay.

4.-Realizar la tabla de multiplicar de un número entre 0 y 10.

5.-Generar una matriz de 4 filas y 5 columnas con números aleatorios entre 1

y 100, e imprimirla.

6.-Dado dos vectores A y B de 15 elementos cada uno, obtener un vector C donde la posición i se almacene la suma de A[i]+B[i].

7.-Dado dos vectores A y B de 15 elementos cada uno, obtener un vector C donde la posición i se almacene la suma de A[i]+B[i] y mostrar el mayor de los C[i].

8.-Dado dos matrices A y B obtener la suma.

9.-Dado una matriz determinar la posición (i,j) del mayor.

10.-Dado una matriz determinar la posición (i,j) del mayor y menor.