trnsformacion de Ip

´
Pontificia Universidad Catolica de Chile
Escuela de Ingenier´
ıa
´
Departamento de Ciencia de la Computacion
IIC1103 — Introducci´n a la Programaci´n
o
o

Cap´
ıtulo 7: Ordenaci´n y B´squeda
o
u
Resumen te´rico
o
La operaci´n de ordenar consisten seleccionar de un conjunto de datos y ordenarlos bajo alg´ n determinado
o
u
criterio. Por ejemplo, cada elemento del conjunto dedatos de una gu´ telef´nica tiene un nombre, una
ıa
o
direcci´n y un n´mero de tel´fono; la gu´ telef´nica est´ dispuesta en orden alfab´tico de nombres; los
o
u
e
ıa
o
a
e
elementos num´ricos se pueden ordenar en orden creciente o decreciente de acuerdo al valor num´rico del
e
e
elemento. En terminolog´ de ordenaci´n, el elemento por el cual est´ ordenado un conjunto de datos (o seıa
o
a
est´ buscando) se denomina clave.
a
Una colecci´n de datos (estructura) puede ser almacenada por ejemplo en un array (vector o tabla). Una
o
estructura se dice que est´ ordenada por la clave k si la lista est´ en orden ascendente o descendente con
a
a
respecto a esta clave. La colecci´nde datos se dice que est´ en orden ascendente si: i < jimplicaquek[i] jimplicaquek[i] 0){inicial = central + 1; }
else if( buscado.compareTo(lista [central]) < 0){
final = central - 1; }
else{ return central; }
}
return -1;
}
Ordenaci´n
o
Dado un arreglo con N elementos, ordenarlo en funci´n de alguna caracter´
o
ıstica com´n entre ellos. Por ejemu
plo, escribir los valores en orden creciente (o decreciente).
Existen una gran cantidad de algoritmos que se diferencian en surapidez y complejidad. Nosotros veremos
dos:
Ordenaci´n por selecci´n.
o
o
Ordenaci´n por burbuja.
o
Ordenaci´n por inserci´n.
o
o

IIC1103 – Cap´
ıtulo 7: Ordenaci´n y B´squeda
o
u

2

Ordenaci´n por selecci´n
o
o
Si quisieramos ordenar ascendentemente:
1. Se busca el menor elemento.
2. Este elemento se cambia con el elemento en el primer lugar de la lista.
3. Se vuelve alpaso 1, pero ahora la b´squeda comienza en el siguiente elemento.
u
Se conoce como Selection Sort.
Ordenaci´n por selecci´n
o
o
Declaraci´n 3 public void ordenacionPorSeleccion ( int [] lista ) {
o
for ( int i = 0; i < lista.length -1; i ++) {
// Buscamos el menor
int menor = i;
for ( int j = i + 1; j < lista.length ; j + +){
if( lista [j] < lista [menor]){ menor = j; }
// Cambiamos elmenor
int aux = lista [i];
lista [i] = lista [menor];
lista [menor] = aux ;
}
}
}
Ordenaci´n por burbuja
o
Si quisieramos ordenar ascendentemente:
1. Se busca el menor elemento.
2. Este elemento se cambia con el elemento en el primer lugar de la lista.
3. Se vuelve al paso 1, pero ahora la b´squeda comienza en el siguiente elemento.
u
Se conoce como Buble Sort.
Ordenaci´n porburbuja
o
Declaraci´n 4 public void ordenacionPorBurbuja ( int [] lista ) {
o
for ( int i = 1; i < lista . length ; i ++) {
for ( int j = i - 1; j ≥ 0; j - -) {
if( lista [j +1] < lista [j]) {
// Intercambio
int aux = lista [j +1];
lista [j +1] = lista [j];
lista [j] = aux ;
}
else { break; }
}
}
}
IIC1103 – Cap´
ıtulo 7: Ordenaci´n y B´squeda
o
u

3

Ordenaci´n por inserci´n
oo
1. Inicialmente se tiene un solo elemento, que obviamente es un conjunto ordenado.
2. Despu´s, cuando hay k elementos ordenados de menor a mayor, se toma el elemento k+1 y se compara
e
con todos los elementos ya ordenados
3. deteni´ndose cuando se encuentra un elemento menor (todos los elementos mayores han sido desplazae
dos una posici´n a la derecha).
o
4. En este punto se inserta elelemento k+1 debiendo desplazarse los dem´s elementos.
a
Se conoce como Insertion Sort.
Declaraci´n 5 public void insertSort (int[] v) {
o
for (int i=1; i < v.length; i + +) {
int aux = v[i];
int j;
for (j=i-1; j>=0 && v[j] > aux; j - -){
v[j+1] = v[j];}
v[j+1] = aux;
}
}

IIC1103 – Cap´
ıtulo 7: Ordenaci´n y B´squeda
o
u

4

Ejemplos
Problema 1: Patentes
Enunciado
Las...