Algoritmos de búsqueda

Un algoritmo de búsqueda es aquel que nos permite encontrar un elemento dentro de una estructura de datos como podría ser un vector o una base de datos.

Para explicar los dos algoritmos básicos de búsqueda, que son: la búsqueda secuencial y la búsqueda dicotómica o binaria; tomaremos como elemento un número entero y como estructura de datos un vector.

Algoritmo de ordenación por selección directa

Es un algoritmo sencillo y uno de los más sencillos de recordar e implementar. No es el mejor algoritmo de ordenación ya que realiza una gran cantidad de comparaciones, pero, por el contrario, realiza muy pocos intercambios.

El algoritmo consiste en realizar varias pasadas sobre el vector, de tal manera que el elemento de menor peso se coloque al principio del vector en un solo intercambio. En cada pasada se recorre la parte no ordenada del vector buscando el elemento de menor peso y cuando se localiza se intercambia con el primer elemento de la parte no ordenada del vector.

Veamos la implementación del algoritmo en C:

/* funcion de ordenacion por seleccion directa */
void seleccion_directa(int v[], int N) {
   int min, tmp; // elemento de menor peso y elemento temporal
 
   /* recorremos todo el vector */
   for(int i = 0; i < N - 1; i++) {
      /* suponemos que es el primero */
      min = i;
      /* recorremos la parte no ordenada */
      for(int j = i+1; j < N; j++) {
         /* buscamos el de menor peso */
         if(v[j] < v[min]) min = j;
      }
      /* intercambio posicion i por el de menor peso */
      tmp = v[i];
      v[i] = v[min];
      v[min] = tmp;  
   }

}

Enlaces externos:

• la tecla de escape
• wikipedia

Algorito de ordenación por inserción directa

Éste es el algoritmo de ordenación más intuitivo para el ser humano, ya que el método de ordenación es el natural para nosotros. Es el que utilizaríamos, por ejemplo, para ordenar una baraja de cartas. A este algoritmo también se le conoce como "insertion short".

Su funcionamiento es el siguiente. Tomamos el vector (nuestra baraja de cartas), que está desordenado. Cogemos la carta de arriba y la insertamos en su lugar correspondiente en un montón separado. Una vez recorridas todas las cartas, el montón separado ya está ordenado.

Veamos como se implementa este algoritmo en C.

void insercion_directa(int v[], int N) {
   int tmp;
 
   for (int i=1; i < N; i++) {
      tmp = v[i];
      j = i - 1;
      while(int j >= 0 && v[j] > tmp) {
         v[j+1] = v[j];
         j--;
      }
      v[j+1] = tmp;
   }
}

Enlaces externos:

• La tecla de escape
• Snippets tricks
• Wikipedia

Algoritmo de ordenación de la burbuja

Es el algoritmo de ordenación más sencillo de implementar y a la vez el más ineficiente. Recibe otros nombres como: bubble short o método de intercambio directo.

Funciona de la siguiente manera: dado un vector de números desordenados, se va recorriendo dicho vector en sucesivas iteraciones de tal manera que los elementos de menor peso se intercambian para que ocupen posiciones superiores (como si fueran burbujas, de ahí el nombre del algoritmo) hasta que ya no hay elementos que intercambiar, momento en el que el vector ya está ordenado.

Veamos a continuación la implementación de este algoritmo en C.

// funcion de ordenacion
void intercambio_directo(int v[], int N) {
   int aux;

   for(int i = 1; i < N; i++)
      for(int j = N - 1; j >= i; j--)
         if(v[j-1] > v[j]) { // intercambiamos los valores
            aux = v[j-1];
            v[j-1] = v[j];
            v[j] = aux;
         }
}