Jump to content

Algorithm Implementation/Sorting/Counting sort

From Wikibooks, open books for an open world
/* 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);
}
import 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
function 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