1

Estou tendo problemas na implementação do método de ordenação Bucket Sort, eu preciso testa-lo 30 vezes com diferentes quantidades de dados, mas quando eu tento com 100000 me apresenta esse erro: "Process returned -1073741819 (0xC0000005)"

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

#define TAM 100

struct balde
{
    int qtd;
    int vl[TAM];
};


double time1, timedif;

void bubble(int *v,int tam)
{
    int i,j,temp,flag;
    if(tam)
        for(j=0; j<tam-1; j++)
        {
            flag=0;
            for(i=0; i<tam-1; i++)
            {
                if(v[i+1]<v[i])
                {
                    temp=v[i];
                    v[i]=v[i+1];
                    v[i+1]=temp;
                    flag=1;
                }
            }
            if(!flag)
                break;
        }
}

void bucketSort(int *v,int n)
{
    int i,j,maior,menor,nbaldes,pos;
    struct balde *bd;
    maior=menor=v[0];

    for(i=1; i<n; i++)
    {
        if(v[i]>maior)
        {
            maior = v[i];
        }
        if(v[i]<menor)
        {
            menor = v[i];
        }
    }

    nbaldes = (maior-menor) / TAM + 1;

    bd = (struct balde *)malloc(nbaldes * sizeof(struct balde));

    for(i=0; i<nbaldes; i++)
    {
        bd[i].qtd=0;
    }

    for(i=0; i<n; i++)
    {
        pos=(v[i]-menor)/TAM;
        bd[pos].vl[bd[pos].qtd]=v[i];
        bd[pos].qtd++;
    }
    pos = 0;
    for(i=0; i<nbaldes; i++)
    {
        bubble(bd[i].vl,bd[i].qtd);
        for(j=0; j<bd[i].qtd; j++)
        {
            v[pos] = bd[i].vl[j];
            pos++;
        }
    }
    free(bd);
}


int main(void)
{
    int a, elementos = 1000; //Troque para quantidade de elementos que vai ser ordenada
    int *array=(int*)malloc(elementos*sizeof(int));
    srand(time(NULL));
    for(int i=0; i<30; i++)
    {
        for (a = 0; a < elementos; a++)
        {
            array[a]=rand()%100;
        }

        time1 = (double)clock();
        time1 = time1 / CLOCKS_PER_SEC;
        bucketSort(array, elementos); //Função
        timedif = (((double)clock()) / CLOCKS_PER_SEC) - time1;




        /* for (a = 0; a < 10; a++)
         {
             printf("\n%d\n", array[a]);
         }*/

        printf("\n--------------------------\nTeste:%d\n--------------------------\nTempo da Ordenação: %.3fs\n--------------------------\n",i+1, timedif);
    }
    return 0;
}
2

1 Resposta 1

2

Seu código está incorreto. Isto não lhe dá o número de baldes:

nbaldes = (maior - menor) / TAM + 1;

No caso seu vetor tem valores menores que 100 (que é o valor de TAM), então isso sempre vai lhe dar um balde só.

O número de baldes deveria ser um argumento da sua função.

Aproveitando, pra fazer malloc() o ideal é não aplicar cast no retorno da função e não usar explicitamente o tipo da variável:

void bucketSort(int *v, int n, int nbaldes)
{
    /* ... */
    bd = malloc(nbaldes * sizeof *bd);
}

O outro problema é que você está alocando baldes com tamanho 100 e nunca verifica se o balde consegue receber mais elementos. Você está tentando ordenar 1000 elementos em um pequeno número de baldes de tamanho 100; é plausível que um balde fique com mais que 100 elementos.

Idealmente você deveria utilizar alguma estratégia de realocação (realloc() para aumentar o vetor ou uma lista encadeada). Mas se você quiser dar uma "forçada", aumente o tamanho de TAM. Isso vai impactar um pouco o desempenho da sua função, mas deve funcionar.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .