How to resolve the algorithm Sorting algorithms/Counting sort step by step in the ALGOL 68 programming language

Published on 12 May 2024 09:40 PM
#Algol 68

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

Source code in the algol programming language

PROC counting sort mm = (REF[]INT array, INT min, max)VOID:
(
  INT z := LWB array - 1;
  [min:max]INT count;

  FOR i FROM LWB count TO UPB count DO count[i] := 0 OD;
  FOR i TO UPB array DO count[ array[i] ]+:=1 OD;

  FOR i FROM LWB count TO UPB count DO
    FOR j TO count[i] DO array[z+:=1] := i OD
  OD
);

PROC counting sort = (REF[]INT array)VOID:
(
  INT min, max;
  min := max := array[LWB array];

  FOR i FROM LWB array + 1 TO UPB array DO
    IF array[i] < min THEN
      min := array[i]
    ELIF array[i] > max THEN
      max := array[i]
    FI
  OD
);

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

INT n = 100;
INT min age = 0, max age = 140;
main:
(
  [n]INT ages;

  FOR i TO UPB ages DO ages[i] := ENTIER (random * ( max age + 1 ) ) OD;
  counting sort mm(ages, min age, max age);
  FOR i TO UPB ages DO print((" ", whole(ages[i],0))) OD;
  print(new line)
)

You may also check:How to resolve the algorithm Horner's rule for polynomial evaluation step by step in the Logo programming language
You may also check:How to resolve the algorithm Fibonacci sequence step by step in the Java programming language
You may also check:How to resolve the algorithm Random number generator (included) step by step in the Z80 Assembly programming language
You may also check:How to resolve the algorithm Add a variable to a class instance at runtime step by step in the Morfa programming language
You may also check:How to resolve the algorithm Keyboard input/Flush the keyboard buffer step by step in the Oforth programming language