Búsqueda y ordenación
Programación II
7-8 de enero de 2009
Funciones
• Un concepto fundamental en este curso
es la función
• Una función no sólo resuelve un problema
específico, sino una clase de problemas
genéricos
• Ejemplo:
– sumar los números enteros 5 y 6 (específico)
– sumar los números enteros a y b (genérico)
Funciones
• Una función tiene una entrada y una
salida
• La entrada es una lista de variables que
especifica el tipo de cada variable
• La salida es un valor de un tipo
determinado
• Ejemplo en C:
int sumar(int a, int b)
Funciones
• Una función debe resolver correctamente
el problema para cualquier valor de las
variables de entrada
• Por lo tanto, tiene que detallar el proceso
completo que lleva a la solución
• Una función que no produce ningún
resultado se llama acción
Ejemplos
int sumar(int a, int b) {
int resultado = a + b;
return resultado;
}
void mostrar(int x) {
printf("El valor es %d\n", x);
}
Llamar a funciones
• Para resolver un problema específico del
tipo resuelto por una función, se llama
• Llamar a una función consiste en
especificar los valores de entrada:
int suma = sumar(5, 6);
mostrar(3);
• Al llamar a una función se ejecuta su
proceso con los valores especificados
Pseudocódigo
• El pseudocódigo es un lenguaje genérico
para escribir funciones
• No corresponde a ningún lenguaje de
programación (como C o Java)
• En cambio, está compuesto por palabras
más cercanas al lenguaje natural
• Vamos a usar el pseudocódigo para
escribir funciones
Ejemplos
funcion Sumar(a:natural,
b:natural) devuelve natural
variable resultado:natural;
resultado  a + b;
devuelve resultado;
ffuncion
accion Mostrar(x:natural)
// Mostrar el valor de x en la pantalla
faccion
Interpretar programas
• La programación no sólo consiste en
escribir programas
• También es necesario poder interpretar
programas de otros programadores
– utilizar el código en su programa
– adaptar el código a problemas parecidos
– ayudar en el proceso de depuración
– verificar que la solución es correcta
Métodos de Búsqueda y Ordenación
Búsqueda lineal
Búsqueda lineal con marcador
Búsqueda binaria
Búsqueda binaria simplificada
Esquemas sencillos de ordenación
Algoritmo de la Burbuja: Bubble Sort
Algoritmo de Inserción: Insertion Sort
Algoritmo de Selección: Selection Sort
Métodos de Búsqueda y Ordenación
Los problemas más comunes en la informática son la
búsqueda y la ordenación.
Número de preguntas diarias en Google: 400 millones
(2006)
Por lo tanto, la eficiencia de la búsqueda es importante
La ordenación consiste en ordenar los elementos de un
conjunto con el fin de acelerar la búsqueda
Búsqueda lineal
Encontrar un elemento determinado dentro de una
colección dada.
La búsqueda se realiza sobre una estructura de datos
de tamaño fijo y conocido, por ejemplo, un vector.
Los algoritmos sirven para hacer búsquedas sobre
cualquier tipo de datos, siempre que sea posible realizar
comparaciones (‘igualdad’, ‘menor que’) sobre este tipo.
¿Porqué se llama lineal?
Búsqueda lineal
1 funcion BusquedaLineal (V: vector de natural ;
2
elem,n : natural ) devuelve entero
3 variable i : natural ;
4 i←1;
5 mientras ( ( i  n ) y (V[i]  elem) ) hacer
6
i ← i +1;
7 fmientras
8 si ( i  n ) entonces
9
devuelve i ;
10 sino
11
devuelve -1;
12 fsi
13 ffuncion
Búsqueda lineal
La instrucción mientras lleva una doble condición:
mientras ( ( i  n ) y (V[i]  elem) ) hacer
Comprobar que la doble condición se satisface para
cada valor de la variable i es ineficiente
Una manera de evitar la doble condición es introducir un
marcador
Búsqueda lineal con marcador
1 funcion BusquedaLinealConMarcador (V: vector de natural ;
2
elem,n : natural ) devuelve entero
3 variable i : natural ;
4 i←1;
5 V[n+1] ← elem ;
6 mientras (V[i]  elem) hacer
7
i ← i +1;
8 fmientras
9 si ( i = n+1 ) entonces
10
devuelve -1;
11 sino
12
devuelve i;
13 fsi
14 ffuncion
Búsqueda binaria
La búsqueda lineal es la primera idea que ocurre para el
problema de la búsqueda.
Sin embargo, su eficiencia puede ser mejorado de forma
considerable.
Para hacerlo es necesario suponer que los elementos del
vector estén ordenados.
Suponemos que el vector esta ordenado de forma
ascendente (de menor a mayor).
Búsqueda binaria
Si el vector está ordenado (de manera ascendente o
descendente), es posible aplicar búsqueda binaria.
La idea es hacer servir la propiedad adicional del vector
para acelerar el proceso de búsqueda:
1) Dividir el vector en dos partes iguales.
2) Si el elemento en el centro del vector es mayor que el
elemento buscado, buscar en la primera mitad.
3) Si el elemento en el centro del vector es menor que el
elemento buscado, buscar en la segunda mitad.
1 funcion BusquedaBinaria (V: vector de natural ; elem,n : natural ) devuelve entero
2
variable E,D,medio : natural ;
3
encontrado : booleano ;
4
E←1;
5
D←n;
6
encontrado := falso ;
7
mientras ( (E  D) y no(encontrado) ) hacer
8
medio ← (E+D) / 2;
9
si (V[medio] = elem) entonces
10
encontrado ← cierto;
11
sino
12
si (V[medio] < elem) entonces
13
E ← medio + 1; // derecha.
14
sino
15
D ← medio - 1; // izquierda.
16
fsi
17
fsi
18 fmientras
19 si ( encontrado ) entonces
20
devuelve medio;
21 sino
22
devuelve -1;
23 fsi
24 ffuncion
Búsqueda binaria simplificada
De nuevo, la instrucción mientras lleva una doble
condición
mientras ( (E  D) y no(encontrado) ) hacer
Es posible mejorar ligeramente la eficiencia eliminando
la doble condición
Una manera de hacerlo es dejar de comprobar si el
elemento en el medio es igual al elemento buscado
Con esta modificación, es posible que el algoritmo repita
más veces el bucle mientras
Sin embargo, cada iteración será más eficiente
1 funcion BusquedaBinariaSimplificada (V: vector de natural ;
2
elem,n : natural ) devuelve entero
3 variable E,D,medio : natural ;
4 E←1;
5 D←n;
6 mientras (E  D) hacer
7
medio ← (E+D) / 2;
8
si (V[medio] < elem) entonces
9
E ← medio + 1;
10
sino
11
D ← medio;
12
fsi
13 fmientras
14 si ( (D = n + 1) o (V[D]  elem) ) entonces
15
devuelve -1;
16 sino
17
devuelve D;
18 fsi
19 ffuncion
Eficiencia de la búsqueda
¿Cuál de las dos opciones de búsqueda (lineal, binaria)
es más óptimo?
Esquemas sencillos de ordenación
Hemos visto como la búsqueda se puede realizar con más
eficiencia si los elementos están ordenados.
Si necesita buscar muchos datos en un mismo conjunto,
vale la pena ordenar los elementos primero.
Igual que para la búsqueda, la ordenación se puede
realizar sobre cualquier tipo de elementos, siempre que se
puedan comparar (‘menor que’).
Esquemas sencillos de ordenación
Como la ordenación es un problema importante,
existen un gran número de algoritmos de ordenación.
Los algoritmos existentes se pueden utilizar en
diferentes estructuras de datos (p.ej., un vector).
Imponen diferentes tipos de requerimientos sobre los
datos a ordenar.
También varía su eficiencia, tanto a nivel de memoria
como a nivel de tiempo de ejecución.
3.3 Esquemas sencillos de ordenación
En general, los algoritmos más eficientes son más
complejos y menos intuitivos.
Estudiaremos en total cinco de estos algoritmos.
Los tres primeros (Burbuja, Inserción, y Selección)
son muy sencillos, aunque no muy eficientes.
Los otros dos (MergeSort y QuickSort) son tan
eficientes como se puede esperar para un algoritmo
de ordenación, pero menos intuitivos.
Algoritmo de la Burbuja: Bubble Sort
El algoritmo de ordenación de
la burbuja es uno de los más
fáciles de recordar.
Su nombre describe de manera
intuitiva su funcionamiento.
Imaginamos que los números
menores ‘pesan menos’ y
‘suben a la superficie’ como
una burbuja.
Se basa en el intercambio
entre pares de items
Algoritmo de la Burbuja: Bubble Sort
1 funcion Burbuja (V : vector de natural ; n : natural ) devuelve vector de natural
2
variable i,j : natural ;
3
para i ← 1 hasta n-1 hacer
4
para j ← n hasta i+1 pasos –1 hacer
5
si (V[j] < V[j-1]) entonces
6
Intercambiar(V, j, j-1);
7
fsi
8
fpara
9
fpara
10 devuelve V;
11 ffuncion
12
13 accion Intercambiar (V : vector de natural ; i,j : natural )
14 variable aux : natural ;
15 aux ← V[i] ;
16 V[i] ← V[j] ;
17 V[j] ← aux ;
18 faccion
Algoritmo de la Burbuja: Animación
http://sziami.cs.bme.hu/~gsala/alg_anims/3/bsort-e.html
http://www.cs.ubc.ca/spider/harrison/Java/
http://www.cs.hope.edu/~alganim/animator/Animator.html
http://www2.hig.no/~algmet/animate.html
Algoritmo de Inserción: Insertion Sort
Se basa en el método seguido por los jugadores de cartas:
Sec-destino (ordenada)
Secuencia-Origen(por ordenar)
V[1 . .
.
i-1]
V[i . . .
n]
En cada paso tomamos el elemento V[i] y lo insertamos
donde convenga de la secuencia destino.
44 55 12 42 94 18 6
67
i=2
44 55
i=3
12 44 55
i=4
12 42 44 55
i=5
12 42 44 55 94
i=6
12 18 42 44 55 94
i=7
6
12 18 42 44 55 94
i=8
6
12 18 42 44 55 67 94
para i=2 hasta n hacer
insertar V[i] en V[1..i-1]
fpara
Para simplificar la inserción
ampliamos el vector a V[0..n] para
poner en v[0] el marcador o centinela
que simplifique la búsqueda de la
inserción.
Insertar v[i] en v[0..i]:
si v[i-1]<v[i] hacer
intercambiar V[i] por v[i-1]
sino terminar
fsi
Algoritmo de Inserción: Insertion Sort
1 funcion Insercion(V: vector de natural; n:natural) devuelve vector de natural
2 variable i,j : natural ;
3 V[0] ← MIN_INT;
4 para i ← 2 hasta n hacer
5
j ← i;
6
mientras (V[j] < V[j-1]) hacer
7
Intercambiar(V, j, j-1);
8
j ← j-1;
9
fmientras
10 fpara
11 devuelve V;
12 ffuncion
13 accion Intercambiar (V : vector de natural ; i,j : natural )
14 variable aux : natural ;
15 aux ← V[i] ;
16 V[i] ← V[j] ;
17 V[j] ← aux ;
18 faccion
Algoritmo de Inserción: Animación
http://sziami.cs.bme.hu/~gsala/alg_anims/3/isort-e.html
http://www.cs.ubc.ca/spider/harrison/Java/
http://www.cs.hope.edu/~alganim/animator/Animator.html
http://www2.hig.no/~algmet/animate.html
Algoritmo de Selección: Selection Sort
En cada paso seleccionamos el elemento de menor valor de los no
ordenados y lo colocamos como primero de los no ordenados:
seleccionamos-entre colocamos-en quedará-por-ordenar
i=1
v[1..n]
v[1]
v[2..n]
i=2
v[2..n]
v[2]
v[3..n]
i=3
v[3..n]
v[3]
v[4..n]
i=n-1
v[n-1..n]
v[n-1]
v[4..n]
El último ya queda ordenado!
 Para i=1 hasta n-1 hacer
Asignar a k el menor valor de v[i..n]
Intercambiar v[i] con v[k]
fpara
Idea opuesta a la de Inserción:
•Inserción: trabaja sobre los ya
ordenados
•Selección: trabaja sobre los ya
ordenados
Algoritmo de Selección: Selection Sort
1 funcion Seleccion(V: vector de natural; n: natural) devuelve vector de natural
2 variable i,j,menor : natural ;
3 para i ← 1 hasta n - 1 hacer
4
menor ← i;
5
para j ← i + 1 hasta n hacer
6
si (V[j] < V[menor]) entonces
7
menor ← j;
8
fsi
9
fpara
10
Intercambiar(V, i, menor);
11 fpara
12 devuelve V;
13 ffuncion
Algoritmo de Selección: Animación
http://sziami.cs.bme.hu/~gsala/alg_anims/3/ssort-e.html
http://www.cs.ubc.ca/spider/harrison/Java/
http://www.cs.hope.edu/~alganim/animator/Animator.html
http://www2.hig.no/~algmet/animate.html
Eficiencia de la ordenación
¿Cuál es la eficiencia de los algoritmos sencillos de
ordenación?
Una idea: contar el número de instrucciones que cada
algoritmo realiza
Hay que tomar en cuenta que las instrucciones dentro
de un bucle mientras se repiten varias veces
Descargar

Búsqueda y ordenación