our $i;
our $tmp;
our $Max;
our ($List,$Test)=maketest(1000);
our %Hash=map {$_,1} @$List;
#######################
# Test Code For qssqrt
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program Q With swap  code added
	# Tail Sentinal if NOT being deleted ($array[$Max])

	$i=0;
	$array[$Max]=$value;

	$i++ while($value ne $array[$i]);

	if ($i<$Max) {
		if ($i>0) {
			$ret=int(sqrt($i));
			$tmp=$array[$ret];
			$array[$ret]=$array[$i];
			$array[$i]=$tmp;

		} else {
			$ret=$i;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For qsrand
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program Q With swap  code added
	# Tail Sentinal if NOT being deleted ($array[$Max])

	$i=0;
	$array[$Max]=$value;

	$i++ while($value ne $array[$i]);

	if ($i<$Max) {
		if ($i>0) {
			$ret=int(rand($i));
			$tmp=$array[$ret];
			$array[$ret]=$array[$i];
			$array[$i]=$tmp;
		} else {
			$ret=$i;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For quick
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program Q
	# Tail Sentinal if NOT being deleted ($array[$Max])

	$i=0;
	$array[$Max]=$value;
	$i++ while($value ne $array[$i]);
	$ret=$i if $i<$Max;
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For wbump
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program S. With swap (bump) code added
	# While implementation

	$i=0;
	$i++ while($value ne $array[$i] && $i<$Max);

	if ($i<$Max) {
		if ($i>0) {
			$tmp=$array[0];
			$array[0]=$array[$i];
			$array[$i]=$tmp;
		}
		$ret=0;
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For qbump
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program Q With swap (bump) code added
	# Tail Sentinal if NOT being deleted ($array[$Max])

	$array[$Max]=$value;
	my $i=0;
	$i++ while($value ne $array[$i]);

	if ($i<$Max) {
		if ($i>0) {
			$tmp=$array[0];
			$array[0]=$array[$i];
			$array[$i]=$tmp;
		}
		$ret=0;
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For wswap
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program S. With swap code added
	# While implementation

	$i=0;
	$i++ while($value ne $array[$i] && $i<$Max);

	if ($i<$Max) {
		if ($i>0) {
			$ret=$i-1;
			$tmp=$array[$ret];
			$array[$ret]=$array[$i];
			$array[$i]=$tmp;

		} else {
			$ret=$i;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For foreach
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
        # from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program S
	# Foreach implementation

	LOOP: foreach (@array) {
		if ($value eq $_) {
			$ret=$value;
			last LOOP;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For qs i-1
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program Q With swap  code added
	# Tail Sentinal if NOT being deleted ($array[$Max])

	$i=0;
	$array[$Max]=$value;

	$i++ while($value ne $array[$i]);

	if ($i<$Max) {
		if ($i>0) {
			$ret=$i-1;
			$tmp=$array[$ret];
			$array[$ret]=$array[$i];
			$array[$i]=$tmp;

		} else {
			$ret=$i;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For while
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program S
	# While implementation

	$i=0;
	LOOP:while($i<$Max) {
		if ($value eq $array[$i]) {
			$ret=$i;
			last LOOP;
		} else {
			$i++;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For Hash
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
        # Simple perl hash Implementation

	$ret=$value if exists($Hash{$value});
	
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For for(;;)
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program S
	# For (;;) implementation

	LOOP: for ($i=0;$i<$Max;$i++) {
		if ($value eq $array[$i]) {
			$ret=$i;
			last LOOP;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For forI
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program S
	# For (0..n) implementation

	LOOP: for $i (0..$Max-1) {
		if ($value eq $array[$i]) {
			$ret=$i;
			last LOOP;
		}
	}
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;
}}


#######################
# Test Code For qs i/2
#######################
{
my @array=@$List;
my @search=@{$Test->[$cur_test]};
$Max=@array;
#print "\@array=@array\n";
#print "\@search=@search\n";
foreach my $value (@search) {
	my $ret="";
	# from Knuth Art of Computer Programming Vol 3
	# Section 6.1 Program Q With swap  code added
        # Tail Sentinal if NOT being deleted ($array[$Max])

	$i=0;
	$array[$Max]=$value;

	$i++ while($value ne $array[$i]);

	if ($i<$Max) {
		if ($i>0) {
			$ret=int($i/2);
			$tmp=$array[$ret];
			$array[$ret]=$array[$i];
			$array[$i]=$tmp;

		} else {
			$ret=$i;
		}
	}        
#print "return for $value=$ret | ".((defined($ret))? $array[$ret] : "")."\n" ;                    
}}                                   
                                     
                               
                                     
----------------                     
Testing 0 gaussian(($i-($total_elems/2))/10,0,.5)*100,
          Rate  while for(;;)  wbump  wswap   forI  qbump  quick
while   1.07/s     --     -3%   -29%   -34%   -49%   -53%   -55%
for(;;) 1.11/s     3%      --   -27%   -32%   -47%   -52%   -53%
wbump   1.51/s    41%     36%     --    -7%   -28%   -34%   -36%
wswap   1.62/s    51%     47%     8%     --   -22%   -29%   -31%
forI    2.08/s    94%     88%    38%    28%     --    -9%   -12%
qbump   2.28/s   113%    106%    51%    41%    10%     --    -3%
quick   2.36/s   120%    113%    56%    45%    13%     3%     --
qs i-1  2.50/s   133%    126%    66%    54%    20%    10%     6%
foreach 2.67/s   149%    141%    77%    64%    28%    17%    13%
qssqrt  5.08/s   374%    359%   237%   213%   144%   123%   115%
qs i/2  15.3/s  1328%   1285%   915%   843%   635%   571%   549%
qsrand  16.3/s  1419%   1373%   980%   903%   682%   614%   590%
Hash     261/s 24295%  23550% 17244% 16010% 12454% 11363% 10983%

----------------
Testing 1 exponential(($i+1)/$total_elems*20,1)*100,
          Rate  while for(;;)  wbump  wswap   forI  qbump  quick
while   1.07/s     --     -2%   -31%   -32%   -48%   -55%   -55%
for(;;) 1.09/s     2%      --   -30%   -31%   -47%   -54%   -54%
wbump   1.55/s    45%     42%     --    -1%   -25%   -34%   -35%
wswap   1.57/s    47%     44%     1%     --   -24%   -33%   -34%
forI    2.07/s    93%     90%    33%    31%     --   -12%   -13%
qbump   2.36/s   120%    116%    52%    50%    14%     --    -1%
quick   2.39/s   123%    119%    54%    52%    15%     1%     --
qs i-1  2.40/s   124%    120%    55%    53%    16%     2%     1%
foreach 2.64/s   146%    143%    70%    68%    28%    12%    11%
qssqrt  3.06/s   185%    180%    97%    94%    48%    30%    28%
qsrand  5.59/s   421%    413%   260%   255%   170%   137%   134%
qs i/2  5.79/s   440%    432%   273%   268%   180%   146%   143%
Hash     255/s 23634%  23261% 16295% 16071% 12197% 10693% 10555%

----------------
Testing 2 (1/($i+1)*$total_elems)**2,
          Rate  while for(;;)   forI  quick wbump foreach wswap 
while   1.12/s     --     -3%   -48%   -55%  -57%    -58%  -60% 
for(;;) 1.15/s     3%      --   -46%   -54%  -56%    -57%  -58% 
forI    2.15/s    92%     87%     --   -14%  -17%    -19%  -22% 
quick   2.51/s   124%    118%    17%     --   -3%     -5%   -9% 
wbump   2.59/s   131%    125%    21%     3%    --     -3%   -7% 
foreach 2.66/s   137%    131%    24%     6%    3%      --   -4% 
wswap   2.77/s   147%    141%    29%    10%    7%      4%    -- 
qbump   3.73/s   233%    224%    74%    48%   44%     40%   35% 
qs i-1  4.18/s   274%    263%    95%    67%   62%     57%   51% 
qssqrt  18.2/s  1530%   1484%   749%   626%  604%    586%  559% 
qsrand  29.6/s  2542%   2468%  1276%  1077% 1042%   1013%  968% 
qs i/2  30.9/s  2658%   2581%  1337%  1129% 1092%   1062% 1015% 
Hash     260/s 23127%  22475% 12001% 10249% 9939%   9683% 9286% 

----------------
Testing 3 (($i-$total_elems)/$total_elems+1)**2
          Rate  while for(;;)  wswap  wbump   forI qssqrt qs i/2
while   1.05/s     --     -3%   -32%   -32%   -48%   -55%   -55%
for(;;) 1.09/s     3%      --   -29%   -29%   -47%   -53%   -53%
wswap   1.53/s    46%     41%     --     0%   -25%   -34%   -34%
wbump   1.53/s    46%     41%     0%     --   -25%   -34%   -34%
forI    2.04/s    94%     88%    33%    33%     --   -12%   -12%
qssqrt  2.32/s   120%    114%    51%    51%    14%     --    -0%
qs i/2  2.32/s   121%    114%    51%    51%    14%     0%     --
qs i-1  2.33/s   122%    115%    52%    52%    14%     0%     0%
qbump   2.35/s   123%    116%    53%    53%    15%     1%     1%
qsrand  2.37/s   125%    118%    54%    54%    16%     2%     2%
quick   2.38/s   126%    119%    55%    55%    17%     2%     2%
foreach 2.61/s   148%    140%    70%    70%    28%    13%    12%
Hash     242/s 22951%  22224% 15687% 15687% 11801% 10354% 10324%

----------------
Testing 4 rand($total_elems)
          Rate  while for(;;)  wbump  wswap   forI qsrand qs i/2
while   1.02/s     --     -3%   -30%   -32%   -48%   -51%   -52%
for(;;) 1.06/s     3%      --   -28%   -30%   -47%   -49%   -50%
wbump   1.47/s    44%     40%     --    -2%   -26%   -29%   -30%
wswap   1.50/s    46%     42%     2%     --   -25%   -28%   -29%
forI    1.99/s    94%     88%    35%    33%     --    -4%    -6%
qsrand  2.07/s   102%     96%    41%    38%     4%     --    -2%
qs i/2  2.12/s   107%    101%    44%    41%     7%     2%     --
qssqrt  2.25/s   120%    113%    53%    50%    13%     9%     6%
qbump   2.26/s   120%    114%    53%    51%    14%     9%     6%
qs i-1  2.29/s   124%    117%    55%    53%    15%    11%     8%
quick   2.31/s   126%    119%    57%    54%    16%    12%     9%
foreach 2.55/s   149%    142%    73%    70%    28%    23%    20%
Hash     245/s 23796%  23083% 16509% 16223% 12210% 11717% 11447%