Download pdf - Busqueda y Ordenacion

Transcript
  • 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