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

Imágen de pdf Tema 1. Ordenación, búsqueda e intercalación interna - Fundamentos de Programación II

Tema 1. Ordenación, búsqueda e intercalación interna - Fundamentos de Programación IIgráfica de visualizaciones

Publicado el 24 de Septiembre del 2020
254 visualizaciones desde el 24 de Septiembre del 2020
651,7 KB
33 paginas
Creado hace 7a (06/02/2013)
Fundamentos de Programación II

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

Luis Rodríguez Baena (luis.rodriguez@upsam.es)

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.
  • Links de descarga
http://lwp-l.com/pdf18249

Comentarios de: Tema 1. Ordenación, búsqueda e intercalación interna - Fundamentos de Programación II (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad