Contar y mostrar las comparaciones de un método de búsqueda en C

Question

Estoy realizando un programa en Dev C++ que genera números aleatorios y después se ordenan en un vector por el método de inserción... Hasta aquí todo marcha bien, el problema a solucionar es que ahora debe encontrar el numero 50 y si no esta en la lista que me muestre el inmediato superior y especifique cuantas comparaciones hizo en la búsqueda.

tengo lo siguiente:

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

#define V_SIZE 10

int cont;

// Declaracion de metodos
void gen_rand(int v[], int size);
void print_vect(int v[], int size);
void swap(int v[], int o, int d);
void insert_sort(int v[], int size);
    
//menu principal
int main(int argc, char *argv[])
{
    int v[V_SIZE];

    printf("\t Ordenando por Insercion \n");
    gen_rand(v, V_SIZE);
    printf("\nNumeros Aleatorios generados: ");
    print_vect(v, V_SIZE);
    printf("\nNumeros ordenados: ");
    insert_sort(v, V_SIZE);
    print_vect(v, V_SIZE);

    //Suponiendo que la lista generada ya ordenada fue [1  2  3  5  63 70]
    //Que aqui mostrara tal vez..."El numero 50 no esta en la lista, su inmediato superior es 63"
    //"Y se realizaron N comparaciones"
    return 0;
}

//Metodo para generar la lista aleatoria
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;
}
    
//Impresion de la lista
void print_vect(int v[], int size) {
    int i;
    printf("[ ");
    for(i = 0; i < size; i++)
    printf("%d ", v[i]);
    printf("]\n");
}

//Metodo de ordenamiento por insercion
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;
    }
}

¿Aquí realmente cuál es el problema? – Aug 05 '20 at 05:46 — , Aug 05 '20 at 05:46

score 3 · Answer 1 · answered Aug 05 '20 at 07:51

Vamos por partes.

Evita las variables globales (lee este hilo para saber por qué).

Tu variable global cont es completamente innecesaria, su uso está mal a varios niveles:
- Se usa en gen_rand sin inicializar (supongo que para aprovechar la incertidumbre del valor contenido), las variables sin inicializar no deberían formar parte de ningún algoritmo pues pueden causar comportamiento indefinido.
- Usas cont para multiplicar el retorno de time(NULL), lo cuál muy posiblemente provoque un error de desbordamiento aritmético.
- Lo usas para restablecer la raíz de números pseudo-aleatorios, dado que rand proporciona una distribución uniforme de valores¹, estás falseando la distribución al restablecer la semilla en cada llamada.
El ámbito de las variables deben ser lo más pequeño posible: No declares las variables de control de los bucles for fuera del bucle.
- Cuando las variables están cerca de su punto de uso, es más fácil comprender su objetivo y rastrearlas.
Usa nombres auto-explicativos: Tu yo del futuro lo agradecerá.
- Nombres como o, d, i, j pueden parecer obvios hoy y ser un enigma mañana, escoge nombres que expliquen su cometido.

Dicho esto, localizamos la función que hace las comparaciones:

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){
//                ^^^^^^^^^^ <---- Aquí está la comparación.
    v[j+1] = v[j];
         j--;
         }

        v[j+1] = temp;
    }
}

Cambiemos la función para que devuelva las comparaciones realizadas:

int insert_sort(int v[], int size) {

    int comparaciones = 0;

    for(int i = 0; i != size; ++i) {
        int temp = v[i];
        int j = i - 1;

        while(j >= 0 && v[j] > temp) {
            ++comparaciones;
            v[j + 1] = v[j];
            --j;
        }

        v[j + 1] = temp;
    }

    return comparaciones;
}

¹Depende de implementación.

Contar y mostrar las comparaciones de un método de búsqueda en C

1 Answers1