I have forgotten
my Password

Or login with:

  • Facebookhttp://facebook.com/
  • Googlehttps://www.google.com/accounts/o8/id
  • Yahoohttps://me.yahoo.com
COST (GBP)
this unit 3.00
sub units 0.00
+
0
ComputingSort

Bucket

Bucket sort an array of integer values into ascending numerical order.
Controller: CodeCogs

Interface

C++

BucketSort

 
template<class T> voidbucketSortT*vals
unsigned intn
Tlo
Thi )
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

valsthe array of values to be sorted
nthe number of items in the array
lothe lowest input value in the array
hithe 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.