Bucket Sort - C

Question

I’m having problems implementing the Bucket Sort sorting method, I need to test it 30 times with different amounts of data, but when I try with 100000 it presents me this error: "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;
}

Answer 1

Your code is incorrect. This does not give you the number of buckets:

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

In the case your vector has values less than 100 (which is the value of TAM), then it will always give you a bucket only.

The number of buckets should be an argument of their function.

Taking advantage to do malloc() the ideal is not to apply cast return function and do not explicitly use variable type:

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

The other problem is that you are allocating buckets with size 100 and never check if the bucket can receive more elements. You are trying to sort 1000 elements in a small number of buckets of size 100; it is plausible that a bucket will have more than 100 elements.

Ideally you should use some relocation strategy (realloc() to increase the array or a chained list). But if you want to give a "forced", increase the size of TAM. This will impact a little the performance of your function, but it should work.