Sorting algorithms/Counting sort: Difference between revisions

{{trans|Python}}

 

V cnt = [0] * (max - min + 1)

L(x) a

 

V data = [9, 7, 10, 2, 9, 7, 4, 3, 10, 2, 7, 10, 2, 1, 3, 8, 7, 3, 9, 5, 8, 5, 1, 6, 3, 7, 5, 4, 6, 9, 9, 6, 6, 10, 2, 4, 5, 2, 8, 2, 2, 5, 2, 9, 3, 3, 5, 7, 8, 4]

 

{{out}}

 

=={{header|360 Assembly}}==

COUNTS CSECT

USING COUNTS,R13 base register

COUNT DC 200F'0' count

REGEQU

{{out}}

<pre>

=={{header|AArch64 Assembly}}==

{{works with|as|Raspberry Pi 3B version Buster 64 bits}}

/* ARM assembly AARCH64 Raspberry PI 3B */

/* program countSort64.s */

/* for this file see task include a file in language AArch64 assembly */

.include "../includeARM64.inc"

 

=={{header|Action!}}==

 

PROC PrintArray(INT ARRAY a INT size)

Test(c,8,101,108)

Test(d,12,-1,1)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Counting_sort.png Screenshot from Atari 8-bit computer]

 

=={{header|ActionScript}}==

{

var count:Array = new Array(array.length);

}

return array;

 

=={{header|Ada}}==

Given that we know the range of data, the problem really reduces to initializing the array to the ordered range of values. The input order is irrelevant.

 

procedure Counting_Sort is

end loop;

New_Line;

===Output===

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

<br>

{{works with|ELLA ALGOL 68|Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386}}

(

INT z := LWB array - 1;

FOR i TO UPB ages DO print((" ", whole(ages[i],0))) OD;

print(new line)

Sample output:

 

=={{header|ARM Assembly}}==

{{works with|as|Raspberry Pi}}

/* ARM assembly Raspberry PI */

/* program countSort.s */

/***************************************************/

.include "../affichage.inc"

=={{header|Arturo}}==

 

a: new items

rng: inc maximum - minimum

]

 

 

{{out}}

=={{header|ATS}}==

 

 

(* My ATS solution to the radix sort task includes a counting sort for

for (i := 0; i <> 8; i := succ i)

println! (arr[i].0, " -> ", arr[i].1)

 

{{out}}

=={{header|AutoHotkey}}==

contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276465.html#276465 forum]

 

CountingSort(ints,min,max) {

}

Return SubStr(t,2)

 

=={{header|BASIC256}}==

# counting sort

 

next i

print

 

=={{header|BBC BASIC}}==

test%() = 4, 65, 2, -31, 0, 99, 2, 83, 782, 1

PROCcountingsort(test%(), -31, 782)

ENDWHILE

NEXT

'''Output:'''

<pre>

 

=={{header|C}}==

#include <stdlib.h>

 

}

}

 

Testing (we suppose the oldest human being is less than 140 years old).

 

#define MAX_AGE 140

int main()

for(i=0; i < N; i++) printf("%d\n", ages[i]);

return EXIT_SUCCESS;

 

=={{header|C sharp|C#}}==

using System.Linq;

 

}

}

 

=={{header|C++}}==

#include <iostream>

#include <time.h>

}

//------------------------------------------------------------------------------

{{out}}

<pre>

Uses C++11. Compile with

g++ -std=c++11 counting.cpp

#include <iterator>

#include <iostream>

copy(std::begin(a), std::end(a), std::ostream_iterator<int>(std::cout, " "));

std::cout << "\n";

Output:

<pre>

Straightforward implementation of counting sort. By using <code>[http://www.lispworks.com/documentation/HyperSpec/Body/f_map.htm map]</code> and <code>[http://www.lispworks.com/documentation/HyperSpec/Body/f_map_in.htm map-into]</code>, counting sort can work efficiently on both lists and vectors. The closure given as the second argument to <code>map-into</code> returns the sorted elements of sequence. Because <code>map-into</code> will only call the function as many times as necessary to re-populate sequence, there is no need for bounds checking. <code>counts</code> is declared to have dynamic-extent and so a compiler might stack allocate it.

 

(max (reduce #'max sequence)))

(let ((i 0)

(incf i))

(decf (aref counts i))

 

=={{header|D}}==

 

void countingSort(int[] array, in size_t min, in size_t max)

countingSort(data, dataMin, dataMax);

assert(isSorted(data));

 

=={{header|Delphi}}==

Straightforward implementation, no particularly interesting characteristics.

 

def counts := ([0] * (max - min + 1)).diverge()

for elem in array {

}

}

 

<pre style="height:15ex;overflow:scroll">? def arr := [34,6,8,7,4,3,56,7,8,4,3,5,7,8,6,4,4,67,9,0,0,76,467,453,34,435,37,4,34,234,435,3,2,7,4,634,534,735,5,4,6,78,4].diverge()

=={{header|Eiffel}}==

 

 

class

 

end

TEST:

class

APPLICATION

end

 

{{out}}

<pre>

=={{header|Elena}}==

ELENA 4.x :

import system'routines;

console.printLine("before:", list.asEnumerable());

console.printLine("after :", list.countingSort().asEnumerable())

{{out}}

<pre>

=={{header|Elixir}}==

{{works with|Elixir|1.1}}

def counting_sort([]), do: []

def counting_sort(list) do

end

 

 

{{out}}

{{works with|Fortran|95 and later}}

 

implicit none

 

end subroutine counting_sort_mm

 

 

Testing:

 

use CountingSort

implicit none

write(*,'(I4)') ages

 

 

=={{header|FreeBASIC}}==

 

Function findMax(array() As Integer) As Integer

Print

Print "Press any key to quit"

 

{{out}}

=={{header|Go}}==

This version follows the task pseudocode above, with one more optimization.

 

import (

}

}

This version follows the WP pseudocode. It can be adapted to sort items other than integers.

 

import (

}

copy(a, output)

 

=={{header|Groovy}}==

Solution:

def max = array.max()

def min = array.min()

array.each { count[it] ++ }

(min..max).findAll{ count[it] }.collect{ [it]*count[it] }.flatten()

 

Test:

println countingSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1])

 

println countingSort([34,6,8,7,4,3,56,7,8,4,3,5,7,8,6,4,4,67,9,0,0,76,467,453,34,435,37,4,34,234,435,3,2,7,4,634,534,-735,5,4,6,78,4])

// slo-o-o-o-ow due to unnecessarily large counting array

 

Output:

We use lists for input and output rather than arrays, since lists are used more often in Haskell.

 

countingSort :: (Ix n) => [n] -> n -> n -> [n]

countingSort l lo hi = concatMap (uncurry $ flip replicate) count

 

=={{header|Haxe}}==

{{trans|C}}

public static function sort(arr:Array<Int>) {

var min = arr[0], max = arr[0];

Sys.println('Sorted Integers: ' + integerArray);

}

 

{{out}}

The following example is hopefully in the spirit of a counting sort using a hash table as a substituted for a sparse array. Simply translating the pseudo-code would be very un-Iconish (as opposed to Uniconish).

 

write("Sorting Demo using ",image(countingsort))

writes(" on list : ")

every put(X := [],( 1 to T[i := lower to upper], i) ) # reconstitute with correct order and count

return X

 

Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'display sort', and 'writex' from Bubble Sort]].

=={{header|Io}}==

{{trans|Java}}

countingSort := method(min, max,

count := list() setSize(max - min + 1) mapInPlace(0)

 

l := list(2, 3, -4, 5, 1)

 

A more functional-like version:

fill := method(x, size,

/* Resizes list to a given size and fills it with a given value. */

 

l := list(2, 3, -4, 5, 1)

 

=={{header|IS-BASIC}}==

100 PROGRAM "CountSrt.bas"

110 RANDOMIZE

540 LOOP

550 NEXT

 

=={{header|J}}==

{{eff note|J|/:~}}

min =. <./y

cnt =. 0 $~ 1+(>./y)-min

end.

cnt # min+i.#cnt

 

Alternative implementation:

 

 

 

'''Example:'''

_2 _2 6 _1 1 6 _1 4 4 1 4 4 5 _3 5 3 0 _1 3 4

 

csort a

 

And note that this can be further simplified if the range is known in advance (which could easily be the case -- this sorting mechanism is practical when we have a small fixed range of values that we are sorting). Here, we do not need to inspect the data to find min and max values, since they are already known:

 

(m+i.n-m) (+/@(=/)~ # [) ]

 

or

 

(+/@(=/) # ])&(m+i.n-m)

 

Example:

 

 

=={{header|Java}}==

{{works with|Java|1.5+}}

int[] count= new int[max - min + 1];

for(int number : array){

}

}

 

=={{header|JavaScript}}==

 

var i, z = 0, count = [];

}

 

Testing:

 

 

var i, ages = [];

for (i = 0; i < 100; i++) {

document.write(ages[i] + "<br />");

 

=={{header|jq}}==

object is used instead. This ensures the space requirement is just O(length). In jq, this approach is both time and space

efficient, except for the small cost of converting integers to strings, which is necessary because JSON keys must be strings.

. as $in

| reduce range(0;length) as $i

else reduce range(0; $hash[$s]) as $j (.; . + [$i])

end

'''Example''':

{{out}}

$ jq -M -c -n -f counting_sort.jq

 

=={{header|Julia}}==

This is a translation of the pseudocode presented in the task description, accounting for the fact that Julia arrays start indexing at 1 rather than zero and taking care to return a result of the same type as the input. Note that <code>cnt</code> has the machine's standard integer type (typically <code>Int64</code>), which need not match that of the input.

 

lo, hi = extrema(a)

b = zeros(a)

println("# unsorted bytes: $v\n -> sorted bytes: $(countsort(v))")

v = rand(1:2 ^ 10, 20)

 

{{out}}

 

=={{header|Kotlin}}==

 

fun countingSort(array: IntArray) {

countingSort(array)

println("Sorted : ${array.asList()}")

 

{{out}}

Prior to 0.10, multi-variable declaration/assignment would use parentheses around variable names and values.

 

val .min, .max = minmax(.array)

var .count = arr .max-.min+1, 0

 

writeln "Original: ", .data

 

{{out}}

 

=={{header|Lua}}==

local min, max = math.min( unpack(f) ), math.max( unpack(f) )

local count = {}

for i in next, f do

print( f[i] )

 

=={{header|M4}}==

 

define(`randSeed',141592653)

show(`a')

countingsort(`a',0,99)

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

minElem = Min[list]; maxElem = Max[list];

count = ConstantArray[0, (maxElem - minElem + 1)];

count[[i - minElem + 1]] = count[[i - minElem + 1]] - 1;]

];

<pre>countingSort@{2, 3, 1, 5, 7, 6}

->{1, 2, 3, 5, 6, 7}</pre>

This is a direct translation of the pseudo-code, except to compensate for MATLAB using 1 based arrays.

 

 

minElem = min(list);

end

 

Sample Usage:

 

ans =

 

 

=={{header|MAXScript}}==

fn countingSort arr =

(

)

return arr

{{out}}

a = for i in 1 to 15 collect random 1 30

#(7, 1, 6, 16, 27, 11, 24, 16, 25, 11, 22, 7, 28, 15, 17)

countingSort a

#(1, 6, 7, 7, 11, 11, 15, 16, 16, 17, 22, 24, 25, 27, 28)

 

=={{header|Modula-3}}==

 

IMPORT IO, Fmt;

END;

IO.Put("\n");

Output:

<pre>

=={{header|Nanoquery}}==

{{trans|Java}}

count = {0} * (max - min + 1)

 

end

end

 

=={{header|NetRexx}}==

===Version 1===

An almost direct implementation of the pseudocode.

options replace format comments java crossref savelog symbols binary

 

 

return array

{{out}}

<pre style="overflow: scroll;">

===Version 2===

A more Rexx-like (and shorter) version. Due to NetRexx's built in indexed string capability, negative values are also easily supported.

options replace format comments java crossref symbols nobinary

 

 

return

{{out}}

<pre>

 

=={{header|Nim}}==

let range = max - min + 1

var count = newSeq[T](range)

var a = @[5, 3, 1, 7, 4, 1, 1, 20]

countingSort(a, 1, 20)

Output:

<pre>@[1, 1, 1, 3, 4, 5, 7, 20]</pre>

 

=={{header|Objeck}}==

bundle Default {

class Cocktail {

}

}

 

=={{header|OCaml}}==

For arrays:

let count = Array.make (hi-lo+1) 0 in

Array.iter (fun i -> count.(i-lo) <- count.(i-lo) + 1) arr;

 

=={{header|Octave}}==

This implements the same algorithm but in a more compact way (using the same loop to count and to ''update'' the sorted vector). This implementation is ''elegant'' (and possible since the sort is not done "in place"), but not so efficient on machines that can't parallelize some operations (the vector <tt>arr</tt> is scanned for every value between <tt>minval</tt> and <tt>maxval</tt>)

r = arr;

z = 1;

endwhile

endfor

 

Testing:

 

sorted = counting_sort(ages, 0, 140);

 

=={{header|Oz}}==

Using arrays as in the original algorithm. The implementation is slightly simpler because arrays can start with an arbitrary index in Oz.

proc {CountingSort Arr Min Max}

Count = {Array.new Min Max 0}

in

{CountingSort A 1 9}

 

Using lists for input and output and a dictionary as a sparse array:

fun {CountingSort Xs}

Count = {Dictionary.new}

end

in

 

=={{header|PARI/GP}}==

my(u=vector(#v),i=0);

for(n=mn,mx,

);

u

 

=={{header|Pascal}}==

 

procedure counting_sort(var arr : Array of Integer; n, min, max : Integer);

for i := 0 to 99 do

writeln(ages[i]);

 

=={{header|Perl}}==

 

use strict;

 

my $i = $min;

@$a = map {($i++) x $_} @cnt;

 

Testing:

 

counting_sort(\@ages, 0, 140);

 

=={{header|Phix}}==

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>

<span style="color: #004080;">sequence</span> <span style="color: #000000;">s</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">7</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">20</span><span style="color: #0000FF;">}</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">countingSort</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">min</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">),</span><span style="color: #7060A8;">max</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span>

{{out}}

<pre>

=={{header|PHP}}==

 

 

function counting_sort(&$arr, $min, $max)

}

}

 

Testing:

 

for($i=0; $i < 100; $i++) {

array_push($ages, rand(0, 140));

echo $ages[$i] . "\n";

}

 

=={{header|PicoLisp}}==

(let Count (need (- Max Min -1) 0)

(for N Lst

(do (car C) (link (car I))) )

Count

Output:

 

 

=={{header|PL/I}}==

declare A(*) fixed;

declare (min, max) fixed;

end;

end;

 

=={{header|PowerShell}}==

function countingSort($array) {

$minmax = $array | Measure-Object -Minimum -Maximum

"$array"

"$(countingSort $array)"

<b>Output:</b>

<pre>

 

=={{header|PureBasic}}==

Define i, j

Dim c(max - min)

Wend

Next

 

=={{header|Python}}==

Follows the spirit of the counting sort but uses Pythons defaultdict(int) to initialize array accesses to zero, and list concatenation:

>>> def countingSort(array, mn, mx):

count = defaultdict(int)

>>> mini,maxi = 1,10

>>> countingSort(data, mini, maxi) == sorted(data)

 

Using a list:

{{works with|Python|2.6}}

cnt = [0] * (max - min + 1)

for x in a:

return [x for x, n in enumerate(cnt, start=min)

 

=={{header|Quackery}}==

 

unrot poke ] is [1+] ( [ n --> [ )

dup say "Before: " echo cr

10 19 csort

 

{{out}}

=={{header|R}}==

{{trans|Octave}}

r <- arr

z <- 1

ages <- floor(runif(100, 0, 140+1))

sorted <- counting_sort(ages, 0, 140)

 

=={{header|Racket}}==

#lang racket

 

 

(counting-sort (vector 0 9 3 8 1 -1 1 2 3 7 4) -1 10)

Output:

'#(-1 0 1 1 2 3 3 4 7 8 9)

 

=={{header|Raku}}==

(formerly Perl 6)

{{Works with|rakudo|2018.03}}

my $off = @ints.min;

(my @counts)[$_ - $off]++ for @ints;

say @ages.sort;

 

{{out}}

<pre>(5 5 5 7 9 17 19 19 20 21 25 27 28 30 32 34 38 40 41 45 48 49 50 51 53 54 55 56 59 62 65 66 67 69 70 73 74 81 83 85 87 91 91 93 94 96 99 99 100 101)

Negative, zero, and positive integers are supported.

===version 1===

$= '1 3 6 2 7 13 20 12 21 11 22 10 23 9 24 8 25 43 62 42 63 41 18 42 17 43 16 44 15 45 14 46 79 113 78 114 77 39 78 38'

#= words($); w= length(#); !.= 0 /* [↑] a list of some Recaman numbers.*/

return

/*──────────────────────────────────────────────────────────────────────────────────────*/

{{out|output|text=&nbsp; when using the default input:}}

 

 

{{trans|PL/I}}

* 13.07.2014 Walter Pachl translated from PL/I

*--------------------------------------------------------------------*/

End

Say ol

'''Output:'''

<pre>before count_sort

 

=={{header|Ring}}==

aList = [4, 65, 2, 99, 83, 782, 1]

see countingSort(aList, 1, 782)

next

return f

 

=={{header|Ruby}}==

def counting_sort!

replace counting_sort

# => [-3, -1, 9, -6, -8, -3, 5, -7, 4, 0, 5, 0, 2, -2, -6, 10, -10, -7, 5, -7]

p ary.counting_sort

 

=={{header|Rust}}==

 

mut data: Vec<usize>,

min: usize,

let arr3 = vec![10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];

println!("{:?}", counting_sort(arr3, 0, 10));

{{out}}

<pre>

 

=={{header|Scala}}==

input.foldLeft(Array.fill(max - min + 1)(0)) { (arr, n) =>

arr(n - min) += 1

}.zipWithIndex.foldLeft(List[Int]()) {

case (lst, (cnt, ndx)) => List.fill(cnt)(ndx + min) ::: lst

 

It's better (i.e. slightly faster) to reverse the frequencies list before processing it, instead of the whole result

input.foldLeft(Array.fill(max - min + 1)(0)) { (arr, n) =>

arr(n - min) += 1

}.zipWithIndex.reverse.foldLeft(List[Int]()) {

case (lst, (cnt, ndx)) => List.fill(cnt)(ndx + min) ::: lst

 

=={{header|Sidef}}==

var cnt = ([0] * (max - min + 1))

a.each {|i| cnt[i-min]++ }

 

var a = 100.of { 100.irand }

 

=={{header|Slate}}==

 

[| counts index |

min `defaultsTo: (s reduce: #min: `er).

].

s

 

=={{header|Smalltalk}}==

{{works with|GNU Smalltalk}}

 

countingSortWithMin: min andMax: max [

|oc z|

]

]

 

Testing:

 

 

ages := OrderedCollection new.

 

ages countingSortWithMin: 0 andMax: 140.

 

=={{header|Tcl}}==

{{works with|Tcl|8.5}}

# If either of min or max weren't given, compute them now

if {$min eq ""} {

for {set i 0} {$i < 50} {incr i} {lappend a [expr {1+ int(rand()*10)}]}

puts $a

<pre>9 7 10 2 9 7 4 3 10 2 7 10 2 1 3 8 7 3 9 5 8 5 1 6 3 7 5 4 6 9 9 6 6 10 2 4 5 2 8 2 2 5 2 9 3 3 5 7 8 4

1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 5 5 5 5 5 5 6 6 6 6 7 7 7 7 7 7 8 8 8 8 9 9 9 9 9 9 10 10 10 10

 

=={{header|VBA}}==

Private Function countingSort(array_ As Variant, mina As Long, maxa As Long) As Variant

Dim count() As Integer

s = [{5, 3, 1, 7, 4, 1, 1, 20}]

Debug.Print Join(countingSort(s, WorksheetFunction.Min(s), WorksheetFunction.Max(s)), ", ")

<pre>1, 1, 1, 3, 4, 5, 7, 20</pre>

 

 

=====Implementation=====

dim num

dim max

next

countingSort = a

 

=====Invocation=====

a = array(300, 1, -2, 3, -4, 5, -6, 7, -8, 100, 11 )

wscript.echo join( a, ", " )

countingSort a

 

=====Output=====

 

=={{header|Vlang}}==

println('Input: ' + arr.str())

mut count := [0].repeat(max - min + 1)

mut arr := [6, 2, 1, 7, 6, 8]

counting_sort(mut arr, 1, 8)

{{out}}

<pre>Input: [6, 2, 1, 7, 6, 8]

 

=={{header|Wren}}==

var count = List.filled(max - min + 1, 0)

for (n in a) count[n - min] = count[n - min] + 1

var max = a.reduce { |max, i| (i > max) ? i : max }

countingSort.call(a, min, max)

 

{{out}}

 

=={{header|XPL0}}==

 

proc CountingSort(Array, Min, Max, Size); \Sort Array

CountingSort(A, -5, 9, 10);

for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];

 

{{out}}

 

=={{header|zkl}}==

count:=(max - min + 1).pump(List().write,0); // array of (max - min + 1) zeros

foreach number in (array){

}

array

{{out}}

<pre>L(-31,0,1,2,2,4,65,83,99,182)</pre>