2

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;
    }
}
1
  • 1
    ¿Aquí realmente cuál es el problema?
    – user166844
    Commented el 5 ago. 2020 a las 5:46

1 respuesta 1

3

Vamos por partes.

  1. 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 valores1, estás falseando la distribución al restablecer la semilla en cada llamada.
  2. 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.
  3. 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;
}

  • 1Depende de implementación.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.