Ordenacion Y Busqueda

´ lica de Chile
Pontificia Universidad Cato
Escuela de Ingenier´ıa
´n
Departamento de Ciencia de la Computacio
IIC1103 — Introducci´on a la Programaci´on

Cap´ıtulo 7: Ordenaci´
on y B´
usqueda
Resumen te´
orico
La operaci´on de ordenar consisten seleccionar de un conjunto de datos y ordenarlos bajo alg´
un determinado
criterio. Por ejemplo, cada elemento del conjunto de datos de una gu´ıatelef´onica tiene un nombre, una
direcci´on y un n´
umero de tel´efono; la gu´ıa telef´onica est´a dispuesta en orden alfab´etico de nombres; los
elementos num´ericos se pueden ordenar en orden creciente o decreciente de acuerdo al valor num´erico del
elemento. En terminolog´ıa de ordenaci´on, el elemento por el cual est´a ordenado un conjunto de datos (o se
est´a buscando) se denomina clave.
Unacolecci´on de datos (estructura) puede ser almacenada por ejemplo en un array (vector o tabla). Una
estructura se dice que est´a ordenada por la clave k si la lista est´a en orden ascendente o descendente con
respecto a esta clave. La colecci´onde datos se dice que est´a en orden ascendente si: i < jimplicaquek[i] <=
k[j]. En cambio, est´a en orden descendente si: i > jimplicaquek[i] <= k[j] para todoslos elementos de la
colecci´on.
Por ejemplo, para una gu´ıa telef´onica, la lista est´a clasificada en orden ascendente por el campo clave k,
donde k[i] es el nombre del abonado (apellidos, nombre). Un ejempo m´as simple de n´
umeros es la colecci´on
4514213245 que se encuentra en orden ascendente y la colecci´on 757035161412 en cambio se encuentra en
orden descendente.

B´
usqueda
Los computadoresse emplean frecuentemente para almacenar grandes vol´
umenes de datos.
Tener mucha informaci´on implica tener dificultades para darle real utilidad.
Los algortimos de b´
usqueda son fundamentales para poder localizar la informaci´on relevante en el
menor tiempo posible.
Los algoritmos de ordenaci´on permiten mantener la informaci´on ordenada de tal forma que la b´
usqueda
se simplifique.
Dado unvalor X, debolver el ´ındice del elemento X en el arreglo, en caso de existir. En caso contrario devolver
no encontrado (-1). Se supone que en un arreglo no hay entradas duplicadas.
Existen varios procedimientos (algoritmos) de b´
usqueda. Nosotros veremos dos:
B´
usqueda Lineal
B´
usqueda Binaria
B´
usqueda Lineal
Consiste en recorrer el arreglo hasta encontrar el elemento buscado (elemento porelemento).
Si se llega hasta el u
´ ltimo elemento y a´
un no se ha encontrado, entonces no se encuentra en la lista.

IIC1103 – Cap´ıtulo 7: Ordenaci´on y B´
usqueda

1

Declaraci´
on 1 public int busquedaLineal ( String [] lista , String buscado ) {
for ( int i = 0; i < lista.length ; i ++){
if( lista [i].equals( buscado )){
return i;}
}
return -1;
}
B´
usqueda Binaria
Restricci´on
• Loselementos de la lista deben estar previamente ordenados.
Algoritmo (asumiento orden ascendente)
1. Si el largo de la lista es 0 el programa termina.
2. Se calcula el ´ındice del elemento central.
3. Se compara el elemento buscado con el elemento central.
a) Si el elemento buscado es mayor al central, se vuelve al paso 1, pero con la sublista [central + 1, largo].
b) Si el elemento buscado es menor alcentral, se vuelve al paso 1, pero con la sublista [0, central − 1].
c) Si el elemento buscado es igual al central se retorna el ´ındice de este. Encontr´o el elemento.
Declaraci´
on 2 public int busquedaBinaria ( String [ ] lista , String buscado ) {
int inicial = 0;
int final = lista.length - 1;
while ( inicial < final ) {
int central = ( inicial + final )/2;
if( buscado.compareTo(lista[central]) >0){
inicial = central + 1; }
else if( buscado.compareTo(lista [central]) < 0){
final = central - 1; }
else{ return central; }
}
return -1;
}
Ordenaci´
on
Dado un arreglo con N elementos, ordenarlo en funci´on de alguna caracter´ıstica com´
un entre ellos. Por ejemplo, escribir los valores en orden creciente (o decreciente).
Existen una gran cantidad de algoritmos que se diferencian en su...