Busqueda_y_ordenacion
Páginas: 14 (3261 palabras)
Publicado: 2 de noviembre de 2015
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
BÚSQUEDA SECUENCIAL
- Se utiliza en arreglos ordenados o desordenados.
- Consiste en recorrer el arreglo elemento por elemento, comparándolos con el dato
buscado. Este proceso finaliza cuando se encuentra el valor o cuando ya no existen más
elementos por recorrer.
int busqsecuencial( int a[N], int x )
{
int i;
i = 0;
while ( i
return i;
else
i++;
return -1;
}
BUSQUEDA BINARIA
- Se utiliza en arreglos ordenados.
- Consiste en reducir el espacio de búsqueda a la mitad cada vez que la comparación del
elemento 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<=u )
{
c = ( p + u ) / 2;
if ( a[c] == x)
return c;
else
if ( x < a[c] )
u =c -1 ;
else
p = c + 1;
}
return -1;
}
Mag. Hilmar Hinojosa Lazo
1
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
Ejemplo de Búsqueda Binaria
Buscar el valor 32 en el siguiente arreglo:
a
4
7
10
12
15
18
21
24
26
30
32
36
39
42
44
46
50
54
59
63
66
69
72
75
77
80
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2223
24
25
Inicialmente, el espacio de búsqueda es todo el arreglo, cuyo centro es el elemento 12:
a
4
7
10
12
15
18
21
24
26
30
32
36
39
42
44
46
50
54
59
63
66
69
72
75
77
80
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
p=0
c = 12
u = 25
Se compara 32 con a[12], como 32 es menor que 39, el nuevo espacio de búsquedava del elemento 0 al elemento 11, cuyo centro es el
elemento 5:
a
4
7
10
12
15
18
21
24
26
30
32
36
0
1
2
3
4
5
6
7
8
9
10
11
p=0
c= 5
u = 11
Mag. Hilmar Hinojosa Lazo
2
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
Se compara 32 con a[5], como 32 es mayor a 18, el nuevo espacio de búsqueda va del elemento 6 al elemento 11, cuyo centro esel
elemento 8:
a
21
24
26
30
32
36
6
7
8
9
10
11
p=6
c=8
u = 11
Se compara 32 con a[8], como 32 es mayor a 26, el nuevo espacio de búsqueda va del elemento 9 al elemento 11, cuyo centro es el
elemento 10:
a
30
32
36
9
10
11
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 posición 10.
Mag. Hilmar Hinojosa Lazo
3 UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
ORDENACIÓN POR EL MÉTODO DE LA BURBUJA
void ord_burbuja( int a[N] )
{
int i,j,aux;
for(i=0;i
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}
Ejemplo de Ordenación por el Método de la Burbuja
Ordenar el siguiente arreglo:
a
27
18
20
11
9
0
1
2
3
4
i=0
j=1
a[ 0 ] > a[ 1 ] ? Si Intercambiar
a
18
27
20
11
9
0
1
2
3
4
j=2
a[ 0 ] > a[ 2 ] ? No
j=3
a[ 0 ] > a[ 3 ] ? Si Intercambiar
a
j=3
11
27
20
18
9
0
1
2
3
4
a[ 0 ] > a[ 4 ] ? Si Intercambiar
Mag. Hilmar Hinojosa Lazo
4
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
a
9
27
20
18
11
0
1
2
3
4
i=1
j=2
a[ 1 ] > a[ 2 ] ? Si Intercambiar
a
j=3
2027
18
11
0
1
2
3
4
a[ 1 ] > a[ 3 ] ? Si Intercambiar
a
j=4
9
9
18
27
20
11
0
1
2
3
4
a[ 1 ] > a[ 4 ] ? Si Intercambiar
a
9
11
27
20
18
0
1
2
3
4
i=2
j=3
a[ 2 ] > a[ 3 ] ? Si Intercambiar
a
j=3
9
11
20
27
18
0
1
2
3
4
a[ 2 ] > a[ 4 ] ? Si Intercambiar
a
Mag. Hilmar Hinojosa Lazo
9
11
18
27
20
0
1
2
3
4
5
UNMSM – Facultad deIngeniería Industrial
ALGORITMOS Y PROGRAMACION
i=3
j=4
a[ 3 ] > a[ 4 ] ? Si Intercambiar
a
9
11
18
20
27
0
1
2
3
4
9
11
18
20
27
0
1
2
3
4
El arreglo ordenado es:
a
ORDENACIÓN POR EL MÉTODO DE SELECCION
void ord_seleccion( int a[N] )
{
int i, j, aux, posmen;
for(i=0;i
posmen = i;
for( j=i+1;j
posmen = j;
if ( posmen != i )
{
aux =...
ALGORITMOS Y PROGRAMACION
BÚSQUEDA SECUENCIAL
- Se utiliza en arreglos ordenados o desordenados.
- Consiste en recorrer el arreglo elemento por elemento, comparándolos con el dato
buscado. Este proceso finaliza cuando se encuentra el valor o cuando ya no existen más
elementos por recorrer.
int busqsecuencial( int a[N], int x )
{
int i;
i = 0;
while ( i
return i;
else
i++;
return -1;
}
BUSQUEDA BINARIA
- Se utiliza en arreglos ordenados.
- Consiste en reducir el espacio de búsqueda a la mitad cada vez que la comparación del
elemento 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<=u )
{
c = ( p + u ) / 2;
if ( a[c] == x)
return c;
else
if ( x < a[c] )
u =c -1 ;
else
p = c + 1;
}
return -1;
}
Mag. Hilmar Hinojosa Lazo
1
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
Ejemplo de Búsqueda Binaria
Buscar el valor 32 en el siguiente arreglo:
a
4
7
10
12
15
18
21
24
26
30
32
36
39
42
44
46
50
54
59
63
66
69
72
75
77
80
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2223
24
25
Inicialmente, el espacio de búsqueda es todo el arreglo, cuyo centro es el elemento 12:
a
4
7
10
12
15
18
21
24
26
30
32
36
39
42
44
46
50
54
59
63
66
69
72
75
77
80
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
p=0
c = 12
u = 25
Se compara 32 con a[12], como 32 es menor que 39, el nuevo espacio de búsquedava del elemento 0 al elemento 11, cuyo centro es el
elemento 5:
a
4
7
10
12
15
18
21
24
26
30
32
36
0
1
2
3
4
5
6
7
8
9
10
11
p=0
c= 5
u = 11
Mag. Hilmar Hinojosa Lazo
2
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
Se compara 32 con a[5], como 32 es mayor a 18, el nuevo espacio de búsqueda va del elemento 6 al elemento 11, cuyo centro esel
elemento 8:
a
21
24
26
30
32
36
6
7
8
9
10
11
p=6
c=8
u = 11
Se compara 32 con a[8], como 32 es mayor a 26, el nuevo espacio de búsqueda va del elemento 9 al elemento 11, cuyo centro es el
elemento 10:
a
30
32
36
9
10
11
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 posición 10.
Mag. Hilmar Hinojosa Lazo
3 UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
ORDENACIÓN POR EL MÉTODO DE LA BURBUJA
void ord_burbuja( int a[N] )
{
int i,j,aux;
for(i=0;i
{
aux = a[i];
a[i] = a[j];
a[j] = aux;
}
}
Ejemplo de Ordenación por el Método de la Burbuja
Ordenar el siguiente arreglo:
a
27
18
20
11
9
0
1
2
3
4
i=0
j=1
a[ 0 ] > a[ 1 ] ? Si Intercambiar
a
18
27
20
11
9
0
1
2
3
4
j=2
a[ 0 ] > a[ 2 ] ? No
j=3
a[ 0 ] > a[ 3 ] ? Si Intercambiar
a
j=3
11
27
20
18
9
0
1
2
3
4
a[ 0 ] > a[ 4 ] ? Si Intercambiar
Mag. Hilmar Hinojosa Lazo
4
UNMSM – Facultad de Ingeniería Industrial
ALGORITMOS Y PROGRAMACION
a
9
27
20
18
11
0
1
2
3
4
i=1
j=2
a[ 1 ] > a[ 2 ] ? Si Intercambiar
a
j=3
2027
18
11
0
1
2
3
4
a[ 1 ] > a[ 3 ] ? Si Intercambiar
a
j=4
9
9
18
27
20
11
0
1
2
3
4
a[ 1 ] > a[ 4 ] ? Si Intercambiar
a
9
11
27
20
18
0
1
2
3
4
i=2
j=3
a[ 2 ] > a[ 3 ] ? Si Intercambiar
a
j=3
9
11
20
27
18
0
1
2
3
4
a[ 2 ] > a[ 4 ] ? Si Intercambiar
a
Mag. Hilmar Hinojosa Lazo
9
11
18
27
20
0
1
2
3
4
5
UNMSM – Facultad deIngeniería Industrial
ALGORITMOS Y PROGRAMACION
i=3
j=4
a[ 3 ] > a[ 4 ] ? Si Intercambiar
a
9
11
18
20
27
0
1
2
3
4
9
11
18
20
27
0
1
2
3
4
El arreglo ordenado es:
a
ORDENACIÓN POR EL MÉTODO DE SELECCION
void ord_seleccion( int a[N] )
{
int i, j, aux, posmen;
for(i=0;i
posmen = i;
for( j=i+1;j
posmen = j;
if ( posmen != i )
{
aux =...
Leer documento completo
Regístrate para leer el documento completo.