How to resolve the algorithm Sorting algorithms/Counting sort step by step in the Action! programming language

Published on 12 May 2024 09:40 PM
#Action!

How to resolve the algorithm Sorting algorithms/Counting sort step by step in the Action! programming language

Table of Contents

Problem Statement

Implement the Counting sort.   This is a way of sorting integers when the minimum and maximum value are known.

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

Note:   we know that, given an array of integers,   its maximum and minimum values can be always found;   but if we imagine the worst case for an array that can hold up to 32 bit integers,   we see that in order to hold the counts,   an array of up to 232 elements may be needed.   I.E.:   we need to hold a count value up to 232-1,   which is a little over 4.2 Gbytes.   So the counting sort is more practical when the range is (very) limited,   and minimum and maximum values are known   a priori.     (However, as a counterexample,   the use of   sparse arrays   minimizes the impact of the memory usage,   as well as removing the need of having to know the minimum and maximum values   a priori.)

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Counting sort step by step in the Action! programming language

Source code in the action! programming language

DEFINE MAXSIZE="100"

PROC PrintArray(INT ARRAY a INT size)
  INT i

  Put('[)
  FOR i=0 TO size-1
  DO
    IF i>0 THEN Put(' ) FI
    PrintI(a(i))
  OD
  Put(']) PutE()
RETURN

PROC CountingSort(INT ARRAY a INT size,min,max)
  INT ARRAY count(MAXSIZE)
  INT n,i,num,z

  n=max-min+1
  FOR i=0 TO n-1
  DO count(i)=0 OD

  FOR i=0 TO size-1
  DO
    num=a(i)
    count(num-min)==+1
  OD

  z=0
  FOR i=min TO max
  DO
    WHILE count(i-min)>0
    DO
      a(z)=i
      z==+1
      count(i-min)==-1
    OD
  OD
RETURN

PROC Test(INT ARRAY a INT size,min,max)
  PrintE("Array before sort:")
  PrintArray(a,size)
  CountingSort(a,size,min,max)
  PrintE("Array after sort:")
  PrintArray(a,size)
  PutE()
RETURN

PROC Main()
  INT ARRAY
    a(10)=[1 4 65535 0 3 7 4 8 20 65530],
    b(21)=[10 9 8 7 6 5 4 3 2 1 0
      65535 65534 65533 65532 65531
      65530 65529 65528 65527 65526],
    c(8)=[101 102 103 104 105 106 107 108],
    d(12)=[1 65535 1 65535 1 65535 1
      65535 1 65535 1 65535]
  
  Test(a,10,-6,20)
  Test(b,21,-10,10)
  Test(c,8,101,108)
  Test(d,12,-1,1)
RETURN

You may also check:How to resolve the algorithm Currency step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Find if a point is within a triangle step by step in the J programming language
You may also check:How to resolve the algorithm State name puzzle step by step in the zkl programming language
You may also check:How to resolve the algorithm Voronoi diagram step by step in the Scala programming language
You may also check:How to resolve the algorithm Associative array/Creation step by step in the Lua programming language