Bucket Sort-C

Question

Bucket Sort-C

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

1

c ponteiro classificação

Author: Victor Stafusa, 2019-09-29

Source

1 answers

score 2 · Accepted Answer

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

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

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

The number of buckets should be an argument to your function.

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

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 checks if the bucket can receive more elements. You are trying to sort 1000 elements into a small number of buckets of size 100; it is plausible that one bucket will have more than 100 elements.

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