PDF de programación - Tema 6: Algoritmos de búsqueda y ordenación

Departamento de Informática
Universidad de Valladolid
Campus de Segovia
______________________

TEMA 6:

ALGORITMOS DE

BÚSQUEDA Y
ORDENACIÓN

Prof. José Vicente Álvarez Bravo

ALGORITMOS DE BÚSQUEDA

Y ORDENACIÓN

• Algoritmos de búsqueda en arrays

– Secuencial
– Secuencial ordenada
– Binaria

• Ordenación de vectores

– Selección directa
– Inserción directa
– Intercambio directo
– Ordenación rápida (Quick Sort)
– Ordenación por mezcla (Merge Sort)

• Algoritmos de búsqueda y ordenación en
archivos

ALGORITMOS DE BÚSQUEDA

EN ARRAYS

• Surgen de la necesidad de conocer tanto si

un dato se encuentra o no dentro de una
colección como de la posición que ocupa.

• Búsqueda(vector,elemento):

– i∈{1,....,n} si existe tal elemento
– 0

en otro caso

• Estructura de datos:

const

N=100;

type

tIntervalo=0..N;
tvector=array[1..N] of tElem {tipo ordinal}

ALGORITMOS DE BÚSQUEDA

EN ARRAYS

• Algoritmos de búsqueda:

– Búsqueda secuencial
– Búsqueda secuencial ordenada
– Búsqueda binaria

BÚSQUEDA SECUENCIAL

• La búsqueda secuencial consiste en

comparar secuencialmente el elemento
deseado con los valores contenidos en las
posiciones 1,....,n.

• El proceso termina cuando o bien

encontramos el elemento o bien se alcanza
el final del vector.

• Un primer nivel de diseño:

ind:=0
buscar elemento en vector
si vector[ind]=elemento entonces

busquedasecuencial:=ind

sino

busquedasecuencial:=0

BÚSQUEDA SECUENCIAL,
IMPLEMENTACIÓN EN PASCAL

FUNCTION Busquedasec(v:tvector ; elem:telem):tIntervalo;
{Dev. 0 si el elemento no está en ‘v’ o i si v[ì]=elem}

VAR

i:tIntervalo;

BEGIN
i:=0;
repeat

i:=i+1;

until (v[i]=elem) or (i=N);
if v[i]=elem then

else

busquedasec:=i

busquedasec:=0

END; {busquedasec}

Este algoritmo en el peor de los casos es de orden O(n).

BÚSQUEDA SECUENCIAL

ORDENADA

• El algoritmo anterior puede ser mejorado si
el vector ‘v’ esta ordenado (i.e. Creciente).

• De esta forma si durante la búsqueda se

alcanza una componente con mayor valor
que ‘elem’, podremos asegurar que no se
encuentra dentro de la colección.

BÚSQUEDA SECUENCIAL

ORDENADA,

IMPLEMENTACIÓN EN PASCAL

FUNCTION Busquedasecord(v:tvector ; elem:telem):tIntervalo;
{Dev. 0 si el elemento no está en ‘v’ o i si v[ì]=elem}

VAR

i:tIntervalo;

BEGIN
i:=0;
repeat

i:=i+1;

until (v[i]≥elem) or (i=N);
if v[i]=elem then

else

busquedasecord:=i

busquedasecord:=0

END; {Busquedasecord}

Este algoritmo en el peor de los casos es de orden O(n).

BÚSQUEDA BINARIA

• El hecho de que el vector este ordenado se
puede, también, aprovechar para conseguir
una mayor eficiencia planteando el
siguiente algoritmo.

– Comparar ‘elem’ con el elemento central del

vector. Si este es el elemento buscado se
finaliza. Si no se sigue buscando en la mitad del
vector que determine la relación entre el valor
del elemento central y el buscado.

– Este algoritmo finaliza cuando se localiza el

elemento o se termina el vector.

• Debido a que el vector es dividido
sucesivamente en dos se denomina
búsqueda binaria.

BÚSQUEDA BINARIA,
IMPLEMENTACIÓN EN PASCAL

FUNCTION Busquedabinaria(v:tvector ; elem:telem):tIntervalo;
{Prec. V esta ordenado crecientemente}
{Dev. 0 si el elemento no está en ‘v’ o i si v[ì]=elem}
VAR

einf,esup,posmed:tIntervalo;
encontrado:boolean;

BEGIN

einf:=1; esup:=N; encontrado:=false;
while not encontrado and (esup≥einf) do begin

posmed:=(esup+einf) DIV 2;
if elem=v[posmed] then

encontrado:=true

else if elem>v[posmed] then

else

einf:=postmed+1

esup:=postmed-1

end {while}
if encontrado then

busquedabinaria:=posmed

else

busquedabinaria:=0

END; {Busquedabinaria}

BÚSQUEDA BINARIA

• La complejidad algorítmica de la búsqueda

binaria es:

Si

2k≤ N≤2k+1

entonces:

T(n) ≤T(2k+1)

En el peor de los casos:
T(n)≈O[logN]

N ≤ 2k+1=22k
logN ≤ log2k+1=k+1

ORDENACIÓN DE VECTORES

• Como se ha presentado con anterioridad,

disponer de una colección de datos
ordenados facilita la operación de
búsqueda. A continuación se presentan
algunos de los algoritmos de ordenación
más frecuentes:

– Algoritmos cuadráticos:

• Selección directa
• Inserción directa
• Intercambio directo

– Algoritmos avanzados de búsqueda:

• Algoritmo rápido (Quick Sort)
• Algoritmo de mezcla (Merge Sort)

ORDENACIÓN DE VECTORES

– Algoritmos cuadráticos:

• Selección directa
• Inserción directa
• Intercambio directo

– Algoritmos avanzados de búsqueda:

• Algoritmo rápido (Quick Sort)
• Algoritmo de mezcla (Merge Sort)

SELECCIÓN DIRECTA

• Procedimiento: Recorre el vector y

selecciona en cada uno de los recorridos el
menor elemento para situarlo en su lugar
correspondiente.

SELECCIÓN DIRECTA

– 1. Se sitúa en v[1] el menor elemento de entre

v[1],...,v[n]. Para ello se intercambian los
valores de v[1] y v[i] {v[i]=min(v)}

4 5 7 1 9 8 2

– 2. Se sitúa en v[2] el menor elemento de entre

v[2],...,v[n]. Para ello se intercambian los
valores de v[2] y v[i] {v[i]=min(v)}

1 5 7 4 9 8 2

– (n-1). Se sitúa en v[n-1] el menor elemento de
entre v[n-1] y v[n]. Para ello se intercambian
los valores de v[n-1] y v[n].

1 2 4 5 7 8 9

SELECCIÓN DIRECTA,
IMPLEMENTACIÓN EN PASCAL

PROCEDURE Selecciondirecta( var v:tvector);
{Efecto. Se ordena ‘v’ ascendentemente}
VAR

i, j,posmenor:tIntervalo;
valmenor,aux:telem;

BEGIN

for i:=1 to N-1 do begin

valmenor:=v[i]
posmenor:=i
for j:=i+1 to N do

Busca el menor
elemento de entre

i+1,....,N

if v[j]<valmenor then begin

valmenor:=v[j];
posmenor:=j

end; {if }

if posmenor<>i then begin

aux:=v[i];
v[i]:=v[posmenor];
v[posmenor]:=aux

end {if}


end{for i}

END; {Selecciondirecta}

Intercambio si posmenor

es diferente de i

INSERCIÓN DIRECTA

• Procedimiento: Recorre el vector ‘v’

insertando el elemento v[i] en su lugar
correcto entre los ya ordenados.

INSERCIÓN DIRECTA

– 1. Se considera v[1] como primer elemento.

– 2. Se inserta v[2] en su posición

correspondiente en relación a v[1] y v[2].

– 3. Se inserta v[3] en su posición

correspondiente en relación a v[1], v[2] y v[3].

– i. Se inserta v[i] en su posición correspondiente

en relación con v[1],...,v[i].

– n. Se repite la operación con el último elemento

del vector.

INSERCIÓN DIRECTA,
IMPLEMENTACIÓN EN PASCAL

PROCEDURE Inserciondirecta( var v:tvector);
{Efecto. Se ordena ‘v’ ascendentemente}
VAR

i, j:tIntervalo;
aux:telem;

BEGIN

for i:=2 to N do begin

aux:=v[i]
j:=i-1
while (j≥1) and (v[j]>aux) do begin

v[j+1]:=v[j];
j:=j-1

Desplazamiento del

menor valor

end; {while}
v[j+1]:=aux

end {for}

END; {inserciondirecta}

Colocación del valor

en su lugar correspondiente

INTERCAMBIO DIRECTO

• Procedimiento: Recorre el vector ‘v’
buscando el menor elemento desde la
última posición hasta la actual y lo inserta
en dicha posición.

INTERCAMBIO DIRECTO

– 1. Situar el elemento menor en la primera
posición. Para ello se compara el último
elemento con el penúltimo intercambiando los
valores si están en orden decreciente. Se repite
esta operación hasta llegar a la primera posición.
(el elemento menor se encuentra en la primera
posición).

– 2. Situar el segundo menor elemento en la

segunda posición. Para ello se procede como
antes finalizando al alcanzar al segunada
posición.

– 3. Repetir este proceso con la tercera,

cuarta,...,y con la enésima posición
intercambiando si procede en cada caso.

INTERCAMBIO DIRECTO,
IMPLEMENTACIÓN EN PASCAL

PROCEDURE Intercambiodirecto( var v:tvector);
{Efecto. Se ordena ‘v’ ascendentemente}
VAR

i, j:tIntervalo;
aux:telem;

BEGIN

for i:=1 to N-1 do

for j:=N downto i+1
{se busca el menor desde atrás y se sitúa en vi}

if v[j-1]>v[j] then begin

aux:=v[j];
v[j]:=v[j-1];
v[j-1]:=aux;

Intercambio

end; {if}
END; {intercambiodirecto}

ALGORITMOS DE BÚSQUEDA

AVANZADA

• Ordenación rápida (Quick sort)

• Ordenación por mezcla (Merge sort)

ORDENACIÓN RÁPIDA

– El algoritmo consiste en dividir el vector que se
desea ordenar en dos bloques. En el primero se
sitúan todos los elementos que son menores que
un cierto valor que se toma como referencia
(pivote), mientras que en segundo irían el resto.

– Este procedimiento se repite dividiendo a su vez

cada uno de estos bloques y repitiendo la
operación anteriormente descrita.

– La condición de parada se da cuando el bloque
que se desea ordenar está formado por un único
elemento (bloque ordenado).

– El esquema seguido por este algoritmo es el de

‘divide y venceras’.

ORDENACIÓN RÁPIDA,

PSEUDOCÓDIGO

Si v es de tamaño 1 entonces

el vector v ya está ordenado

sino

dividir v en dos bloques A y B
con todos los elementos de A menores que los
de B
fin {si}

Ordenar A y B usando Quick Sort
Devolver v ya ordenado.

• Donde dividir v en dos bloques se puede

refinar:

Elegir un elemento como pivote de v
para cada elemento de v hacer:

si el elemento es < pivote colocarlo en A
en otro caso situarlo en B.

ORDENACIÓN RÁPIDA,
IMPLEMENTACIÓN EN PASCAL

PROCEDURE Quicksort( var v:tvector);
{Efecto. Se ordena ‘v’ ascendentemente}

PROCEDURE Sortdesdehasta(var v:tvector;izq,der:tintervalo);
{Efecto. Se ordena ‘v[izq..der]’ ascendentemente}
{siguiente página}

BEGIN {Quicksort}

Sortdesdehasta(v,1,n);

END; {Quicksort}

ORDENACIÓN RÁPIDA,
IMPLEMENTACIÓN EN PASCAL

PROCEDURE Sortdesdehasta(var v:tvector;izq,der:tintervalo);
{Efecto. Se ordena ‘v[izq..der]’ ascendentemente}
VAR

i, j:tIntervalo;
p,aux:telem;

BEGIN

i:=izq; j:=der; p:=v[(izq+der) DIV 2];
while i<j do begin {se reorganizan los vectores}

while v[i]<p do
i:=i+1;
while p<v[j] do
j:=j-1;

if i≤ j then begin {intercambio de elementos}

aux:=v[i];
v[i]:=v[j];
v[j]:=aux;
i:=i+1; j:=j-1; {ajuste posiciones}

Intercambio

end; {if}

end; {while}

if izq<j then sortdesdehasta(v, izq, j);
if i<der then sortdesdehasta(v, i, der);
END; {Sortdesdehasta}

ORDENACIÓN RÁPIDA,

TRAZA PARA UN EJEMPLO

V=[0,5,15,9,11]
1. Sortdesdehasta(v,1,5)

p=v[3]=15

i=1 [0,5,15,9,11]
i=2 [0,5,15,9,11]
i=3 [0,5,15,9,11]
j=5 [0,5,15,9,11]
j=4 [0,5,11,9,15]

0<15
5<15
15 not <15
11 not >15
intercambio.