I am coding a program in C that sorts an array by using bucketSort. My code works. I can print the data structure and every element of the original array is in the right "bucket". I understand what a linked list is and how it works. But I couldn't understand very well how this part of the code works.
/*If the bucket has already another element, */
else
{
p -> next = buckets[index];
buckets[index] = p;
}
And it is not very clear to me how the last node of the linked list is going to points to NULL to indicate the end of the linked list?
bucketSort Function:
void bucketSort(float arr[], int arr_length)
{
/*Sort an array within elements from [0, 1). We are going to use insertion sort
as a subroutine.
Assume arr contains elements from [0, 1)*/
//Initialize empty buckets.
for (int i = 0; i < NBUCKETS; i++)
{
buckets[i] = NULL;
}
//Fill the buckets with respective elements
for (int i = 0; i < arr_length; i++)
{
node *p = malloc(sizeof(node));
//Check if malloc has succeeded in getting memory
if (p == NULL)
{
printf("Something went wrong!\n");
exit(1);
}
//Get index of element arr[i]
int index = getBucketIndex(arr[i]);
//Assign the element arr[i] to the data structure
p -> data = arr[i];
//If data is the first element of bucket do the following...
if (buckets[index] == NULL)
{
buckets[index] = p;
}
/*If the bucket has already another element, */
else
{
p -> next = buckets[index];
buckets[index] = p;
}
}
When the bucket array is initially created, all buckets are usually marked empty, as follows:
buckets[0] -> NULL
buckets[1] -> NULL
Then let's say you want to insert a new element 42 in the first bucket. You have it pointed to via p and pointing to some random location as its next element:
p -> (42) -> ?
This is what happens when you run your code to insert the first item (which doesn't actually need a special case provided you already have the bucket pointing to NULL:
// buckets[0] -> NULL
// p -> (42) -> ?
p -> next = buckets[index]; // p -> (42, NULL)
buckets[index] = p; // buckets[0] -> (42, NULL) -> NULL
And this is what happens when you run your code to insert the second item 99:
// buckets[0] -> (42) -> NULL
// p -> (99) -> ?
p -> next = buckets[index]; // p -> (99) -> (42) -> NULL
buckets[index] = p; // buckets[0] -> (99) -> (42) -> NULL
In other words, it just inserts the new item at the start of the list (empty or otherwise).
You are absolutely correct that the code you posted is not safe. In the event that the bucket is currently empty, there is no statement that sets the next pointer of the new item to NULL, almost certainly leading to corrupted structures.
The good news is, as mentioned above, that you can simply throw away the if block and do the else block unconditionally, assuming the buckets are correctly initialised to NULL (and this seems to be likely based on the fact the original code if explicitly checking that to decide if a bucket is empty).