array bucket sort in C

Question

I am trying to read list of numbers from txt file and then sort them with Bucket sort. so here is my code:

void bucketSort(int array[],int *n)
{
    int i, j;  
    int count[*n]; 
    for (i = 0; i < *n; i++)
        count[i] = 0;

    for (i = 0; i < *n; i++)
        (count[array[i]])++;

    for (i = 0, j = 0; i < *n; i++)  
        for(; count[i] > 0; (count[i])--)
            array[j++] = i; 
}   

int main(int brArg,char *arg[])
{

    FILE *ulaz;
    ulaz = fopen(arg[1], "r");

    int array[100];
    int i=0,j,k,n;


      while(fscanf(ulaz, "%d", &array[i])!=EOF)i++;

    fclose(ulaz);    
    n=i;
    for (j = 0; j<i; j++)
    {
        printf("Broj: %d\n", array[j]);
    }

    BucketSort(array,&n); 
    for (k = 0; k<i; k++)
        printf("%d \n", array[i]);   


    return 0;
}

There are no errors in code,but when i call my function instead of sorted array i get array length random numbers(example: 2 3 5 4,after sorting i get 124520 124520 124520 124520 or some other random number) since i am a beginner,could someone help me with my code and what i did wrong? (sorry for bad english)

Answer 1

As Cool Guy correctly pointed out you have issues with memory access but on top of it the code does not sort anything. First you should read how Bucket Sort actually works.

In general:

• You divide the input data among buckets by some criteria that guarantees that the buckets will not mess up the input order
• Sort each bucket either using some other sorting method or recursively with bucket sort
• Concatenate the sorted data (this is why the first point has the restriction of not messing up the input order)

Here is an example of your original code, I tried to adjust it as little as possible you it is easier for you to understand. This code divides a predefined input array among 3 buckets by range:

• [-infinity][-1] -> first bucket
• [0;10] -> second bucket
• [11;infinity] -> third bucket

then performs Quicksort on each bucket and concatenates the result. I hope this helps to understand how this algorithm works.

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

struct bucket 
{
    int count;
    int* values;
};

int compareIntegers(const void* first, const void* second)
{
    int a = *((int*)first), b =  *((int*)second);
    if (a == b)
    {
        return 0;
    }
    else if (a < b)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

void bucketSort(int array[],int n)
{
    struct bucket buckets[3];
    int i, j, k;
    for (i = 0; i < 3; i++)
    {
        buckets[i].count = 0;
        buckets[i].values = (int*)malloc(sizeof(int) * n);
    }
    // Divide the unsorted elements among 3 buckets
    // < 0    : first
    // 0 - 10 : second
    // > 10   : third
    for (i = 0; i < n; i++)
    {
        if (array[i] < 0)
        {
            buckets[0].values[buckets[0].count++] = array[i];
        }
        else if (array[i] > 10)
        {
            buckets[2].values[buckets[2].count++] = array[i];
        }
        else
        {
            buckets[1].values[buckets[1].count++] = array[i];
        }
    }
    for (k = 0, i = 0; i < 3; i++)
    {
        // Use Quicksort to sort each bucket individually
        qsort(buckets[i].values, buckets[i].count, sizeof(int), &compareIntegers);
        for (j = 0; j < buckets[i].count; j++)
        {
            array[k + j] = buckets[i].values[j];
        }
        k += buckets[i].count;
        free(buckets[i].values);
    }
}

int main(int brArg,char *arg[]) {

    int array[100] = { -5, -9, 1000, 1, -10, 0, 2, 3, 5, 4, 1234, 7 };
    int i = 12,j,k,n;

    n=i;
    for (j = 0; j<i; j++)
    {
        printf("Broj: %d\n", array[j]);
    }

    bucketSort(array, n); 
    for (k = 0; k<i; k++)
        printf("%d \n", array[k]);   


    return 0;
}

Answer 2

Your code exhibits Undefined Behavior as you try to write into memory location which are not owned by your program.

for (i = 0; i < *n; i++)
    (count[array[i]])++;

The above loop is causing the problem. You say that i is 4 which means that *n is also 4 and array contains 2 3 5 4. In the above code,count is an array of *n elements(in this case 4 elements) and the valid indices for the array are count[0],count[1],count[2] and count[3]. Doing

count[array[i]]

when i is zero is okay as it is same as count[2]. This is the same when i is 1 as it would be count[3] . After that ,when i is 4 and 5,count[4] and count[5] are wrong as you try to write to a invalid memory location.

Also,your code dosen't sort the values.