Bucket

Bucket sort permutes an array of integer values to lie in ascending numerical order. It does so using an auxiliary array to speed up the process. This sort is extremely fast in applications when there is a small range of input values compared with the total number of values. This particular implementation is a special case of bucket sort sometimes referred to as counting sort. The time complexity of bucket sort is:

(1)

where: m is the range input values, n is the total number of values in the array. Bucket sort beats all other sorting routines in time complexity. It should only be used when the range of input values is small compared with the number of values. In other words, occasions when there are a lot of repeated values in the input. Bucket sort works by counting the number of instances of each input value throughout the array. It then reconstructs the array from this auxiliary data. This implementation has a configurable input range, and will use the least amount of memory possible.

#include <stdlib.h>
#include <time.h>

#include <codecogs/computing/sort/bucket.h>

int main()
{
  int vals[25];
  int n=25;

  srand(time(0));
  for (int i=0; i<n; i++) vals[i]=(int)((double) n*rand())/RAND_MAX;

  printf("\nArray to be sorted:\n");
  for (int i=0; i<n; i++) printf("%i ", vals[i]);
  printf("\n");

  Array::Sort::bucketSort<int>(vals, n, 0, 25);

  printf("Sorted array:\n");
  for (int i=0; i<n; i++) printf("%i ", vals[i]);
  printf("\n");
  return 0;
}

Array to be sorted:
 12  23  10  23   4
  2   9  19  14  16
 22   5   7  16   1
  6   8  24  13  21
  9  17   1   3   6
Sorted array:
  1   1   2   3   4
  5   6   6   7   8
  9   9  10  12  13
 14  16  16  17  19
 21  22  23  23  24

Parameters