c - Segmentation fault in bucket sort + insertion sort algorithm -

i'd know why algorithm implemented bucket sort getting segmentation fault result. seems in implementation working nicely there's variable n should n+1 or whatever; i'm experiencing difficulty figuring 1 out.

i'm implementing according described in this video.

#include <stdio.h> #include <stdlib.h>  void insertion(int * array, int n){     // insertion sort     int = 1, j = 0, temp;     while(i < n){         j = i;         while(j > 0 && array[j-1] > array[j]){             temp = array[j-1];             array[j-1] = array[j];             array[j] = temp;             --j;         }         ++i;     } }  void bucket(int * array, int n){     int max,i,j,k,size, div, pos;     int ** buckets, *bucket_position;      //find maximum value in array     max = array[0];     for(i=0;i<n;++i) if( max < array[i] ) max = array[i];      //determine amount of buckets , creates them     size = max / n;     buckets = (int**) malloc(sizeof(int*) * size);     for(i=0;i<size;++i){         buckets[i] = (int*) malloc(sizeof(int) * max);     }     bucket_position = (int*) malloc(sizeof(int) * size);     for(i=0;i<size;++i) bucket_position[i] = 0;      //copy array values buckets     div = (max+1) / size;     if( (max+1) % size ) ++div;     for(i=0;i<n;++i){         pos = array[i] / div;         buckets[pos][bucket_position[pos]] = array[i];         ++bucket_position[pos];     }      //take values out of buckets array     k = 0;       for(i=0;i<size;++i){         for(j=0;j<=bucket_position[i];++j){             array[k] = buckets[i][j];             ++k;         }     }      //do insertion sort on array     insertion(array,n); }  int main(){     int array[5] = {24354,95023,439052,934851};     int n = 5;     bucket(array,n);     return 0; } 

program output segmentation fault instead of sorted array.

you want sort array n == 5 elements, maximum vlaue is:

max == 934851 

then calculate nuber of buckets:

size = max / n == 186970 

now try allocate memory 186970 buckets, each capacity hold 934851 elements:

buckets = (int**) malloc(sizeof(int*) * size);  (i = 0; < size; ++i) {     buckets[i] = (int*) malloc(sizeof(int) * max); } 

that's 651 gigabytes. many large allocations, system can't provide more memory. should therefore check whether pointers returned malloc null. , that's happens: array indices legal, dynamically allocated arrays null.

of course don't need memory sort 5 elements. such small array, shouldn't need use buckets @ all; use insertion sort straight away.

for larger arrays, base number of buckets on number of elements, not on maximum value. in worst case, elements go 1 bucket, have n elements. don't need max determine size here, either.

you should use max , min, program doesn't have, calculate bucket index, however:

index = (a[i] - min) * nbuckets / (max + 1 - min) 

be aware of possible arithmetic overflow here. (the + 1 ensures maximum element doesn't invalid index ´n´.)