program StrBuckSort;

{ Sortierung von Strings mit Bucketsort. Dies ist eine der eher typischen
 Anwendungen von Bucketsort, mit all seinen Zutaten. Auf Groß- bzw. Klein-
 schreibung wird hier *nicht* geachtet; es wird immer nur mit Kleinbuchstaben
 gearbeitet. }

uses
   Queue;

const
   TableSize = 20;
   StrMax    = 8;

type
   PSortStr = ^TSortStr;
   TSortStr = String[StrMax];
   
var
   Table     : Array[1..TableSize] of TSortStr;
   Bucket    : Array['a'..'z'] of TQueue;
   Index     : LongInt;
   CharIndex : LongInt;
   c	     : Char;

procedure SBuckSort;
var
   Run	   : LongInt;
   Index   : LongInt;
   SortStr : PSortStr;
   c	   : Char;
begin
   for Run := StrMax downto 1 do
   begin
      for Index := 1 to TableSize do
      begin
	 New(SortStr);
	 SortStr^ := Table[Index];
	 Enqueue(Bucket[Table[Index][Run]],SortStr);
      end;
      c := 'a';
      for Index := 1 to TableSize do
      begin
	 while IsEmpty(Bucket[c]) do Inc(c);
	 SortStr := Dequeue(Bucket[c]);
	 Table[Index] := SortStr^;
	 Dispose(SortStr);
      end;
   end;
end;

begin
   Randomize;
   for c := 'a' to 'z' do
      InitQueue(Bucket[c]);
   for Index := 1 to TableSize do
   begin
      for CharIndex := 1 to StrMax do
	 Table[Index] := Table[Index] + Chr(Ord('a') + Random(26));
      Writeln(Table[Index]);
   end;
   Writeln;
   SBuckSort;
   for Index := 1 to TableSize do
      Writeln(Table[Index]);
end.