Posted By

jamessiene on 10/10/10


Tagged

algorithm practice bucket-sort


Versions (?)

Bucket Sort


 / Published in: C++
 

  1. /*
  2.   @James Siene - October 10th, 2010
  3.   - This program is a simple demonstration of a bucket-sort algorithm
  4.   *it displays the amount of time it takes to do the specified sort
  5. */
  6. #include <iostream.h>
  7. #include <time.h>
  8.  
  9. // This is all for memory allocation/manipulation/free
  10. #include <stdlib.h>
  11. #include <stdio.h>
  12. #include <string.h>
  13.  
  14. void bucketSort(int *inArr, int arrSize, int variance);
  15.  
  16. int main(void){
  17.  
  18. // We'll let the user enter the length and variance of the array
  19. int listSize, nodeVariance;
  20.  
  21. cout << "Enter a size for the list to be sorted: ";
  22. cin >> listSize;
  23.  
  24. cout << "Enter a numeric variance for each node in the list: ";
  25. cin >> nodeVariance;
  26.  
  27. // We'll generate a list, and fill it with random values.
  28. int *list = (int*)malloc(sizeof(int) * listSize);
  29.  
  30. srand(time(NULL));
  31.  
  32. for (int i = 0; i < listSize; i++){
  33. list[i] = rand() % nodeVariance;
  34. }
  35.  
  36. // We'll time the function to see how long it takes.
  37. time_t startTime, endTime;
  38. startTime = clock();
  39.  
  40. bucketSort(list, listSize, nodeVariance);
  41.  
  42. endTime = clock();
  43. int timeDiff = (int)(difftime(endTime, startTime) * 10.0);
  44.  
  45. cout << "The bucket-sort algorithm took approximately " << timeDiff << " ms to execute." << endl;
  46.  
  47. free(list);
  48.  
  49. return 0;
  50. }
  51.  
  52.  
  53. void bucketSort(int *inArr, int arrSize, int variance){
  54. int *bucket = (int*)malloc(sizeof(int) * variance);
  55. // Initialize all bucket nodes to have a count of 0
  56. memset(bucket, 0, sizeof(int) * variance);
  57. // Throw the count of each node into the bucket
  58. for (int i = 0; i < arrSize; i++){
  59. bucket[inArr[i]]++;
  60. }
  61. // We'll fill the new array with whatever is in the bucket
  62. int newArrayPosition = 0;
  63. for (int x = 0; x < variance; x++){
  64. for (int j = 0; j < bucket[x]; j++){
  65. inArr[j + newArrayPosition] = x;
  66. }
  67. newArrayPosition += bucket[x];
  68. }
  69.  
  70. free(bucket);
  71. }

Report this snippet  

You need to login to post a comment.