# Bucket Sort

Bucket sort (a.k.a Bin Sort) is a sorting algorithm that works by partitioning an array into a number buckets. Each bucket then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm.

```									```struct Bucket {
int* Data;
int Count;
};

int* AddItemInArray(int** arr, int count, int item) {
int* newArr = malloc(sizeof(int) * (count + 1));

for (int i = 0; i < count; i++) {
newArr[i] = arr[i];
}

newArr[count] = item;

return newArr;
}

void BucketSort(int* data, int count) {
int minValue = data;
int maxValue = data;

for (int i = 1; i < count; i++)
{
if (data[i] > maxValue)
maxValue = data[i];
if (data[i] < minValue)
minValue = data[i];
}

int bucketLength = maxValue - minValue + 1;
struct Bucket* bucket = malloc(sizeof(struct Bucket) * bucketLength);

for (int i = 0; i < bucketLength; i++)
{
bucket[i] = *(struct Bucket*)malloc(sizeof(struct Bucket));
}

for (int i = 0; i < count; i++)
{
struct Bucket b = bucket[data[i] - minValue];
if (b.Count < 0) {
b.Count = 0;
}

bucket[data[i] - minValue].Data = AddItemInArray(b.Data, b.Count++, data[i]);
bucket[data[i] - minValue].Count = b.Count;
}

int k = 0;
for (int i = 0; i < bucketLength; i++)
{
int bucketSize = bucket[i].Count;

if (bucketSize > 0)
{
for (int j = 0; j < bucketSize; j++)
{
data[k] = bucket[i].Data[j];
k++;
}
}
}
}```
```

### Example

```									```int data[] = { -1, 25, -58964, 8547, -119, 0, 78596 };
BucketSort(data, 7);```
```

### Output

```									```-58964
-119
-1
0
25
8547
78596```
```