Download - Busqueda y Ordenacion
-
7/24/2019 Busqueda y Ordenacion
1/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 1
BSQUEDA SECUENCIAL
- Se utiliza en arreglos ordenados o desordenados.- Consiste en recorrer el arreglo elemento por elemento, comparndolos con el dato
buscado. Este proceso finaliza cuando se encuentra el valor o cuando ya no existen mselementos por recorrer.
int busqsecuencial( int a[N], int x ){
int i;i = 0;while ( i < N )
if ( a[i] == x )return i;
else
i++;return -1;}
BUSQUEDA BINARIA
- Se utiliza en arreglos ordenados.
- Consiste en reducir el espacio de bsqueda a la mitad cada vez que la comparacin delelemento central con el dato buscado resulte falso.
int busqbinaria( int a[N], int x ){int c,p,u;p = 0;u = N-1;while ( p
-
7/24/2019 Busqueda y Ordenacion
2/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 2
Ejemplo de Bsqueda Binaria
Buscar el valor 32en el siguiente arreglo:
4 7 10 12 15
0 1 2 3 4
a 18 21 24 26 30
5 6 7 8 9
32 36 39 42 44
10 11 12 13 14
46 50 54 59 63
15 16 17 18 19
66
20
69 72 75 77
21 22 23 24
80
25
Inicialmente, el espacio de bsqueda es todo el arreglo, cuyo centro es el elemento 12:
4 7 10 12 15
0 1 2 3 4
a 18 21 24 26 30
5 6 7 8 9
32 36 39 42 44
10 11 12 13 14
46 50 54 59 63
15 16 17 18 19
66
20
69 72 75 77
21 22 23 24
80
25
p = 0 u = 25c = 12
Se compara 32 con a[12], como 32 es menor que 39, el nuevo espacio de bsqueda va del elemento 0 al elemento 11, cuyo centro es el
elemento 5:
4 7 10 12 15
0 1 2 3 4
a 18 21 24 26 30
5 6 7 8 9
32 36
10 11
p = 0 u = 11c = 5
-
7/24/2019 Busqueda y Ordenacion
3/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 3
Se compara 32 con a[5], como 32 es mayor a 18, el nuevo espacio de bsqueda va del elemento 6 al elemento 11, cuyo centro es el
elemento 8:
21 24 26 30
6 7 8 9
32 36
10 11
a
p = 6 u = 11c = 8
Se compara 32 con a[8], como 32 es mayor a 26, el nuevo espacio de bsqueda va del elemento 9 al elemento 11, cuyo centro es elelemento 10:
30
9
32 36
10 11
a
p = 9 u = 11
c = 10
Se compara 32 con a[10], como 32 es igual a 32, el dato buscado ha sido encontrado en la posicin 10.
-
7/24/2019 Busqueda y Ordenacion
4/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 4
ORDENACIN POR EL MTODO DE LA BURBUJA
void ord_burbuja( int a[N] ){int i,j,aux;for(i=0;i a[ 1 ] ? Si Intercambiar
18 27 20 11 9
0 1 2 3 4
a
j = 2 a[ 0 ] > a[ 2 ] ? No
j = 3 a[ 0 ] > a[ 3 ] ? Si Intercambiar
11 27 20 18 9
0 1 2 3 4
a
j = 3 a[ 0 ] > a[ 4 ] ? Si Intercambiar
-
7/24/2019 Busqueda y Ordenacion
5/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 5
9 27 20 18 11
0 1 2 3 4
a
i = 1
j = 2 a[ 1 ] > a[ 2 ] ? Si Intercambiar
9 20 27 18 11
0 1 2 3 4
a
j = 3 a[ 1 ] > a[ 3 ] ? Si Intercambiar
9 18 27 20 11
0 1 2 3 4
a
j = 4 a[ 1 ] > a[ 4 ] ? Si Intercambiar
9 11 27 20 18
0 1 2 3 4
a
i = 2
j = 3 a[ 2 ] > a[ 3 ] ? Si Intercambiar
9 11 20 27 18
0 1 2 3 4
a
j = 3 a[ 2 ] > a[ 4 ] ? Si Intercambiar
9 11 18 27 20
0 1 2 3 4
a
-
7/24/2019 Busqueda y Ordenacion
6/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 6
i = 3
j = 4 a[ 3 ] > a[ 4 ] ? Si Intercambiar
9 11 18 20 27
0 1 2 3 4
a
El arreglo ordenado es:
9 11 18 20 27
0 1 2 3 4
a
ORDENACIN POR EL MTODO DE SELECCION
void ord_seleccion( int a[N] ){
int i, j, aux, posmen;for(i=0;i
-
7/24/2019 Busqueda y Ordenacion
7/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 7
i = 0 posmen = 0
j = 1 a[ 1 ] < a[ 0 ] ? Si posmen = 1
j = 2 a[ 2 ] < a[ 1 ] ? No
j = 3 a[ 3 ] < a[ 1 ] ? Si posmen = 3
j = 4 a[ 4 ] < a[ 3 ] ? Si posmen = 4
Como i y posmen son distintos, se intercambian los elementos 0 y 4:
9 18 20 11 27
0 1 2 3 4
a
i = 1 posmen = 1
j = 2 a[ 2 ] < a[ 1 ] ? No
j = 3 a[ 3 ] < a[ 1 ] ? Si posmen = 3
j = 4 a[ 4 ] < a[ 3 ] ? No
Como i y posmen son distintos, se intercambian los elementos 1 y 3:
9 11 20 18 27
0 1 2 3 4
a
i = 2 posmen = 2
j = 3 a[ 3 ] < a[ 2 ] ? Si posmen = 3
j = 4 a[ 4 ] < a[ 3 ] ? No
Como i y posmen son distintos, se intercambian los elementos 2 y 3:
9 11 18 20 27
0 1 2 3 4
a
-
7/24/2019 Busqueda y Ordenacion
8/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 8
i = 3 posmen = 3
j = 4 a[ 4 ] < a[ 3 ] ? No
Como i y posmen son iguales, no se realiza ningn intercambio.
El arreglo ordenado es:
9 11 18 20 27
0 1 2 3 4
a
ORDENACIN POR EL MTODO SHELL
void ord_shell( int a[N] ){
int i, j, k, inc, aux;inc = N/2;while (inc>0){
for(i=inc;i= 0){
k = j + inc;if ( a[j]
-
7/24/2019 Busqueda y Ordenacion
9/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 9
Ejemplo de Ordenacin por el Mtodo de Shell
Ordenar el siguiente arreglo:
20 11 37 24 18
0 1 2 3 4
a 15 29 32 13
5 6 7 8
Este arreglo tiene N=9 elementos.
inc = N / 2 = 4
20 11 37 24 18
0 1 2 3 4
a 15 29 32 13
5 6 7 8
a[ 4 ] < a[ 0 ] ? Sise intercambian:
18 11 37 24 20
0 1 2 3 4
a 15 29 32 13
5 6 7 8
a[ 5 ] < a[ 1 ] ? Nono se intercambian:
18 11 37 24 20
0 1 2 3 4
a 15 29 32 13
5 6 7 8
a[ 6 ] < a[ 2 ] ? Sise intercambian:
18 11 29 24 20
0 1 2 3 4
a 15 37 32 13
5 6 7 8
a[ 7 ] < a[ 3 ] ? Nono se intercambian:
-
7/24/2019 Busqueda y Ordenacion
10/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 10
18 11 29 24 20
0 1 2 3 4
a 15 37 32 13
5 6 7 8
a[ 8 ] < a[ 4 ] ? Sise intercambian:
18 11 29 24 13
0 1 2 3 4
a 15 37 32 20
5 6 7 8
Como hubo intercambio, a[ 4 ] < a[ 0] ? Sise intercambian:
13 11 29 24 18
0 1 2 3 4
a 15 37 32 20
5 6 7 8
inc = inc / 2 = 2
13 11 29 24 18
0 1 2 3 4
a 15 37 32 20
5 6 7 8
a[ 2 ] < a[ 0 ] ? Nono se intercambian:
13 11 29 24 18
0 1 2 3 4
a 15 37 32 20
5 6 7 8
a[ 3 ] < a[ 1 ] ? Nono se intercambian:
13 11 29 24 18
0 1 2 3 4
a 15 37 32 20
5 6 7 8
-
7/24/2019 Busqueda y Ordenacion
11/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 11
a[ 4 ] < a[ 2 ] ? Sise intercambian:
13 11 18 24 29
0 1 2 3 4
a 15 37 32 20
5 6 7 8
Como hubo intercambio, a[ 2 ] < a[ 0 ] ? Nono se intercambian:
13 11 18 24 29
0 1 2 3 4
a 15 37 32 20
5 6 7 8
a[ 5 ] < a[ 3 ] ? Sise intercambian:
13 11 18 15 29
0 1 2 3 4
a 24 37 32 20
5 6 7 8
Como hubo intercambio, a[ 3 ] < a[ 1 ] ? Nono se intercambian:
13 11 18 15 29
0 1 2 3 4
a 24 37 32 20
5 6 7 8
a[ 6 ] < a[ 4 ] ? Nono se intercambian:
13 11 18 15 29
0 1 2 3 4
a 24 37 32 20
5 6 7 8
a[ 7 ] < a[ 5 ] ? Nono se intercambian:
-
7/24/2019 Busqueda y Ordenacion
12/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 12
13 11 18 15 29
0 1 2 3 4
a 24 37 32 20
5 6 7 8
a[ 8 ] < a[ 6 ] ? Sise intercambian:
13 11 18 15 29
0 1 2 3 4
a 24 20 32 37
5 6 7 8
Como hubo intercambio, a[ 6 ] < a[ 4 ] ? Sise intercambian:
13 11 18 15 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
Como hubo intercambio, a[ 4 ] < a[ 2 ] ? Nono se intercambian:
13 11 18 15 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
inc = inc / 2 = 1
13 11 18 15 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 1 ] < a[ 0 ] ? Sise intercambian:
11 13 18 15 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
-
7/24/2019 Busqueda y Ordenacion
13/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 13
a[ 2 ] < a[ 1 ] ? Nono se intercambian:
11 13 18 15 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 3 ] < a[ 2 ] ? Sise intercambian:
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
Como hubo intercambio, a[ 2 ] < a[ 1 ] ? Nono se intercambian:
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 4 ] < a[ 3 ] ? Nono se intercambian:
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 5 ] < a[ 4 ] ? Nono se intercambian:
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 6 ] < a[ 5 ] ? Nono se intercambian:
-
7/24/2019 Busqueda y Ordenacion
14/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 14
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 7 ] < a[ 6 ] ? Nono se intercambian:
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
a[ 8 ] < a[ 7 ] ? Nono se intercambian:
El arreglo ordenado es:
11 13 15 18 20
0 1 2 3 4
a 24 29 32 37
5 6 7 8
ORDENACIN POR EL MTODO QUICKSORT
void ord_quicksort( int a[N], int pri, int ult ){
int i, j, c, piv, aux;i = pri; j = ult; c = (pri + ult)/2;piv = a[c];do{ while( a[i] < piv )
i++;while( a[j] > piv )
j--;if (i
-
7/24/2019 Busqueda y Ordenacion
15/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 15
if ( pri < j )ord_quicksort(a,pri,j);
if ( i < ult )ord_quicksort(a,i,ult);
}
Ejemplo de Ordenacin por el Mtodo Quicksort
Ordenar el siguiente arreglo:
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
Se elige como pivote el elemento central: a[ 8 ] = 50.
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
i = 0 j = 16
a[ 0 ] < 50 ? Si, entonces i = i + 1:
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
i = 1 j = 16
a[ 1 ] < 50 ? Si, entonces i = i + 1:
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
i = 2 j = 16
a[ 2 ] < 50 ? No, entonces i no se incrementa
a[ 16 ] > 50 ? Si, entonces j = j -1:
-
7/24/2019 Busqueda y Ordenacion
16/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 16
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
i = 2 j = 15
a[ 15 ] > 50 ? Si, entonces j = j -1:
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
i = 2 j = 14
a[ 14 ] > 50 ? Si, entonces j = j -1:
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 42 61
10 11 12 13 14
98 57
15 16
i = 2 j = 13
a[ 13 ] > 50 ? No, entonces j no se decrementa. Se deben intercambiar los elementos i y j:
44 32 66 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 10 42 61
10 11 12 13 14
98 57
15 16
i = 2 j = 13
Luego del intercambio, i = i + 1 y j = j -1:
44 32 42 48 15
0 1 2 3 4
a 71 90 16 50 40
5 6 7 8 9
32 36 100 66 61
10 11 12 13 14
98 57
15 16
i = 3 j = 12
a[ 3 ] < 50 ? Si, entonces i = i + 1:
-
7/24/2019 Busqueda y Ordenacion
17/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 17
44 32 42 48 15
0 1 2 3 4
71 90 16 50 40
5 6 7 8 9
32 36 100 66 61
10 11 12 13 14
98 57
15 16
i = 4 j = 12
a
a[ 4 ] < 50 ? Si, entonces i = i + 1:
44 32 42 48 15
0 1 2 3 4
71 90 16 50 40
5 6 7 8 9
32 36 100 66 61
10 11 12 13 14
98 57
15 16
i = 5 j = 12
a
a[ 5 ] < 50 ? No, entonces i no se incrementa
a[ 12 ] > 50 ? Si, entonces j = j -1:
44 32 42 48 15
0 1 2 3 4
71 90 16 50 40
5 6 7 8 9
32 36 100 66 61
10 11 12 13 14
98 57
15 16
i = 5 j = 11
a
a[ 11 ] > 50 ? No, entonces j no se decrementa. Se deben intercambiar los elementos i y j:
44 32 42 48 15
0 1 2 3 4
71 90 16 50 40
5 6 7 8 9
32 36 100 66 61
10 11 12 13 14
98 57
15 16
i = 5 j = 11
a
Luego del intercambio, i = i + 1 y j = j -1:
44 32 42 48 15
0 1 2 3 4
36 90 16 50 40
5 6 7 8 9
32 71 100 66 61
10 11 12 13 14
98 57
15 16
i = 6 j = 10
a
a[ 6 ] < 50 ? No, entonces i no se incrementaa[ 10 ] > 50 ? No, entonces j no se decrementa
Se deben intercambiar los elementos i y j:
-
7/24/2019 Busqueda y Ordenacion
18/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
Mag. Hilmar Hinojosa Lazo 18
44 32 42 48 15
0 1 2 3 4
36 90 16 50 40
5 6 7 8 9
32 71 100 66 61
10 11 12 13 14
98 57
15 16
i = 6 j = 10
a
Luego del intercambio, i = i + 1 y j = j -1:
44 32 42 48 15
0 1 2 3 4
36 32 16 50 40
5 6 7 8 9
90 71 100 66 61
10 11 12 13 14
98 57
15 16
i = 7 j = 9
a
a[ 7 ] < 50 ? Si, entonces i = i +1:
44 32 42 48 15
0 1 2 3 4
36 32 16 50 40
5 6 7 8 9
90 71 100 66 61
10 11 12 13 14
98 57
15 16
i = 8
j = 9
a
a[ 8 ] < 50 ? No, entonces i no se incrementa
a[ 9 ] > 50 ? No, entonces j no se decrementa
Se deben intercambiar los elementos i y j:
44 32 42 48 15
0 1 2 3 4
36 32 16 50 40
5 6 7 8 9
90 71 100 66 61
10 11 12 13 14
98 57
15 16
i = 8
j = 9
a
Luego del intercambio, i = i + 1 y j = j -1:
44 32 42 48 15
0 1 2 3 4
36 32 16 40 50
5 6 7 8 9
90 71 100 66 61
10 11 12 13 14
98 57
15 16
j = 8
i = 9
-
7/24/2019 Busqueda y Ordenacion
19/19
UNMSM Facultad de Ingeniera Industrial
ALGORITMOS Y PROGRAMACION
M Hil Hi j L 19
Se ha logrado colocar los valores menores al pivote ( 50 ) en los elementos del 0 al 8 y los
valores mayores o iguales al pivote en los elementos del 9 al 16.
Ahora se tiene que ordenar por separado estas dos regiones del arreglo:
ord_quicksort( a , 0 , 8 );
44 32 42 48 15
0 1 2 3 4
36 32 16 40
5 6 7 8
a
i = 0 j = 8
ord_quicksort( a , 9 , 16 );
50
9
90 71 100 66 61
10 11 12 13 14
98 57
15 16
a
i = 9 j = 16