Countingsort in PASCAL




PROGRAM Counting;
CONST max  = 100;
      kmax = 26;
TYPE  Feld = ARRAY[1..max] OF INTEGER;
VAR  A,B : Feld;
     n,i,k : INTEGER;


PROCEDURE Countingsort (VAR A,B : Feld; n,k : INTEGER);
(* Sortiert das Feld A der Laenge n, wobei die Element von A    *)
(* aus {1, ..., k} sind. Das Ergebnis wird in B zurueckgegeben. *)

VAR  C	 : ARRAY[1..kmax] OF INTEGER;
     i,j : INTEGER;

BEGIN
   (* Initialisiere Zaehler C mit 0 *)
   FOR i := 1 TO k DO C[i] := 0;

   (* Zaehle in C[i] die Vorkommen von i = A[j] *) 
   FOR j := 1 TO n DO C[A[j]] := C[A[j]] + 1;

   FOR i := 2 TO k DO C[i] := C[i] + C[i-1];
   (* C[i] enthaelt jetzt die Anzahl der Elemente kleiner oder gleich i in A *)

   FOR j := n DOWNTO 1 DO
   BEGIN
      B[C[A[j]]] := A[j];   (* i = A[j] ist das C[i]-kleinste Elemente in A *)
                            (* und kommt deshalb auf Platz C[i] in B.       *)
      C[A[j]] := C[A[j]] -1 (* Falls i in A mehrfach vorkommt, kommt das    *)
                            (* naechste i auf Platz C[i]-1 in B.            *)
   END
END; { Countingsort }
	

BEGIN (* Hauptprogramm *)
   n:=10;
   k := 10;
   (* Erzeuge Zahlenfolge A *)
   randomize;
   FOR i:=1 TO n DO
   BEGIN
      A[i] := random(k)+1;
      write(A[i],' ')
   END;
   writeln;

   Countingsort(A,B,n,k);

   FOR i:=1 TO n DO write(B[i],' ');
END.