Bucket

Interface

BucketSort

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:

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.

Example 1

#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;
}

Output:

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

vals	the array of values to be sorted
n	the number of items in the array
lo	the lowest input value in the array
hi	the highest input value in the array

Authors

James Warren (July 2005)

Source Code

Source code is available when you buy a Commercial licence.

Not a member, then Register with CodeCogs. Already a Member, then Login.