Algorithm Implementation/Sorting/Counting sort
(Redirected from Algorithm implementation/Sorting/Counting sort)
/* end is the last index + 1 */
void csort(int array[], const int end, const int max, const int min)
{
int i;
const int range = max-min+1;
int count[range+1],
scratch[end];
for(i=0; i<range+1; i++)
count[i] = 0;
/* Set the value of count[i] to the number of
* elements in array with value i+min-1. */
for(i=0; i<end; i++) {
int c = array[i]+1-min;
count[c]++;
}
/* Update count[i] to be the number of
* elements with value less than i+min. */
for(i=1; i<range; i++)
count[i] + = count[i-1];
/* Copy the elements of array into scratch in
* stable sorted order. */
for(i=(end-1); i>=0; i--) {
int c = array[i]-min;
int s = count[c];
scratch[s] = array[i];
/* Increment count so that the next element
* with the same value as the current element
* is placed into its own position in scratch. */
count[c]++;
}
for(i=0; i<end; i++)
array[i] = scratch[i];
}
#include <vector>
#include <algorithm>
/*
To sort a sequence using an integer key having a known range,
you must define a function-object that, given an element, returns a zero-based key.
The sorting is performed by calling the "counting_sort" function template,
passing to it the sequence extremes, the maximum number of keys, and the function-object.
If the sorted sequence must anyway be copied to another sequence,
it is more efficient to call the "counting_sort_copy" function template, passing to it the above
arguments plus a pointer or iterator at the beginning of the destination sequence.
If this algorithm must be called several times, it is further more efficient to call
the "counting_sort_copy_with_counters" function templates, passing to it the above arguments plus
a pointer or iterator to the beginning of the auxiliary buffer used by the algorithm.
*/
/* Function template "counting_sort_copy_with_counters".
Input:
- The sequence to sort, between the pointers or bidirectional iterator
"begin_to_sort" and "end_to_sort".
- The sequence in which to copy the sorted elements, beginning at the address referenced
by the pointer or random iterator "sorted",
and having as many elements as the sequence to sort
- The sequence in which to store the temporary counters, beginning at the address referenced
by the pointer or random iterator "counters", and containing "n_keys" elements.
- The maximum number of keys: "n_keys".
- The function-object "get_key" that, for any element of the sequence,
returns its key as an ingeger number in the range [0, n_keys - 1].
Output:
- The sequence beginning at the address referenced by "sorted", sorted by the key.
Example of usage, where it is assumed that "arr" contains only
integer numbers between 1000 and 1039:
struct get_key {
int operator()(const int& i) const { return i - 1000; }
};
int arr[100];
int sorted[100];
int counters[40];
counting_sort_copy_with_counters(arr, arr + 100, sorted, counters, 40,
get_key());
other example, where it is assumed that "lst" contains only structures
whose "i" field has a value between 1000 and 1039:
struct S { double d; int i; };
int get_key(const S& s) { return s.i - 1000; }
std::list<S> lst;
S sorted[100];
int counters[40];
counting_sort_copy_with_counters(lst.begin(), lst.end(), sorted,
counters, 40, get_key);
*/
template<typename BidIt, typename RanIt, typename IntRanIt, class Functor>
void counting_sort_copy_with_counters(
BidIt begin_to_sort, BidIt end_to_sort,
RanIt sorted, IntRanIt counters,
size_t n_keys, Functor get_key)
{
std::fill_n(counters, n_keys, 0);
for (BidIt it = begin_to_sort; it != end_to_sort; ++it) {
++counters[get_key(*it)];
}
for (IntRanIt it = counters + 1; it != counters + n_keys; ++it) {
*it += *(it - 1);
}
for (BidIt it = end_to_sort; it != begin_to_sort; ) {
sorted[--counters[get_key(*--it)]] = *it;
}
}
/* Function template "counting_sort_copy".
Input:
- The sequence to sort, between the pointers or bidirectional iterator
"begin_to_sort" and "end_to_sort".
- The sequence in which to copy the sorted elements, beginning at the address referenced
by the pointer or random iterator "sorted",
and having as many elements as the sequence to sort.
- The maximum number of keys: "n_keys".
- The function-object "get_key" that, for any element of the sequence,
returns its key as an ingeger number in the range [0, n_keys - 1].
Output:
- The sequence beginning at the address referenced by "sorted", sorted by the key.
Internally, a temporary vector is created, containing "n_keys" ints.
Example of usage, where it is assumed that "arr" contains only
integer numbers between 1000 and 1039:
struct get_key {
int operator()(const int& i) const { return i - 1000; }
};
int arr[100];
int sorted[100];
counting_sort_copy(arr, arr + 100, sorted, 40, get_key());
other example, where it is assumed that "lst" contains only structures
whose "i" field has a value between 1000 and 1039:
struct S { double d; int i; };
int get_key(const S& s) { return s.i - 1000; }
std::list<S> lst;
S sorted[100];
counting_sort_copy(lst.begin(), lst.end(), sorted, 40, get_key);
*/
template<typename BidIt, typename RanIt, class Functor>
void counting_sort_copy(
BidIt begin_to_sort, BidIt end_to_sort,
RanIt sorted,
size_t n_keys, Functor get_key)
{
std::vector<int> counters(n_keys);
counting_sort_copy_with_counters(begin_to_sort, end_to_sort, sorted,
counters.begin(), n_keys, get_key);
}
/* Function template "counting_sort".
Input:
- The sequence to sort, between the pointers or bidirectional iterator
"begin_to_sort" and "end_to_sort".
- The maximum number of keys: "n_keys".
- The function-object "get_key" that, for any element of the sequence,
returns its key as an ingeger number in the range [0, n_keys - 1].
Output:
- The sequence between "begin_to_sort" and "end_to_sort", sorted by the key.
Internally, a temporary vector is created, containing a copy
of the sorted sequence, and another temporary vector containing "n_keys" ints.
Example of usage, where it is assumed that "arr" contains only
integer numbers between 1000 and 1039:
struct get_key {
int operator()(const int& i) const { return i - 1000; }
};
int arr[100];
counting_sort(arr, arr + 100, 40, get_key());
other example, where it is assumed that "lst" contains only structures
whose "i" field has a value between 1000 and 1039:
struct S { double d; int i; };
int get_key(const S& s) { return s.i - 1000; }
std::list<S> lst;
counting_sort(lst.begin(), lst.end(), 40, get_key);
*/
template<typename BidIt, class Functor>
void counting_sort(
BidIt begin_to_sort, BidIt end_to_sort,
size_t n_keys, Functor get_key)
{
std::vector<typename std::iterator_traits<BidIt>::value_type>
sorted(std::distance(begin_to_sort, end_to_sort));
counting_sort_copy(begin_to_sort, end_to_sort, sorted.begin(), n_keys,
get_key);
copy(sorted.begin(), sorted.end(), begin_to_sort);
}
Java
editimport java.util.Arrays;
public static void countingSort(int[] a, int low, int high)
{
int[] counts = new int[high - low + 1]; // this will hold all possible values, from low to high
for (int x : a)
counts[x - low]++; // - low so the lowest possible value is always 0
int current = 0;
for (int i = 0; i < counts.length; i++)
{
Arrays.fill(a, current, current + counts[i], i + low); // fills counts[i] elements of value i + low in current
current += counts[i]; // leap forward by counts[i] steps
}
}
JavaScript implementation with simple HTML test page
<html>
<head>
<script type="text/javascript">
// GLOBAL FUNCTION
Array.prototype.counting_sort = function() {
var i, j, k;
// find min, max to set range of counts array
var min = this[0];
var max = this[0];
for(i=0; i<this.length; i++) {
if (min > this[i])
min = this[i];
else if (max < this[i])
max = this[i];
}
var counts = []
var newarray = []
// initialize counts array
for(i=0; i<max-min+1; i++) {
counts[i] = 0;
}
// count distinct values from input array array
for(i=0; i<this.length; i++) {
counts[this[i]-min]++;
}
k = 0
// write output values ordered by counts index
// replicate output value according to repeat count
for(i=0; i<counts.length; i++) {
for(j=0; j<counts[i]; j++) {
newarray[k++] = i + min;
}
}
return(newarray)
}
// LOCAL FUNCTION
show = function (inarray, arrayname) {
document.writeln("<h4>"+arrayname+":</h4>");
for(i=0; i<inarray.length; i++)
document.write(inarray[i]+((i+1==inarray.length)?"":", "));
document.writeln("<br />");
}
</script>
</head>
<body>
<script>
// MAIN
// test counting_sort function
sorted_array = [1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1].counting_sort();
// result: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7]
show(sorted_array, "Sorted Array");
</script>
</body>
</html>
use List::Util qw(max min);
sub counting_sort {
my $max = &max;
my $min = &min;
# make an array of each value, with the number of times it occurs.
# subtract min, to normalize as well as to allow for negative numbers.
my $sz = $max - $min + 1;
my @counts= (0) x $sz; # initialization is actually optional since Perl
# promotes $counts[$not_seen] from undef to 0
$counts[$_-$min]++ foreach @_;
# make a new sorted array, repeating values per counts array
# return new array implicitly
map { ($_ + $min) x $counts[$_] } (0..$sz);
}
# test:
my $sorted_list = join ", ", counting_sort(1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1);
print "$sorted_list\n";
# prints: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7
Phix
editfunction countingSort(sequence array, integer mina, maxa)
sequence count = repeat(0,maxa-mina+1)
for i=1 to length(array) do
count[array[i]-mina+1] += 1
end for
integer z = 1
for i=mina to maxa do
for j=1 to count[i-mina+1] do
array[z] := i
z += 1
end for
end for
return array
end function
Note: that this implementation does not need the temporary scratch array. It sorts in-place, except it needs the counting array. The emit step does not copy original values from the input array but creates new ones.
#!/usr/bin/env python
def counting_sort(array, maxval):
"""in-place counting sort"""
m = maxval + 1
count = [0] * m # init with zeros
for a in array:
count[a] += 1 # count occurences
i = 0
for a in range(m): # emit
for c in range(count[a]): # - emit 'count[a]' copies of 'a'
array[i] = a
i += 1
return (array,count)
print counting_sort( [1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1], 7 )
# prints: [1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7],[0, 4, 4, 2, 2, 0, 0, 1]
Unlike the Python version, this doesn't sort in-place, but returns a new array.
def counting_sort(array)
min = array.min
max = array.max
# make an array of each value, with the number of times it occurs.
# subtract min, to normalize as well as to allow for negative numbers.
counts = Array.new(max-min+1, 0);
array.each { |n| counts[n-min] += 1 }
# make a new sorted array, repeating values per counts array
# return new array implicitly
(0...counts.size).map { |i| [i + min] * counts[i] }.flatten
end
# test:
print counting_sort([1, 4, 7, 2, 1, 3, 2, 1, 4, 2, 3, 2, 1]).join(", ") + "\n"
# prints: 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 7