Sorting algorithms/Counting sort: Difference between revisions

{{task|Sorting Algorithms}}

{{Sorting Algorithm}}

 

'''function''' ''countingSort''(array, min, max):

count: '''array of''' (max - min + 1) '''elements'''

The ''min'' and ''max'' can be computed apart, or be known ''a priori''.

 

 

=={{header|Ada}}==

 

procedure Counting_Sort is

type Data is array (Integer range <>) of Natural;

begin

end loop;

end Sort;

begin

Sort(Stuff);

for I in Stuff'range loop

Put(Natural'Image(Stuff(I)));

end loop;

New_Line;

 

=={{header|ALGOL 68}}==

{{trans|C}}

{{works with|ALGOL 68|Standard - no extensions to language used}}

{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}

{{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:

 

0 1 2 3 3 4 4 5 6 7 8 9 9 10 11 12 15 18 18 19 21 21 22 27 33 35 36 38 38 38 38 39 40 40 41 43 44 53 54 55 57 57 58 59 59 60 60 60 60 61 62 64 65 66 67 68 70 71 78 79 82 83 84 84 87 87 88 88 88 89 89 92 93 93 97 98 99 99 100 107 109 114 115 115 118 122 126 127 127 129 129 130 131 133 134 136 136 137 139 139

=={{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|C}}==

#include <stdlib.h>

 

}

 

{

for(i=1; i < n; i++) {

}

}

 

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;

 

 

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.

 

(let ((i 0)

(counts (make-array (1+ (- max min)) :initial-element 0

(incf i))

(decf (aref counts i))

 

 

Straightforward implementation, no particularly interesting characteristics.

 

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

for elem in array {

}

}

 

# value: [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()

 

? countingSort(arr, 0, 735)

? arr

 

=={{header|Fortran}}==

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

 

implicit none

 

integer :: i, z

 

z = 1

do i = tmin, tmax

end subroutine counting_sort_mm

 

 

Testing:

 

use CountingSort

implicit none

write(*,'(I4)') ages

 

 

=={{header|Haskell}}==

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

 

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

 

=={{header|Java}}==

{{works with|Java|1.5+}}

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

for(int number : array){

}

}

 

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

 

IMPORT IO, Fmt;

END;

IO.Put("\n");

Output:

<pre>

Sorted: 10 20 30 40 50 60 70 80

</pre>

 

=={{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|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|PHP}}==

 

 

{

$count = array();

}

}

 

Testing:

 

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

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

}

 

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

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

}

 

=={{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|R}}==

{{trans|Octave}}

r <- arr

z <- 1

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

sorted <- counting_sort(ages, 0, 140)

 

=={{header|Ruby}}==

end

count = Array.new(max - min + 1, 0)

each {|number| count[number - min] += 1}

end

end

 

ary = [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]

 

=={{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

</pre>