Algoritmos de búsqueda binario, secuencial y secuencial indexado

Este es un programa escrito en ANSI C que demuestra los algoritmos de ordenamiento binario, secuencial y secuencial indexado. Primero crea una vector aleatorio, busca el numero pedido por medio de búsqueda secuenical. Posteriormente odena el vector mediante Quiksort, para después proceder sobre el vector mediante búsqueda binaria y finalmente crea un índice para la búsqueda seciencial indexada.

/*
 * Programa: busca.c
 *
 * Programa muestra de una busqueda secuencial, binaria y sequencial indexada
 *
 * Autor: Jesús Manuel Mager Hois
 * Materia: Informática III
 * Facultad de Contaduría y Administración
 * UNAM
 * 
 * Licencia GPL 3 o superior
 * 2009
 *
 */

#include<stdio.h>
#include<stdlib.h>

#define TAM 45 
#define MAX_IND 100

typedef struct index{
 int valor;
 int pos;
}index;

// Funciones de utilidad

void quick_sort(int v[], int size);
void q_sort(int v[], int left, int right);


// Devuelve la posición int del arreglo de enteros v de tamaño tam entero
int b_secuencial(int v[], int tam, int buscar);
int b_binaria(int v[], int tam, int buscar);
int index_creator(int tam);
int b_secindexada(int v[], int tam, int buscar);

int main (int argc, char * argv[]){

 int v[TAM];
 int i;
 int pos;
 int temp;


 printf("********* Programa demostrar algoritmos de ordenamiento *********\n");

 printf("Números generados en el vector: ");
 for(i=0; i<TAM; i++){
  v[i]=random()%150;
  printf("%d ",v[i]);
 }
  

 printf("\nNúmero a buscar?");
 scanf("%d", &temp);

 printf("\n# Por búsqueda secuencial ");

 if((pos=b_secuencial(v, TAM, temp))!=-1)
  printf("%d se encuenra en la posición: %d\n", temp, pos);
 else
  printf("%d no se encuentra en la lista", temp);

 printf("\nOrdenando la lista.... (Quicksort)");
 printf("\nEl vector ordenado es: ");

 quick_sort(v, TAM);

 for(i=0; i<TAM; i++)
  printf("%d ", v[i]);
 printf("\n");

 printf("\n# Por búsqueda binaria  ");

 if((pos=b_binaria(v, TAM, temp))!=-1)
  printf("%d se encuenra en la posición: %d\n", temp, pos);
 else
  printf("%d no se encuentra en la lista", temp);

 if((pos=b_secindexada(v, TAM, temp))!=-1)
  printf("%d se encuenra en la posición: %d\n", temp, pos);
 else
  printf("%d no se encuentra en la lista", temp);


 printf("\n ****************** Fin del Programa *******************\n");


 return 0;
}

/*
 * Funciones de utilidad para ordenar mediante
 * Quicksort
 */

void quick_sort(int v[], int size)
{
 q_sort(v, 0, size-1);
}

void q_sort(int v[], int left, int right)
{

 int pivot, lTmp, rTmp;
 lTmp=left;
 rTmp=right;
 pivot=v[left];

 while ( left < right )
 {
  while((v[right] >= pivot) && (left < right))
   right--;
  if(left != right)
  {
   v[left]=v[right];
   left++;
  }
  while ((v[left] <= pivot) && (left<right))
   left++;
  if(left!=right)
  {
   v[right]=v[left];
   right--;
  }
 }
 v[left]=pivot;
 pivot=left;
 left=lTmp;
 right=rTmp;

 if(left<pivot)
  q_sort(v, left, pivot-1);
 if(right>pivot)
  q_sort(v, pivot+1, right);
}

/*
 * Función que recorre el vector sin ordenar en busca
 * del valor deseado. 
 * Devuelve la posición o -1 si no existe el valor
 * en el vector.
 */

int b_secuencial(int v[], int tam, int buscar){
 int i;

 for(i=0; i<tam; i++)
  if(v[i]==buscar)
   return i;
 return -1;
}

/*
 * Función que busca un elemento en una lista ordenada
 * partiendo la lista en dos, descartando la mitad de la lista 
 * donde no se puede encontrar el valor buscado, y así 
 * sucesivamente.
 * Devuelve la posición del valor en el vector o -1 si 
 * no se encontró el valor.
 */

int b_binaria(int v[], int tam, int buscar){

 int ini=0;
 int fin=tam;
 int centro;

 while (ini<=fin){
  centro=((ini+fin)/2);

  if (v[centro] == buscar)
   return centro;

  if (buscar<v[centro])
   fin=centro-1;
  else
   ini=centro+1;
 }
 return -1;
}

/*
 * Función que busca un intervalo adecuado para el índice
 */

int index_creator(int tam){
 
 int i;

 printf("El tamaño del arreglo es %i", tam);

 if (tam<=1000){
  for(i=5; i<=30; i++)
   if(tam%i==0 && tam!=i)
    return i;
  for (i=5; i>=3; i--)
   if(tam%i==0 && tam!=i)
    return i;
  return -1;
 }
 else if(tam>1000 && tam < 99999){
  for(i=20; i<99; i++)
   if(tam%i==0 && tam!=i)
    return i;
  return -1;
 }
}

/* Función que realiza una búsqueda secuencial indexada
 * Primero busca un intervalo para el indice, luego
 * general el ínidce.
 * Una vez teniendo el ínidice realiza una búsqueda 
 * en secuencial en el ínidce, para posteriormente encontrar
 * las claves entre las cuales realizar otra búsqueda
 * secuencial y asi encontrar la posición que se devuele.
 * Si no existe el valor en el vector se devuelve -1.
 * El vector tiene que estar ordenado.
 */

int b_secindexada(int v[], int tam, int buscar){

 int intervalo;
 int i;
 int j=0;
 int tam_ind=0;
 index indice[MAX_IND];

 printf("\nGenerando el indice:\n");

 intervalo=index_creator(tam);
 if(intervalo==-1){
  printf("\nNo se encontró un intervalo adecuado... abortando...\n");
  return -1;
 }

 printf("\nEl intervalo es: %d\n", intervalo);

 for(i=0; i<=tam; i=i+intervalo){
  indice[tam_ind].pos=i;
  indice[tam_ind].valor=v[i];
  tam_ind++;
 }

 for(i=0; i<tam_ind; i++)
  printf("\n %d, %d", indice[i].pos,indice[i].valor);

 printf("\n");
 
 for(i=0; i<tam_ind; i++)
 {
  printf("La posición es: %d\n",indice[i].pos);
  if(indice[i].valor>=buscar)
  {
   printf("Estamos buscando %d entre %d a %d \n", buscar, indice[i].pos-intervalo, indice[i].pos);
   for(j=(indice[i].pos-intervalo); j<=indice[i].pos; j++)
   {
    printf("Estamos buscando %d en %d:%d \n", buscar, j, v[j]);
    if(v[j]==buscar)
    {
     return j;
    }
   }
  }
 }
 return -1;
}

Algoritmos de Ordenamiento

Comparto con ustedes un programa en C ANSI 89 que muestra la implementación de cuatro algoritmos de ordenamient: Burbuja, Selección, Inerción y una implementación básica de Quicksort son optimizaciones. Espero este ejemplo siva a todos los estudiantes para ver la aplicación de estos algoritmos.
La licencia es GPL 3 así que ya saben, pueden copiar y pegar sin problema siempre y cuando el nuevo código esté disponible bajo GPL 3 o superior.

/*
 * Escrito por Jesús Manuel Mager Hois 
 * el 27 de abril de 2009, tomando referencias
 * de Wikipedia.
 * 
 * Descripción: Programa que genera listas
 *     aleatorias para después 
 *     ordenarlas con los algoritmos
 *     de burbuja, selección,
 *     inserción y quicksort.
 *
 *     Todos los algoritmos son simples,
 *     y representan únicamente
 *     las ideas básicas detrás de
 *     cada algoritmo.
 *
 * Lenguaje: ANSI C
 *
 * Bajo licencia GPL 3
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define V_SIZE 10

int cont;

// Herramientas
void gen_rand(int v[], int size);
void print_vect(int v[], int size);
void swap(int v[], int o, int d);

//Algoritmos
void bubble_sort(int v[], int size);
void insert_sort(int v[], int size);
void select_sort(int v[], int size);
void quick_sort(int v[], int size);
void q_sort(int v[], int left, int right);
//void quick_sort(int v[], int size);

int main(int argc, char *argv[])
{
 int v[V_SIZE];

 printf("---------------------------------------------------\n");
 printf("UNAM FCA SUA\n");
 printf("Materia: Informática III\n");
 printf("Alumno: Jesús Manuel Mager Hois\n");
 printf("---------------------------------------------------\n");
 printf("Este programa genera listas aleatorias que son\n");
 printf("ordenadas por los siguientes algoritmos: bubblesort\n");
 printf("insert sort, selecction sort y quicksort. Todos\n");
 printf("son ejemplos sencillos que solo pretenden mostrar\n");
 printf("los conecpts básicos de cada uno.\n");
 printf("Por J. M. 2009 Bajo GPL 3. (ver código fuente)\n");
 printf("############ Ordenando con Burbuja ############\n");
 gen_rand(v, V_SIZE);
 printf("No. Aleatorios: ");
 print_vect(v, V_SIZE);

 bubble_sort(v, V_SIZE);
 printf("No. Ordenados : ");
 print_vect(v, V_SIZE);

 printf("############ Ordenando por Inserción ##########\n");
 gen_rand(v, V_SIZE);
 printf("No. Aleatorios: ");
 print_vect(v, V_SIZE);
 
 insert_sort(v, V_SIZE);
 printf("No. Ordenados : ");
 print_vect(v, V_SIZE);

 printf("############ Ordenando por Selección ##########\n");
 gen_rand(v, V_SIZE);
 printf("No. Aleatorios: ");
 print_vect(v, V_SIZE);
 
 select_sort(v, V_SIZE);
 printf("No. Ordenados : ");
 print_vect(v, V_SIZE);

 printf("############ Ordenando por Quicksort ##########\n");
 gen_rand(v, V_SIZE);
 printf("No. Aleatorios: ");
 print_vect(v, V_SIZE);
 
 quick_sort(v, V_SIZE);
 printf("No. Ordenados : ");
 print_vect(v, V_SIZE);



 return 0;
}


void gen_rand(int v[], int size)
{
 int i;

 cont = cont + 1;
 srand(time(NULL)*cont);
 for(i=0; i<size; i++)
  v[i]=rand()%100;
}


void print_vect(int v[], int size)
{
 int i;
 printf("[ ");
 for(i=0; i<size; i++)
  printf("%d ", v[i]);
 printf("]\n");
}

void swap(int v[], int o, int d)
{
 int temp;
 temp=v[d];
 v[d]=v[o];
 v[o]=temp;
}

void bubble_sort(int v[], int size)
{
 int i, j;
 for (j=0; j<size; j++)
  for (i=0; i<size-1; i++)
   if(v[i]>v[i+1])
    swap(v, i, i+1);
}

void insert_sort(int v[], int size)
{
 int i, j, temp;
 for(i=0; i<size; i++)
 {
  temp=v[i];
  j=i-1;
  while(j>=0 && v[j] >temp)
  {
   v[j+1] = v[j];
   j--;
  }

  v[j+1] = temp;
 }
}

void select_sort(int v[], int size)
{
 int i, j, min;
 for (i=0; i<size; i++)
 {
  min=i;

  for(j=i+1; j< size; j++)
   if(v[min]>v[j])
    min=j;

  swap(v, min, i);
 }
}

void quick_sort(int v[], int size)
{
 q_sort(v, 0, size-1);
}

void q_sort(int v[], int left, int right)
{

 int pivot, lTmp, rTmp;
 lTmp=left;
 rTmp=right;
 pivot=v[left];

 while ( left < right )
 {
  while((v[right] >= pivot) && (left < right))
   right--;
  if(left != right)
  {
   v[left]=v[right];
   left++;
  }
  while ((v[left] <= pivot) && (left<right))
   left++;
  if(left!=right)
  {
   v[right]=v[left];
   right--;
  }
 }
 v[left]=pivot;
 pivot=left;
 left=lTmp;
 right=rTmp;

 if(left<pivot)
  q_sort(v, left, pivot-1);
 if(right>pivot)
  q_sort(v, pivot+1, right);
}