There is a simple Test_Sort test function at the bottom. It uses a very simple random number generator to populate an array and then sort it (twice).
At the very bottom we have the result of running the program.
interface Sorting<Array_Type is Indexable<Comparable<>, Countable<>>> is
func Quicksort(var A : Array_Type);
// Sort Arr according to the sorting op "<" which returns
// True if Left must appear before Right in the sorted order.
// Before returns False if Left = Right.
end interface Sorting;
class Sorting is
exports
func Quicksort(var A : Array_Type) is
// Handle short arrays directly. Partition longer arrays.
for Arr : Slice<Array_Type> => A[..] while Length(Arr) > 1 loop
if Length(Arr) == 2 then
if Arr[Arr.Last] < Arr[Arr.First] then
// Swap elements
Arr[Arr.First] <=> Arr[Arr.Last];
end if;
else
// Partition array
const Mid := Arr[Arr.First + Length(Arr)/2];
var Left := Arr.First;
var Right := Arr.Last;
until Left > Right loop
var New_Left := Right+1;
var New_Right := Left-1;
block
// Find item in left half to swap
for I in Left .. Right forward loop
if not (Arr[I] < Mid) then
// Found an item that can go into right partitition
New_Left := I;
if Mid < Arr[I] then
// Found an item that *must* go into right part
exit loop;
end if;
end if;
end loop;
||
// Find item in right half to swap
for J in Left .. Right reverse loop
if not (Mid < Arr[J]) then
// Found an item that can go into left partitition
New_Right := J;
if Arr[J] < Mid then
// Found an item that *must* go into left part
exit loop;
end if;
end if;
end loop;
end block;
if New_Left > New_Right then
// Nothing more to swap
// Exit loop and recurse on two partitions
Left := New_Left;
Right := New_Right;
exit loop;
end if;
// Swap items
Arr[New_Left] <=> Arr[New_Right];
// continue looking for items to swap
Left := New_Left + 1;
Right := New_Right - 1;
end loop;
// At this point, "Right" is right end of left partition
// and "Left" is left end of right partition
// and the partitions don't overlap
// and neither is the whole array
// and everything in the left partition can precede Mid
// and everything in the right partition can follow Mid
// and everything between the partitions is equal to Mid.
{Left > Right;
Right < Arr.Last;
Left > Arr.First;
(for all I in Arr.First .. Right => not (Mid < Arr[I]));
(for all J in Left .. Arr.Last => not (Arr[J] < Mid));
(for all K in Right+1 .. Left-1 =>
not (Mid < Arr[K]) and not (Arr[K] < Mid))}
then
// continue with two halves in parallel
continue loop with Arr[Arr.First .. Right];
||
continue loop with Arr[Left .. Arr.Last];
end if;
end loop;
end func Quicksort;
end class Sorting;
func Random(var Seed : Univ_Integer; Mult, Mod : Univ_Integer)
-> Univ_Integer is
Seed := Seed * Mult mod Mod;
return Seed;
end func Random;
func Test_Sort(Len : Univ_Integer) is
// For Random
const Mult := 7**5;
const Mod := 2**31 - 1;
var Seed := Len;
Println("Seed = " | Seed | ", Mult = " | Mult | ", Mod = " | Mod);
type My_Sorter is Sorting<Vector<Univ_Integer>>;
var Vec : Vector<Univ_Integer> := [];
for I in 1..Len loop
Vec |= Random(Seed, Mult, Mod) mod 100;
end loop;
var Vec2 := Vec;
Println("Before sort, Vec = ");
for I in 1 .. Length(Vec) forward loop
Print(" " | Vec[I]);
if I < Length(Vec) then
Print(",");
end if;
end loop;
Print("\n");
My_Sorter::Quicksort(Vec);
Println("After sort, Vec = ");
for I in 1 .. Length(Vec) forward loop
Print(" " | Vec[I]);
if I < Length(Vec) then
Print(",");
end if;
end loop;
Print("\n");
My_Sorter::Quicksort(Vec2);
Println("After 2nd sort, Vec2 = ");
for I in 1 .. Length(Vec2) forward loop
Print(" " | Vec2[I]);
if I < Length(Vec2) then
Print(",");
end if;
end loop;
Print("\n");
end func Test_Sort;
Here is the result of compiling and running the program. "aaa.psi" contains the standard ParaSail library of modules. "qsort6.psl" is given above. We are using the compiler interactively here, so we can run stand-alone ParaSail operations. It also can run non-interactively, by giving "-command <operation> <param1> ..." after the list of source file names on the command line. When in interactive mode, it dumps out some virtual machine threading statistics after the user "quit"s. These are at the very bottom. In this example, we have 21 threads active simultaneously at one point during execution.% pslc aaa.psi qsort6.psl Parsing aaa.psi Parsing qsort6.psl ---- Beginning semantic analysis ---- 52 trees in library. Done with First pass. Done with Second pass. Done with Pre codegen pass. Done with Code gen. Command to execute: Test_Sort 20 Seed = 20, Mult = 16807, Mod = 2147483647 Before sort, Vec = 40, 86, 55, 37, 30, 52, 80, 49, 49, 34, 71, 30, 88, 40, 93, 90, 29, 80, 71, 93 After sort, Vec = 29, 30, 30, 34, 37, 40, 40, 49, 49, 52, 55, 71, 71, 80, 80, 86, 88, 90, 93, 93 After 2nd sort, Vec2 = 29, 30, 30, 34, 37, 40, 40, 49, 49, 52, 55, 71, 71, 80, 80, 86, 88, 90, 93, 93 Command to execute: quit Threading Statistics: Num_Initial_Thread_Servers : 10 Num_Dynamically_Allocated_Thread_Servers : 0 Max_Waiting_Threads (for server task): 6 Max_Active : 21 Max_Active_Masters : 17 Max_Sub_Threads_Per_Master : 6 Max_Waiting_For_Threads (to finish): 113
No comments:
Post a Comment