AyC Tema02 11 12

Algorítmica y Complejidad
curso 2011-2012

Algorítmica y Complejidad

Tema 2
Búsqueda y Ordenación

curso 20112011-2012

Algorítmica y Complejidad

Búsqueda y Ordenación interna

z Métodos de búsqueda:

– Datos sin ordenar: búsqueda secuencial
– Datos
D t ordenados:
d
d
bú
búsqueda
d bi
binaria
i

z Conceptos básicos de ordenación
z Tipos de ordenación:

– Por inserción: directa y binaria(dicotómica)
– Por selección: directa
– Por intercambio: burbuja, sacudida y quickSort

Búsqueda y Ordenación interna:

© 2011 Dpto. Organización y Estructura de la información

2

-1-

Algorítmica y Complejidad
curso 2011-2012
Algorítmica y Complejidad

Datos sin ordenar: búsqueda secuencial (I)
z Se emplea sobre vectores no ordenados
z Consiste en recorrer linealmente el vector hasta encontrar la
clavebuscada (o hasta llegar al final sin encontrar dicha
clave)
z Resultado de la búsqueda: índice de la posición del vector
que contiene la clave buscada
– Si la clave no aparece en el vector: devolver p.ej. -1

z Complejidad O(N/2): como media
media, el algoritmo necesitará
inspeccionar la mitad de las posiciones del vector hasta
encontrar la clave

Búsqueda y Ordenación interna:

3

Algorítmica yComplejidad

Datos sin ordenar: búsqueda secuencial (II)

indice

64

40

22

68

31

87

51

53

74

2

0

1

2

3

4

5

6

7

8

9

i
clave = 68

indice = 3

Búsqueda y Ordenación interna:

© 2011 Dpto. Organización y Estructura de la información

4

-2-

Algorítmica y Complejidad
curso 2011-2012
Algorítmica y Complejidad

Búsqueda secuencial: técnica del centinela (I)
z Esta técnica mejora elrendimiento de la búsqueda
secuencial
z Para su utilización es necesario un vector con una posición
adicional al final del mismo (centinela)
z Antes de empezar la búsqueda se inserta en la posición del
centinela la clave buscada
z Se lanza la búsqueda secuencial, con la seguridad de que se
va a encontrar la clave:
– Si aparece antes del centinela, se devuelve la posición
– Si aparece en laposición del centinela: devolver -1

Búsqueda y Ordenación interna:

5

Algorítmica y Complejidad

Búsqueda secuencial: técnica del centinela (II)

indice

64

40

22

68

31

87

51

53

74

2

70

0

1

2

3

4

5

6

7

8

9

10

i
clave = 70

indice = -1

Búsqueda y Ordenación interna:

© 2011 Dpto. Organización y Estructura de la información

6

-3-

Algorítmica y Complejidad
curso 2011-2012Algorítmica y Complejidad

Datos ordenados: búsqueda binaria (I)
z Aplicable sólo si los datos están ordenados
z Se emplean
p
dos índices ((izquierdo
q
y derecho)) q
que delimitan
el espacio del vector en el que se realiza la búsqueda
z Si los índices están “cruzados” (izquierdo > derecho), la
clave no está en el vector
z Se compara la clave buscada con el elemento central
– Si coincide con la clavebuscada, el algoritmo ha terminado
– Si la clave es menor: se vuelve a buscar en la mitad izquierda
– Si la clave es mayor: se vuelve a buscar en la mitad derecha

z En cada iteración el espacio de búsqueda se reduce a la
mitad: complejidad O(log N)
Búsqueda y Ordenación interna:

7

Algorítmica y Complejidad

Datos ordenados: búsqueda binaria (II)

clave = 64
indice = 6
2

22

31

40

51

53

64

6874

87

0

1

2

3

4

5

6

7

8

9

der

izq
centro
Búsqueda y Ordenación interna:

© 2011 Dpto. Organización y Estructura de la información

8

-4-

Algorítmica y Complejidad
curso 2011-2012
Algorítmica y Complejidad

Datos ordenados: búsqueda binaria (III)

clave = 59
indice = -1
2

22

31

40

51

53

64

68

74

87

0

1

2

3

4

5

6

7

8

9

der

izq
centro
Búsqueda y Ordenacióninterna:

9

Algorítmica y Complejidad

Conceptos básicos de Ordenación (I)
z Ordenar consiste en situar información de un modo concreto basándose
en un criterio determinado
z Situar
Si
iinformación
f
ió de
d un modo
d concreto iimplica
li reorganizar
i
un conjunto
j
de objetos o datos
z El conjunto de objetos o datos debe de ser organizable respecto al
criterio tomado
z Ordenar un grupo de datos...