How to resolve the algorithm Sorting algorithms/Counting sort step by step in the Icon and Unicon programming language

Published on 12 May 2024 09:40 PM
#Icon and unicon

How to resolve the algorithm Sorting algorithms/Counting sort step by step in the Icon and Unicon 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 Icon and Unicon programming language

Source code in the icon programming language

procedure main()                                         #: demonstrate various ways to sort a list and string 
   write("Sorting Demo using ",image(countingsort))                
   writes("  on list : ")
   writex(UL)
   displaysort(countingsort,copy(UL))           
end

procedure countingsort(X)                                #: return sorted list (integers only)
local T,lower,upper

   T := table(0)                                         # hash table as sparse array
   lower := upper := X[1]

   every x := !X do {
      if not ( integer(x) = x ) then runerr(x,101)       # must be integer
      lower >:= x                                        # minimum
      upper <:= x                                        # maximum
      T[x] +:= 1                                         # record x's and duplicates
      }

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

You may also check:How to resolve the algorithm Ranking methods step by step in the Visual FoxPro programming language
You may also check:How to resolve the algorithm Numerical integration/Gauss-Legendre Quadrature step by step in the Python programming language
You may also check:How to resolve the algorithm Repeat a string step by step in the Harbour programming language
You may also check:How to resolve the algorithm Hash from two arrays step by step in the C# programming language
You may also check:How to resolve the algorithm Leonardo numbers step by step in the F# programming language