PDF de programación - Tema 1. Ordenación, búsqueda e intercalación interna - Fundamentos de Programación II

Fundamentos de Programación II

Tema 1. Ordenación, búsqueda e
intercalación interna

Luis Rodríguez Baena ([email protected])

Universidad Pontificia de Salamanca
Escuela Superior de Ingeniería y Arquitectura

Ordenación interna

 Reorganización de un conjunto dado de objetos en una secuencia

especificada.
● Permutará las posiciones de los elementos de forma que sus claves formen una

secuencia creciente.

● La ordenación se suele realizar sobre un conjunto de registros con un campo clave

que identifique el registro.
 Dados los registros r1, r2,…, rn con valores de clave k1, k2,…, kn debe resultar la misma secuencia

de registros en orden ri1

, ri2,…, rin tal que ki1≤ ki2≤… kin.

● Una clave o un campo clave es el dato a partir del cual se va a realizar la

ordenación.
 Por ejemplo, si queremos ordenar una lista de personas a partir de su DNI, el campo clave será el

DNI.

 Los métodos se pueden clasificar según su eficiencia.

● La eficiencia se puede medir en base al número de comparaciones y movimientos

que realizan.
 Métodos directos (n2 comparaciones de claves).
 Métodos no directos (n log n comparaciones de claves).

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

2

Ordenación interna (II)

Para todos los métodos se va a suponer que exixten

estas declaraciones iniciales…
const
tipos

numElementos = ... //Número de elementos del array a ordenar
//tipoElemento podrá ser cualquier tipo de dato simple, por ejemplo
entero = tipoElemento
array[0..numElementos] de tipoElemento = vector

procedimiento intercambiar(ref tipoElemento : a,b)
var
inicio

tipoElemento : aux
aux  a
a  b
b  aux

fin_procedimiento

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

3

Ordenación por intercambio directo (burbuja)

i = 1
6
10
3
20
14
16
12
15

i = 2
3
6
10
12
20
14
16
15

i = 3
3
6
10
12
14
20
15
16

i = 4
3
6
10
12
14
15
20
16

i = 5
3
6
10
12
14
15
16
20

i = 6
3
6
10
12
14
15
16
20

i = 7
3
6
10
12
14
15
16
20

procedimiento OrdenaciónIntercambioDirecto(ref vector:v;valor entero:n)
var
inicio

entero : i,j
desde i  1 hasta n-1 hacer

desde j  n hasta i+1 incremento -1 hacer

si v[j-1] > v[j]entonces
fin_si
fin_desde

intercambiar(v[j],v[j-1])

fin_desde

fin_procedimiento

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

4

Ordenación por intercambio directo (II)

procedimiento OrdenaciónIntercambioDirecto (ref vector:v;
var

valor entero : n)

inicio

entero : i,j
lógico : ordenado
i  0
repetir

fin_si
fin_desde

hasta_que ordenado

fin_procedimiento

i  i + 1
ordenado  verdad
desde j  n hasta i+1 incremento -1 hacer

si v[j-1] > v[j]entonces

intercambiar(v[j],v[j-1])
ordenado  falso

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

5

Ordenación por selección directa

 Busca el primer elemento

menor y lo coloca en la
primera posición.

 Repite el proceso con los

siguientes elementos del array.
 No considera la relación entre

los elementos, es decir, no
considera que los elementos ya
pueden estar colocados.
● En cada paso sólo se considera

uno de ellos.

i = 1
i = 1
i = 1

i = 2
i = 2
i = 2

i = 3
i = 3
i = 3

i = 4
i = 4
i = 4

i = 5
i = 5
i = 5

i = 6
i = 6
i = 6

i = 7
i = 7
i = 7

1
1
1
6
6
6

3
3
3

3
3
3

3
3
3

3
3
3

3
3
3

3
3
3

3
3
3

min
3
3
3
3
3
3

min
6
6
6

min
10
10
10

10
10
10

10
10
10

10
10
10

10
10
10

10
10

2
2
2
10
10
10

10
10
10

6
6
6

6
6
6

6
6
6

6
6
6

6
6
6

6
6

4
4
4
20
20
20

5
5
5
14
14
14

6
6
6
16
16
16

7
7
7
12
12
12

20
20
20

14
14
14

16
16
16

12
12
12

20
20
20

20
20
20

12
12
12

12
12
12

12
12
12

12
12

14
14
14

14
14
14

14
14
14

14
14
14

14
14
14

14
14

16
16
16

16
16
16

16
16
16

16
16
16

15
15
15

15
15

12
12
12

min
12
12
12

20
20
20

20
20
20

20
20
20

16
16

8
8
8
15
15
15

15
15
15

15
15
15

15
15
15

15
15
15

min
15
15
15

min
16
16
16

20
20

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

6

Ordenación por selección directa (II)

procedimiento OrdenaciónSelecciónDirecta(ref vector:v;
var
inicio

entero : i,j,min
desde i  1 hasta n-1 hacer

valor entero : n)

min  i
desde j  i+1 hasta n hacer
si v[j] < v[min] entonces
fin_si
fin_desde
intercambiar(v[i],v[min])

min  j

fin_desde

fin_procedimiento

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

7

Ordenación por inserción directa

 Comprueba la colocación

del primer y segundo
elemento.

 A partir del elemento 2, se

desplazan todos los
elementos mayores una
posición a la derecha para
“abrir hueco”.

 Coloca el nuevo elemento
en la posición del primer
elemento menor o igual.

 Mejora su eficiencia

utilizando un centinela.

0
0
0

10
10
10

i = 2
i = 2
i = 2

i = 3
i = 3
i = 3

3
3
3

i = 4
i = 4
i = 4

20
20
20

i = 5
i = 5
i = 5

14
14
14

i = 6
i = 6
i = 6

16
16
16

i = 7
i = 7
i = 7

12
12
12

i = 8
i = 8

15
15

15
15

1
1
1

6
6
6

6
6
6

3
3
3

3
3
3

3
3
3

3
3
3

3
3
3

3
3

2
2
2

10
10
10

10
10
10

6
6
6

6
6
6

6
6
6

6
6
6

6
6

6
6

3
3
3

3
3
3

3
3
3

4
4
4

20
20
20

5
5
5

14
14
14

6
6
6

16
16
16

7
7
7

12
12
12

8
8
8

15
15
15

20
20
20

14
14
14

16
16
16

12
12
12

15
15
15

10
10
10

20
20
20

14
14
14

16
16
16

12
12
12

15
15
15

10
10
10

20
20
20

14
14
14

16
16
16

12
12
12

15
15
15

10
10
10

14
14
14

20
20
20

16
16
16

12
12
12

15
15
15

10
10
10

14
14
14

16
16
16

20
20
20

12
12
12

15
15
15

10
10

12
12

14
14

16
16

20
20

15
15

10
10

12
12

14
14

15
15

16
16

20
20

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

8

Ordenación por inserción directa (II)

procedimiento OrdenaciónInserciónDirecta(ref vector:v;valor entero : n)
//El vector v tiene elementos entre 1 y n
var
inicio

entero : i,j
desde i  2 hasta n hacer

//Se almacena el elemento a insertar (v[i]) en la posición 0
//del array para que actúe como centinela
v[0]  v[i]
j  i – 1
//Se desplazan todos los elementos mayores que v[0]
//y situados a su izquierda una posición a la derecha
mientras v[j] > v[0] hacer

v[j+1]  v[j]
j  j – 1

fin_mientras
//En la posición siguiente al primer elemento menor o igual
//se inserta el elemento v[0]
v[j+1]  v[0]

fin_desde

fin_procedimiento

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

9

Ordenación por incrementos decrecientes o
método de Shell

 Basado en la inserción directa.
 En lugar de comparar elementos adyacentes,

la comparación no se realiza siempre con
elementos continuos.
● La distancia entre elementos a comprar decrece

a partir de la mitad del número de elementos.
 Repite varias veces el método de inserción

directa y en cada repetición modifica la
distancia entre los elementos.

 La mejora radica en que cuando la distancia

es grande, se tarda poco en realizar la
pasada y la lista queda medio ordenada.

 Cuando la distancia es corta, aunque

aumenta el número de pasadas, la lista ya
está medianamente ordenada.
● Al final, se compararán elementos adyacentes,
pero al estar la lista ordenada se deberán hacer
pocos intercambios entre elementos.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

10

Ordenación por incrementos decrecientes (II)

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

11

Ordenación por incrementos decrecientes (III)

inicio

procedimiento OrdenaciónShell(ref vector:v; valor entero : n)
var

//incr es la separación entre elementos a comparar
entero : i,j,incr
tipoElemento : aux
//Inicialmente la separación entre elementos a comparar es n/2
incr  n div 2
//Se repite el método de ordenación por inserción mientras
//que la separación sea mayor que 0
mientras incr > 0 hacer
desde i  incr + 1 hasta n hacer

aux  v[i]
j  i - incr
//Se comparan el elemento auxiliar con el situado
//incr posiciones más a la derecha (elemento v[j])
mientras j>=1 y v[j]>aux hacer

v[j+incr]  v[j]
j  j-incr
fin_mientras
v[j+incr]  aux
fin_desde
//Una vez que la lista está ordenada entre los elementos
//situados a incr posiciones, el incremento decrece
incr  incr div 2

fin_mientras

fin_procedimiento

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

12

Búsqueda

 Localizar un elemento dado entre una lista de ellos para

obtener su posición.
● Normalmente se buscará en arrays paralelos o arrays de registros

a partir de un campo clave.
 El campo clave normalmente será único.

● Las funciones de búsqueda para claves únicas devolverán un

número entero con la posición del elemento y un centinela
(normalmente 0) en el caso de que no lo hayan encontrado.
 Para la búsqueda de claves repetidas se deben utilizar métodos

alternativos.
○ En ese caso un procedimiento devolverá un array con las posiciones en las

que se encuentra ese elemento.

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

13

Búsqueda lineal (secuencial)

Buscar secuencialmente los elementos (uno detrás de

otro) hasta encontrarlo o llegar al final de la lista.
entero función Buscar(valor vector:v;valor tipoElemento:el;
var
inicio

valor entero:n)

entero: i
i  1
mientras (el <> v[i]) y (i < n) hacer
i  i + 1
fin_mientras
si el = v[i] entonces
si_no
fin_si

devolver(i)
devolver(0)

fin_función

Universidad Pontificia de Salamanca. Escuela Superior de Ingeniería y Arquitectura
(CC) Luis Rodríguez Baena, 2013

14

Búsqueda lineal con centinela

 Busca desde el último al primer elemento hasta encontrarlo.