SCAR Code:
program Hoi;
Const
ArrayLength = 9999; //The length of the input array
Negatives = True; //Put in Negative numbers?
Randoms = 9999; // The random?
Radix = 10; //I can't really explain.. Radix 10 is used the most.. It stands for 0,1,2,3,4,5,6,7,8,9.. And if your using negative numbers to, its -9..9
Procedure RadixSort(Integers : TIntegerArray; Digits : Integer; Negative : Boolean);
var
Dump : Array[-Radix + 1..Radix-1] of TIntegerArray; //We store them temporary here
Counts : Array[-Radix + 1..Radix-1] of Integer; //Counts, for the length of the Dump
Len,Divider,I,II,III,Temporary,Counter : Integer;
RadixMax,RadixMin : integer;
begin
Divider := 1; //We use this, to sort all the digits time by time ;).
Len := High(Integers);
if Negative then
RadixMin := -Radix + 1
else
RadixMin := 0;
RadixMax := Radix - 1;
For I := RadixMin to RadixMax do
SetLength(Dump[I],Len + 1);
For I := 1 to Digits do //Digits!
begin;
For II := RadixMin to RadixMax do
Counts[II] := -1; //Reset the counts
For II := 0 to Len do
begin;
Temporary := (Integers[II] div Divider) mod Radix // We get the single digit of the number..
Counts[Temporary] := Counts[Temporary] + 1; //Increase the Counts ;)
Dump[Temporary][Counts[Temporary]] := Integers[II]; //Store the whole number in in its own digit 'dump', 0 to Radix - 1.. E.G. : Dump[0][0] := Integers[II];
end;
Counter := -1;
For II := RadixMin to RadixMax do
For III := 0 to Counts[II] do
begin;
Counter := Counter + 1;
Integers[Counter] := Dump[II][III]; //Place back the orignal var, "Integers"
end;
Divider := Divider * Radix; //So that we go to the next Digit
end;
end;
Procedure MySort(var Integers : TIntegerArray);
var
Counts : Array of Integer;
Min, Max : Integer;
I,II,Len,CountOr : Integer;
begin;
Len := High(integers);
Max := Integers[0];
Min := Integers[0];
For I := 1 to Len do
begin;
if Integers[I] < Min then
Min := Integers[I]
else if Integers[I] > max then
Max := Integers[I];
end;
CountOr := 0;
if Min < 0 then
begin;
Min := -Min;
Max := Min + Max;
SetLength(Counts, Max + 1);
For I := 0 to Len do
Inc(Counts[Integers[I] + Min]);
For I := 0 to Max do
For II := 1 to Counts[I] do
begin;
Integers[CountOr] := I - Min;
CountOr := CountOr + 1;
end;
end else
begin;
SetLength(Counts,Max +1 );
For I := 0 To Len do
Inc(Counts[INtegers[I]])
For I := Min to Max do
For II := 1 to Counts[I] do
begin;
Integers[CountOr] := I;
CountOr := CountOr + 1;
end;
end;
end;
procedure QuickSort(var arr: TIntegerArray; s, e: integer);
var
cs, ce: Integer;
pivot, swap: INteger;
begin
cs:= s;
ce:= e;
pivot:= arr[(s + e) div 2];
repeat
while arr[cs] < pivot do cs:= cs + 1;
while arr[ce] > pivot do ce:= ce - 1;
if cs <= ce then
begin
swap:= arr[cs];
arr[cs]:= arr[ce];
arr[ce]:= swap;
cs:= cs + 1;
ce:= ce - 1;
end;
until cs > ce;
if ce > s then QuickSort(arr, s, ce);
if cs < e then QuickSort(arr, cs, e);
end;
Function GetDigits( Num : Integer):Integer;
begin;
if Num = 0 then Result := 1;
Num := iAbs(Num);
While Num > 0 do
begin;
Result := Result + 1;
Num := Num div 10;
end;
end;
Function GetDigitsArray ( Ints : TIntegerArray) : Integer;
var
C,I : Integer;
Len : Integer;
begin;
Len := High(Ints);
if Len < 0 then Exit;
C := 1;
For I := 0 to Len do
if (Ints[I] >= C) or (Ints[I] <= -C) then
begin;
C := C * 10;
Dec(I);
end;
Result := GetDigits(C - 1);
end;
var
Ints,SortInts : TIntegerArray;
I,Len : integer;
J : Integer;
Time : Integer;
begin
{ Writeln(inttostr(GetDigits(100)));
Writeln(inttostr(GetDigitsArray([15,0,10,-99]))); }
// exit;
SetLength(Ints, ArrayLength);
Len := High(ints);
SetLength(SortInts,Len+ 1);
if Negatives then
For I := 0 to Len do
Ints[I] := Random(Randoms) - Random(Randoms)
else
For I := 0 to Len do
Ints[I] := Random(Randoms);
For I:= 0 to Len do
SortInts[i] := Ints[I];
Time := GetSystemTime;
MySort(SortInts);
Time := GetSystemTime - Time;
{ For I := 0 to high(SortInts) do
Writeln(inttostr(SortInts[I])); }
Writeln(IntToStr(Time) + ' msec - Count sort!');
For I:= 0 to Len do
SortInts[i] := Ints[I];
J := GetDigitsArray(SortInts);
Time := GetSystemTime;
RadixSort(SortInts,J, Negatives);
Time := GetSystemTime - Time;
Writeln(IntToStr(Time) + ' msec - Radix sort!');
For I:= 0 to Len do
SortInts[i] := Ints[I];
Time := GetSystemTime;
QuickSort(SortInts,0,Len);
Time := GetSystemTime - Time;
Writeln(IntToStr(Time) + ' msec - Quick sort!');
end.