Método de Búsqueda

Método de Búsqueda Binaria

la búsqueda binaria proporciona una técnica de búsqueda mejorada. Una búsqueda binaria típica es la búsqueda de una palabra en un diccionario. Dada la palabra, se abre el libro cerca del principio, del centro o del final dependiendo de la primera letra del primer apellido o de la palabra que busca. Se puede tener suerte

y acertar con la página correcta; pero, normalmente, no será así y se mueve el lector a la página anterior o posterior del libro. Por ejemplo, si la palabra comienza con «J» y se está en la «L» se mueve uno hacia atrás. El proceso continúa hasta que se encuentra la página buscada o hasta que se descubre que la palabra no está en la lista.

Técnica del Método de Búsqueda:

Se aplica en la búsqueda en una lista ordenada. Se sitúa la lectura en el centro de la lista y se comprueba si la clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sigue la búsqueda uno en la mitad inferior o superior del elemento central de la lista. En general, si los datos de la lista están ordenados se puede utilizar esa información para acortar el tiempo de búsqueda.

Ejemplo


Se desea buscar el elemento 225 y ver si se encuentra en el conjunto de datos siguiente:

a[0]      a[1]      a[2]     a[3]      a[4]      a[5]       a[6]      a[7]
13         44         75      100      120       275       325       510


El punto central de la lista es el elemento a[3] (100). El valor que se busca es 225, mayor que 100; por consiguiente, la búsqueda continúa en la mitad superior del conjunto de datos de la lista, es decir, en la sublista,

a[4] a[5] a[6] a[7]
120 275 325 510

Ahora el elemento mitad de esta sublista a[5] (275). El valor buscado, 225, es menor que 275 y, por consiguiente, la búsqueda continúa en la mitad inferior del conjunto de datos de la lista actual; es decir, en la sublista de un único elemento:

a[4]
120

El elemento mitad de esta sublista es el propio elemento a[4] (120). Al ser 225 mayor que 120, la búsqueda debe continuar en una sublista vacía. Se concluye indicando que no se ha encontrado la clave en la lista.

Codificación de Método de Búsqueda Binaria 

int busq_bin(int a[], int n, int nx)

{

int central,bajo,alto,valorCentral;

bajo=1;

alto=n-1;

while(bajo<=alto)

     {

     central=(bajo+alto)/2;

     valorCentral=a[central];

     if(nx==valorCentral)

       return(central);

     else if(nx<valorCentral)

       alto=central-1;

     else

       bajo=central+1;

     }

     return-1;

}

Prueba de Escritorio:

Método de Búsqueda

Búsqueda Secuencial 

La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave. En una búsqueda secuencial (a veces llamada búsqueda lineal), los elementos de una lista o vector se exploran (se examinan) en secuencia, uno después de otro.

Técnica del Método de Búsqueda:El algoritmo de búsqueda secuencial compara cada elemento del array con la clave de búsqueda. Dado que el array no está en un orden prefijado, es probable que el elemento a buscar pueda ser el primer elemento, el último elemento o cualquier otro. De promedio, al menos el programa tendrá que comparar la clave de búsqueda con la mitad de los elementos del array. El método de búsqueda lineal funcionará bien con arrays pequeños o no ordenados. La eficiencia de la búsqueda secuencial es pobre, tiene complejidad lineal, O(n).

Codificación del Método de Búsqueda Secuencial

void busq_sec(int a[], int n, int nx)

{

int i,x1,ubicado=0;

for(i=0;i<n;i++)

   {

   if(a[i]==nx)

     {

     ubicado=1;

     printf("\nEl numero %d se encuentra en la posicion a[%d] de lista",nx,i);

     }

   }

if(ubicado==0)

   printf("\nEl numero ingresado no se encuentra en la lista %d");

}

Prueba de Escritorio:

Método de Búsqueda

• Clases de Método de Búsqueda 

1. Búsqueda Secuencial
2. búsqueda Binaria

Otros Métodos de Ordenamiento Indirectos

•Ordenamiento por mezcla: Es un algoritmo de ordenamiento externo estable basado en la técnica divide y vencerás. Es de complejidad O(n log n), es similar al método Quicksort .

• Ordenamiento Radix: es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort  no está limitado sólo a los enteros.

• Ordenación por fusión(v: vector): Sea N := tamaño(v), podemos separar el vector en dos mitades. Estas dos mitades tienen tamaño N/2 por lo que por inducción podemos aplicar la ordenación en estos dos sub-problemas. Una vez tenemos ambas mitades ordenadas simplemente debemos fusionarlas. El caso base es ordenar un vector de 0 elementos, que está trivialmente ordenado y no hay que hacer nada.

Método de Binsort: Este método, también llamado clasificación por urnas, persigue conseguir funciones de tiempo de ejecución menores de O(n log n), para ordenar una secuencia de n elementos siempre que se

conozca algo acerca del tipo de las claves por las que se están ordenando.

* Dentro de los métodos Indirectos

Método de Quicksort

2. Método de ordenamiento Quicksort : (ordenación rápida) recibe el nombre de su autor, Tony Hoare. La idea del algoritmo es simple, se basa en la división en particiones de la lista a ordenar, por lo que se puede considerar que aplica la técnica divide y vencerás. El método es, posiblemente, el más pequeño de código, más rápido, más elegante, más interesante y eficiente de los algoritmos de ordenación conocidos.

Técnica del Método: El método se basa en dividir los n elementos de la lista a ordenar en dos partes o particiones separadas por un elemento: una partición izquierda, un elemento central denominado pivote o
elemento de partición, y una partición derecha. La partición o división se hace de tal forma que todos los elementos de la primera sublista (partición izquierda) son menores que todos los elementos de la segunda sublista (partición derecha). Las dos sublistas se ordenan entonces independientemente.
Para dividir la lista en particiones (sublistas) se elige uno de los elementos de la lista y se utiliza como pivote o elemento de partición. Si se elige una lista cualquiera con los elementos en orden aleatorio, se puede seleccionar cualquier elemento de la lista como pivote, por ejemplo, el primer elemento de la lista. Si la lista tiene algún orden parcial conocido, se puede tomar otra decisión para el pivote. Idealmente, el pivote se debe elegir de modo que se divida la lista exactamente por la mitad, de acuerdo al tamaño relativo de las claves.

Ejemplo:

1. Lista original           5 2 1 7 9 3 8 7
pivote elegido 5
sublista izquierda1 (elementos menores que 5)   2 1 3
sublista derecha1 (elementos mayores o iguales a 5)   9 8 7

2. El algoritmo se aplica a la sublista izquierda
Sublista Izda  2 1 3
sublista Izda 1
pivote  2                                  
sublista Dcha 3

Sublista Izda
 Izda  pivote  Dcha
    1      2        3
3. El algoritmo se aplica a la sublista derecha
Sublista Dcha   9 8 7
sublista Izda 7
pivote 8
sublista Dcha 9

Sublista Dcha
Izda        pivote       Dcha
   7            8              9

4. Lista ordenada final
Sublista izquierda        pivote             Sublista derecha
       1 2 3                      5                         7 8 9


Codificación del Método Quicksort

void quicksort(double a[], int primero, int ultimo)

{

int i, j, central;

double pivote;

central = (primero + ultimo)/2;

pivote = a[central];

i = primero;

j = ultimo;

do {

while (a[i] < pivote) i++;

while (a[j] > pivote) j--;

if (i<=j)

{

double tmp;

tmp = a[i];

a[i] = a[j];

a[j] = tmp;

i++;

j--;

}

}while (i <= j);

if (primero < j)

quicksort(a, primero, j);

if (i < ultimo)

quicksort(a, i, ultimo);

}

Prueba de Escritorio:

* Dentro de los métodos Indirectos

1. Método de Ordenamiento Shell

Técnica del Método: La ordenación Shell debe el nombre a su inventor, D. L. Shell. Se suele denominar también ordenación por inserción con incrementos decrecientes. Se considera que el método Shell es una mejora de los métodos de inserción directa. 

En el álgoritmo de inserción, cada elemento se compara con los elementos contiguos de su izquierda, uno tras otro. Si el elemento a insertar es el más pequeño hay que realizar muchas comparaciones antes de colocarlo en su lugar definitivo.

El algoritmo de Shell modifica los saltos contiguos resultantes de las comparaciones por saltos de mayor tamaño y con ello se consigue que la ordenación sea más rápida. Generalmente se toma como salto inicial n/2 (siendo n el número de elementos), luego se reduce el salto a la mitad en cada repetición hasta que el salto es de tamaño 1.

Los pasos a seguir por el algoritmo para una lista de n elementos son:

1. Dividir la lista original en n/2 grupos de dos, considerando un incremento o salto entre los elementos de n/2.

2. Clarificar cada grupo por separado, comparando las parejas de elementos, y si no están ordenados, se intercambian.

3. Se divide ahora la lista en la mitad de grupos (n/4), con un incremento o salto entre los elementos también mitad (n/4), y nuevamente se clasifica cada grupo por separado.

4. Así sucesivamente, se sigue dividiendo la lista en la mitad de grupos que en el recorrido anterior con un incremento o salto decreciente en la mitad que el salto anterior, y luego clasificando cada grupo por separado.

5. El algoritmo termina cuando se consigue que el tamaño del salto es 1.

Ejemplo:

Obtener las secuencias parciales del vector al aplicar el método Shell para ordenar en orden creciente la lista:

                                                             6 1 5 2 3 4 0

El número de elementos que tiene la lista es 6, por lo que el salto inicial es 6/2 = 3. La siguiente tabla muestra el número de recorridos realizados en la lista con los saltos correspondiente.

Recorrido                    Salto                         Intercambios                             Lista

     1                               3                        (6,2),(5,4),(6,0)                       2 1 4 0 3 5 6

     2                               3                        (2, 0)                                       0 1 4 2 3 5 6

     3                               3                            ninguno                                0 1 4 2 3 5 6

salto 3/2 = 1

   4                                  1                         (4,2),(4,3)                              0 1 2 3 4 5 6

   5                                  1                         ninguno                                  0 1 2 3 4 5 6

Codificación de la Función de Método de Shell

void Shell(int a[], int n)

{

int intervalo,i,j,k;

intervalo=n/2;

while(intervalo>0)

     {

     for(i=intervalo;i<n;i++)

  {

  j=i-intervalo;

  while(j>=0)

       {

       k=j+intervalo;

       if(a[j]<=a[k])

         j=-1;

       else

  {

  int temp;

  temp=a[j];

  a[j]=a[k];

                   a[k]=temp;

  j-=intervalo;

  }

        }

   }

              intervalo=intervalo/2;

     }

}

Prueba de Escritorio:

Método por Inserción 

3. Método de  Inserción 

• Técnica del método: El método de ordenación por inserción es similar al proceso típico de ordenar tarjetas de nombres (cartas de una baraja) por orden alfabético, que consiste en insertar un nombre en su posición correcta dentro de una lista o archivo que ya está ordenado.

La ordenación por inserción contempla los siguientes pasos:
1. El primer elemento A[0] se considera ordenado; es decir, la lista inicial consta de un
elemento.
2. Se inserta A[1] en la posición correcta, delante o detrás de A[0], dependiendo de que sea
menor o mayor.
3. Por cada bucle o iteración i (desde i=1 hasta n-1) se explora la sublista A[i-1] . .
A[0] buscando la posición correcta de inserción; a la vez se mueve hacia abajo (a la derecha
en la sublista) una posición todos los elementos mayores que el elemento a insertar
A[i], para dejar vacía esa posición.
4. Insertar el elemento a la posición correcta.

Ejemplo:

La función Inserción() tiene dos argumentos, el array a[] que se va a ordenar crecientemente,
y el número de elementos n. En la codificación se supone que los elementos son de tipo
entero.

void  Insercion (int [] a, int n)

{

int i, j;

int aux;

for (i = 1; i < n; i++)

       {

        j = i;

aux = a[i];

while (j > 0 && aux < a[j-1])

          {

           a[j] = a[j-1];

          j--;

           }

          a[j] = aux;

       }

}

Definición de Funciones:

void  Insercion (int [] a, int n)

{

int i, j;

int aux;

for (i = 1; i < n; i++)

       {

        j = i;

aux = a[i];

while (j > 0 && aux < a[j-1])

          {

           a[j] = a[j-1];

          j--;

           }

          a[j] = aux;

       }

}

void imprimirLista (int a[], int n)

{

int i;

for (i = 0 ; i < n ; i++)

{

printf("%d", a[i]);

}

}

void entradaLista (int a[], int n)

{

int i;

printf("\n Entrada de los elementos\n");

for (i = 0 ; i < n ; i++)

{

printf("a[%d] = ",i);

scanf("%d", a+i);

}

}

Prueba de Escritorio: