## Posted By

jamessiene on 10/10/10

# Bucket Sort

/ Published in: C++

`/*  @James Siene - October 10th, 2010  - This program is a simple demonstration of a bucket-sort algorithm    *it displays the amount of time it takes to do the specified sort*/#include <iostream.h>#include <time.h> // This is all for memory allocation/manipulation/free#include <stdlib.h> #include <stdio.h>#include <string.h> void bucketSort(int *inArr, int arrSize, int variance); int main(void){   // We'll let the user enter the length and variance of the array  int listSize, nodeVariance;   cout << "Enter a size for the list to be sorted: ";  cin  >> listSize;   cout << "Enter a numeric variance for each node in the list: ";  cin  >> nodeVariance;   // We'll generate a list, and fill it with random values.  int *list = (int*)malloc(sizeof(int) * listSize);   srand(time(NULL));   for (int i = 0; i < listSize; i++){    list[i] = rand() % nodeVariance;  }   // We'll time the function to see how long it takes.  time_t startTime, endTime;  startTime = clock();   bucketSort(list, listSize, nodeVariance);   endTime = clock();  int timeDiff = (int)(difftime(endTime, startTime) * 10.0);   cout << "The bucket-sort algorithm took approximately " << timeDiff << " ms to execute." << endl;   free(list);   return 0;}  void bucketSort(int *inArr, int arrSize, int variance){  int *bucket = (int*)malloc(sizeof(int) * variance);    // Initialize all bucket nodes to have a count of 0  memset(bucket, 0, sizeof(int) * variance);  // Throw the count of each node into the bucket  for (int i = 0; i < arrSize; i++){    bucket[inArr[i]]++;  }  // We'll fill the new array with whatever is in the bucket  int newArrayPosition = 0;  for (int x = 0; x < variance; x++){    for (int j = 0; j < bucket[x]; j++){      inArr[j + newArrayPosition] = x;      }    newArrayPosition += bucket[x];  }   free(bucket);}`