Getting malloc assertion error in bin sort algorithm

Question

These is a bin sort program. I have found other approaches on the net but my instructor thought us these way. I am a beginner to programming please help me with the code.

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

struct Node{
  int data;
  struct Node *next;
};


//Print array function
void printArray(int arr[], int n){
  for(int i=0; i<n; i++)
    printf("%d ",arr[i]);
  printf("\n");
} 

//findMax function for count and bin/bucket sort
int findMax(int arr[], int n){
  int max = INT_MIN;
  for(int i=0; i<n; i++){
    if(arr[i]>max) max=arr[i];
  }
  return max;
}

//insert function for bins sort
void Insert(struct Node *Bins[], int index){
  struct Node *t;
  t=(struct Node*)malloc(sizeof(struct Node));
  t->data = index;
  t->next=NULL;
  if(Bins[index] != NULL){
    while(Bins[index] == NULL)
      Bins[index]= Bins[index]->next;
    Bins[index]->next = t;
  }
  else
    Bins[index] = t;
}

//delete function for bin/bucket sort
int Delete(struct Node *Bins[], int i){
  int x;
  if(Bins[i]->next !=NULL){
    struct Node *temp;
    temp=(struct Node*)malloc(sizeof(struct Node));
    temp=Bins[i]->next;
    x=Bins[i]->data;
    free(Bins[i]);
    Bins[i] = temp;
  }
  else{
    x = Bins[i]->data;
    free(Bins[i]);
  }
  return x;
}

// bin/bucket sort
void BinSort(int arr[], int n){
  int max, i, j;
  struct Node **Bins;
  Bins =(struct Node**)malloc(sizeof(struct Node*));
  max = findMax(arr, n);
   for(i =0; i<max+1; i++) 
    Bins[i] = NULL;
  for(i=0; i<n; i++)
    Insert(Bins, arr[i]);
  i=j=0;
  while(i < max+1){
    while(Bins[i] != NULL)  
      arr[j++] = Delete(Bins, i);
  i++;
  }
}

int main(){
  int n=10;
  int arr[] = {8,5,7,5,3,2,6,4,11,5};
  BinSort(arr, n);
  printArray(arr, n);
  return 0;
}

The program uses a auxiliary array for maintaining the count of elements but using a linked list, i have written insert and delete function accordingly.

You are doing `temp=(struct Node*)malloc(sizeof(struct Node)); temp=Bins[i]->next;` so the second line is _trashing_ the pointer you just got from `malloc`. Probably _not_ what you want and _is_ a memory leak. — Craig Estey, Jun 28 '21 at 17:29
There are no assertions. How can you be getting an assertion error? — William Pursell, Jun 28 '21 at 17:48
I think they have a debugging allocator which has asserted internally .... but I _do wish_ they'd pasted the error message instead of only alluding to it. — Useless, Jun 28 '21 at 17:48

score 1 · Answer 1 · answered Jun 28 '21 at 17:27

The line

Bins =(struct Node**)malloc(sizeof(struct Node*));

is wrong. You are using max+1 elements, but you are allocating only one element. You have to allocate max+1 elements.

In other words, the line should be:

Bins = malloc(sizeof(struct Node*) * (max+1));

or

Bins = malloc(sizeof(*Bins) * (max+1));

Also note that casting results of malloc() family is considered as a bad practice.

Getting malloc assertion error in bin sort algorithm

1 Answers1