When sorting an array removes data

Question

When sorting an array removes data

Navigation

#1 by (1 votes)

3

I am programming a genetic algortimo so that this solves problems of linear programming, I am using C language, when calculating the limit of the variables I keep the values in a float type array, I need to order that array but it erases a data What I need at the time of ordering: I have used a shell_sort pogramado by me and the qsort that is implemented in the standard librarian and with both gives me the same result, annex the code of the algortimo that I use to order and the comparator function that I use for the qsort ():

void shell_sort(float *A, int n){
    int gap = n/2;  //Se obtiene el gap dividiendo el tamaño de arreglo entre dos
    int inner, outer, swap; //Variables auxiliares

    while (gap > 0) { //Mientras gap sea mayor que zero entonces:
        for(outer = gap; outer < n; outer++){ // Para outer igual a gap, siempre que outer sea menor a n, outer aumentara su valor en uno
            inner = outer; // inner se iguala al valor de outer
            swap = A[inner]; // Swap se iguala a la posiscion inner de A
            while (inner > gap - 1 && A[inner - gap] > swap ) {  // Mientras inner sea mayor que gap menos 1 y que A en su posicion inner menos gap sea mayor a Swap
                A[inner] = A[inner - gap]; //La posicion inner de A tomara como nuevo valor la posicion inner menos  gap de A
                inner -= gap; //inner decrementa su valor en gap veces
            }
            A[inner] = swap; //La posicion inner de A tomo como nuevo valor swap
        }
        gap /=2; // se divide a gap entre dos
    }
}

Output:

int comp(const void * a, const void * b){
    if(*(float*)a < *(float*)b) return -1;
    if(*(float*)a == *(float*)b) return 0;
    if(*(float*)a > *(float*)b) return 1;
}

In the image you can see the data before ordering them and after ordering them, as you can see the 0.000 is missing Function where the sorting algorithms are used:

Limites obtenerValoresLimites(lista *l,char var){
    Limites lim;
    restriccion r;
    int i,j;
    float *aux = (float*)malloc(sizeof(float));
    for (i = 0; i < Size(l); i++)
    {
        r = Element(l,i+1);
        for (j = 0; j < strlen(r.variables); j++)
        {
            if(r.variables[j] == var){
                aux[i] = (r.limite/r.coeficientes[j]);
                }
        }
    }

    //for (i = 0; i < sizeof(aux)/sizeof(*aux) ;i++)
        //printf("%f\n",aux[i]);


    //qsort(aux,sizeof(aux)/sizeof(*aux)+1,sizeof(float),comp);
    shell_sort(aux,sizeof(aux)/sizeof(*aux));

    //printf("\n");

    //for (i = 0; i < sizeof(aux)/sizeof(*aux) ;i++)
    //{
    //  printf("%f\n",aux[i]);
    //}

    lim.inferior = 0;
    lim.superior = aux[(sizeof(aux)/sizeof(*aux))-1];
    lim.variable = var;

    return lim;
}

array c algoritmos quicksort

asked by Alan Garduño III 22.04.2018 в 20:42

source

1 answer

Invalid HTTP_HOST header using Nginx and Django Click on recyclerview does not work and does not give an error

score 1 · Answer 1

The first one on the forehead:

float *aux = (float*)malloc(sizeof(float));

You are reserving memory for a single element of type float , then this other instruction:

aux[i] = (r.limite/r.coeficientes[j]);

... will access memory that is not reserved for this variable and here two things can happen:

The memory belongs to other variables of your application and it becomes unstable (since you step on memory)
The memory belongs to another process and, depending on whether the Operating System is minimally modern or not, or you will leave the system made some foxes (old OS) or the OS kills your application to avoid it (new OS).

Since from the beginning you are already able to know how many elements you need, you have to make the correct reservation:

int numElementos = Size(l);
float *aux = (float*)malloc(sizeof(float)*numElementos);
for (i = 0; i < numElementos; i++)
// ...

free(aux); // No olvides liberar la memoria!!!

On the other hand, if this is the way you were using to print the array values:

for (i = 0; i < sizeof(aux)/sizeof(*aux) ;i++)
{
  printf("%f\n",aux[i]);
}

I have to tell you that you have a problem and that aux is not an array of fixed size but is a pointer that directs dynamic memory ... and sizeof is evaluated at compile time and, in this case , it will give you the size of a pointer (32 or b4 bits) regardless of the number of reserved items.

For iterations you have to use numElementos or, failing that, Size(l) :

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

// ...

shell_sort(aux,numElementos);

By the way, since C99 it is legal to declare variables within the loops, then I would recommend reducing the life of each variable to the minimum necessary:

for (int i = 0; i < numElementos ;i++)

And if we now take a look at the sort function we see this:

void shell_sort(float *A, int n){
  int swap;

  swap = A[inner];

  A[inner] = swap;
}

swap is type int while A[inner] is type float . By assigning a float to a int decimals are lost since int stores integers. If you do not want to lose those decimals, convert swap to type float :

float swap;

Since you have not set a minimum and complete example that reproduces the problem, I can not validate the solution, but as I told you via comments, the ordering function does not set values, so I understand that with this battery of changes the program should start working correctly.