Busqueda y Ordenacion

  • View
    217

  • Download
    0

Embed Size (px)

Text of 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