PDF de programación - Tema 9 - Algoritmos sobre listas

Imágen de pdf Tema 9 - Algoritmos sobre listas

Tema 9 - Algoritmos sobre listasgráfica de visualizaciones

Publicado el 2 de Junio del 2019
233 visualizaciones desde el 2 de Junio del 2019
324,0 KB
41 paginas
Creado hace 4a (29/11/2015)
Tema 9

Algoritmos sobre listas
Programación
2015-2016

Programación - Tema 9: Algoritmos sobre listas

1

Tema 9. Algoritmos sobre listas

● Algoritmos sobre Arrays.

● Búsqueda.

● Inserción.

● Ordenación.

Programación - Tema 9: Algoritmos sobre listas

2
2

Algoritmos sobre Arrays

● En la vida coditiana es frecuente la búsqueda de

elementos en conjuntos o listas de datos. Por ejemplo:
Índices de libros, callejeros, guías de teléfonos, etc.

● Es evidente que si dichos conjuntos de datos no
estuvieran ordenados la búsqueda sería larga y
pesada.

● En computación se dedica bastante tiempo a la búsqueda
y ordenación de datos. Por ejemplo accesos a Google,
etc.

● En este tema vamos a abordar algunos de los algoritmos
de búsqueda y ordenación más utilizados sobre arrays.

Programación - Tema 9: Algoritmos sobre listas

3

Tema 9. Algoritmos sobre listas

● Algoritmos sobre Arrays.

● Búsqueda.

● Inserción.

● Ordenación.

Programación - Tema 9: Algoritmos sobre listas

4
4

Búsqueda

Los algoritmos de búsqueda más sencillos son:

– la búsqueda secuencial

– la búsqueda binaria

Programación - Tema 9: Algoritmos sobre listas

5

Búsqueda secuencial

● Puede realizarse en arrays ordenados y en arrays

desordenados.

● En los desordenados es la única posible.

● Hay que comparar cada elemento del array con el elemento

buscado.

● La búsqueda finaliza cuando se encuentra el elemento o

cuando se llega al final del array.

● Si se ha encontrado el elemento se indicará su posición en el

array, y en caso contrario se dará un mensaje de error.

● Es un método sencillo, pero poco eficiente. Obsérvese que

puede ser necesario recorrer el array entero.

Programación - Tema 9: Algoritmos sobre listas

6

Algoritmo

Variables
lista[ ] es un array de enteros
elemento es un entero el dato buscado
Pseudocódigo
Inicio programa
mientras (elemento no encontrado y pos<=ultimo) hacer

si elemento == lista [pos] entonces

encontrado  cierto

si no

pos  pos+1

fin si
fin-mientras
si encontrado == cierto entonces

devolver pos

si no

Visualizar “Elemento no encontrado”

Fin programa

Programación - Tema 9: Algoritmos sobre listas

7

Código Java

public static int secuencial (int [] vector,int elem, int p,int u){

// recibe una matriz no ordenada, un elemento a buscar
// y los limites del rango donde buscar (p y u)
// devuelve la posición del elemento o -1 si no esta
int i;
boolean encontrado;
i =p;

encontrado = false;

while (i<=u && !encontrado){


if (elem == vector[i]){
encontrado = true;

i++;
}

}

if (encontrado){



return i;

} else {

return -1;
}

}

Programación - Tema 9: Algoritmos sobre listas

8

Búsqueda binaria

El array debe estar ordenado.
Es mas rápido que el secuencial.
Algoritmo:

– Se busca el elemento central del array, si éste no coincide con el
elemento buscado se determina en que mitad del array debe estar.
Se busca en esa mitad repitiendo el proceso las veces que haga
falta hasta encontrar el elemento, o bien hasta que se determine
que no está en la lista.

Programación - Tema 9: Algoritmos sobre listas

9

Búsqueda binaria

Buscamos el elemento 20 en el array lista

Programación - Tema 9: Algoritmos sobre listas

10

Búsqueda binaria

Buscamos el elemento 20 en el array lista

Programación - Tema 9: Algoritmos sobre listas

11

Algoritmo

Variables
lista(i) es un array ordenado
men, may, cen son variables enteras para el índice en la lista
X es el valor búscado
Pseudocódigo
Inicio programa.
men  1
may  n
cen  (n+1)/2
Mientras lista(cen) <> X y men < may hacer

si lista(cen) > X entonces

may  cen-1

sino

men  cen+1

fin_si
cen  (men+may)/2

Fin mientras
Si lista(cen) = X entonces

escribir “Encontrado en la posición”, cen

escribir “No encontrado en el array”

sino

Fin si
Fin Programa

Programación - Tema 9: Algoritmos sobre listas

12

Código Java

public static void binaria (int [] vector,int elem, int p,int u, int posicion, boolean encontrado){
// recibe una matriz ordenada, un elemento a buscar y los limites del rango donde buscar(p y u)

// recibe dos referencias con un booleano para devolver si el elemento se encuentra en la matriz,
// y con un entero para devolver la posicion donde esta o la que le corresponde si no esta
int i;
int menor = p, mayor = u, medio=0;
encontrado = false;
while (!encontrado && mayor >= menor){

medio = (mayor + menor) / 2;
if (elem == vector[medio])

encontrado=true;
else if (elem > vector[medio])

menor = medio + 1;

mayor = medio - 1;

// buscar en la mitad superior

// buscar en la mitad inferior

else

}
if (encontrado)

posicion = medio;

else

}

posicion = menor;

Programación - Tema 9: Algoritmos sobre listas

13

Tema 9. Algoritmos sobre listas

● Algoritmos sobre Arrays.

● Búsqueda.

● Inserción.

● Ordenación.

Programación - Tema 9: Algoritmos sobre listas

Programacion – Tema 7: Tratamiento de Listas

14

Inserción

El array debe tener espacio para añadir un nuevo elemento.

Dos posibilidades:

– Array desordenado

• El elemento se insertara en el lugar que se indique.

– Array ordenado

• El elemento ocupara el lugar que le corresponda.

Programación - Tema 9: Algoritmos sobre listas

15

Inserción en array desordenado.

Insertar el elemento 95 en la posición 2 del array lista

Programación - Tema 9: Algoritmos sobre listas

16

Inserción en array desordenado. Algoritmo
Variables
j índice del array; k posición de inserción
elemento valor a insertar
lista(j) array de elementos
Pseudocódigo
Inicio Programa
si lista(j) llena entonces

escribir “Error, no se puede insertar “

fin_si
para j = ultimo hasta j>=k ; con incremento -1 hacer

lista(j+1)  lista(j)

fin_para
lista(k)  elemento
ultimo  ultimo + 1
Fin programa

Programación - Tema 9: Algoritmos sobre listas

17

Código Java

public static int insertarNoOrdenada (int [] vector, int elemento,
int pos, int ultimo){
// recibe una matriz, un elemento a insertar, y la posicion de
// insercion. También recibe un objeto num de tipo Entero con la última
// posición ocupada de la matriz. Se supone que el valor de
// pos es correcto

if (ultimo == vector.length - 1)
return -1; // codigo de error, matriz llena
else {
for (int i = ultimo ; i >= pos; i-- )
vector[i+1] = vector[i];
vector[pos] = elemento;
ultimo ++;
return 0;
}

} // fin de insertarNoOrdenada

Programación - Tema 9: Algoritmos sobre listas

18

Inserción en array ordenado

● Si se va a insertar en un array ordenado hay que insertar el

elemento en el lugar que le corresponde.

● Se utilizará el algoritmo de búsqueda binaria para buscar la

posición de inserción.

● No obstante caben dos posibilidades:
– Que no se admitan elementos repetidos
– Que pueda haber elementos repetidos.

Programación - Tema 9: Algoritmos sobre listas

19

Inserción en array ordenado sin repetidos

● Se comprueba que el array no está lleno
● Se utiliza la búsqueda binaria para comprobar si el elemento

a insertar ya está en el array.

● Si está se lanza un mensaje de error y se termina.
● Si el elemento no está, el mismo algoritmo de búsqueda
binaria nos devuelve la posición de inserción, y se procede
como en caso de array desordenado.

Programación - Tema 9: Algoritmos sobre listas

20

Inserción en array ordenado con repetidos

● Se comprueba que el array no está lleno.
● Se utiliza la búsqueda binaria para encontrar
la posición en la que hay que insertar el
elemento, y se procede como en caso de
array desordenado.

Programación - Tema 9: Algoritmos sobre listas

21

Tema 9. Algoritmos sobre listas

● Algoritmos sobre Arrays.

● Búsqueda.

● Inserción.

● Ordenación.

Programación - Tema 9: Algoritmos sobre listas

22
22

Métodos de ordenación

– Intercambio directo

– Inserción directa

– Selección directa

Programación - Tema 9: Algoritmos sobre listas

23

Ordenación por intercambio directo
Método de la burbuja

Se intercambian pares de elementos consecutivos.
Consiste en recorrer varias veces el array comparando
en cada una de ellas los elementos consecutivos para
intercambiarlos si no están ordenados.
Existen varias versiones:

– Recorrer el vector de izquierda a derecha
– Recorrer el vector de derecha a izquierda.
En los dos casos el orden es ascendente.

Programación - Tema 9: Algoritmos sobre listas

24

Método de la burbuja

Programación - Tema 9: Algoritmos sobre listas

25

Método de la burbuja

Programación - Tema 9: Algoritmos sobre listas

26

Método de la burbuja

Programación - Tema 9: Algoritmos sobre listas

27

Método de la burbuja

Programación - Tema 9: Algoritmos sobre listas

28

Método de la burbuja

Programación - Tema 9: Algoritmos sobre listas

29

Método de la burbuja. Algoritmo

Variables
P, I índices de bucles
n tamaño del array
Lista array de elementos a ordenar
Aux variable del tipo de elementos del array
Pseudocódigo
Inicio Programa
Para P de 1 a n-1 hacer

Para I de 1 a n-P hacer
Si Lista(I) > Lista(I+1) entonces
Aux  Lista(I)
Lista(I)  Lista(I+1)
Lista(I+1)  Aux
Fin_si
Fin_para

Fin_para
Fin Programa

Programación - Tema 9: Algoritmos sobre listas

30

Método de la burbuja. Código

public static void burbuja(int [] vector, int num){

// ordena por el algoritmo de la burbuja una matriz de
// num elementos utiles.

int aux;
for (int k=1; k<num; k++)
for (int j=0; j<num - k; j++)
if (vector[j] > vector [j+1]){
aux = vector [j];
vector [j] = vector [j+1];
vector [j+1] = aux;
}
}

Programación - Tema 9: Algoritmos sobre listas

31

Ordenación por inserción directa
Método de la baraja

trata de
  • Links de descarga
http://lwp-l.com/pdf16023

Comentarios de: Tema 9 - Algoritmos sobre listas (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad