#!/usr/bin/perl #-w
#Damian Knopp 
#Data Structures 336
#sort project
#A file of numeric data is sorted using Shell sort,Insertion sort, Merge sort
#Quick sort, and Heap sort algorithms. Thye program also reports the CPU time
#,the number of comparisons,and number of data assignments made by the algortim
##########################################################################
use Benchmark;

@array=();
open(TD,"proj4.dat") || die "Can not open file : $!\n"; 
@array = <TD>;
@array1=@array;
@array2=@array;
@array3=@array;
@array4=@array;

my $shellstart=new Benchmark;
shellsort(\@array);
my $shellend=new Benchmark;
my $shelldiff= timediff($shellend,$shellstart);
print "It took shellsort ",timestr($shelldiff), "\n";


my $mstart= new Benchmark;
mergesort(\@array1);
my $mend=new Benchmark;
my $mdiff= timediff($mend,$mstart);
print "mergesort: " ,scalar @array1,
        " elements ,$mcomp comparisons, $mswap swaps\n";
print "It took mergesort ",timestr($mdiff), "\n";

my $hstart= new Benchmark;
heapsort(\@array2);
my $hend= new Benchmark;
print "heapsort: ", scalar @array2,
         " elements, $hcomp comparisons, $hswap swaps\n";
my $hdiff = timediff($hend,$hstart);
print "It took heapsort ",timestr($hdiff), "\n";


my $istart= new Benchmark;
insertion_sort(\@array3);
my $iend= new Benchmark;
my $idiff= timediff($iend,$istart);
print "It took insertion sort ",timestr($idiff), "\n";

my $qstart=new Benchmark;
quicksort(\@array4);
my $qend= new Benchmark;
print "quicksort ", scalar @array4,
       " elements,$qcomp comparisons, $qswap swaps\n";
my $qdiff= timediff($iend,$istart);
print "It took quicksort ",timestr($qdiff), "\n";

#print"quicksort:\n";
#print"@array4\n";

###########################
sub insertion_sort {
my  $array = shift;
my  $i=0;
my  $j=0;
my $nswap=0;
my $ncomp=0;

for ($i =0; $i < $#$array && ++$ncomp; $i++){
   my $m = $i;            #the final index for the minimum element
   my $x = $array->[ $m ];#the mini value
   
   for ( $j = $i + 1; $j < @$array && ++$ncomp; $j++){
       ( $m, $x ) = ($j, $array->[$j] ) #Update minimum
          if $array->[$j] < $x;   
   }

   splice @$array, $i, 0, splice @$array, $m, 1 if $m > $i;
   $nswap++;
   }

print "insertion sort: ", scalar @$array,
       " elements, $ncomp comparisons, $nswap swaps\n";
}
#######################
sub shellsort{
my $array = shift;
my $i;
my $j;
my $shell;
my $ncomp = 0;
my $nswap = 0;

for($shell=1; $shell < @$array; $shell=2*$shell+1) {
}
do {
    $shell = int( ($shell - 1) / 2);
    for($i = $shell; $i < @$array;$i++){
       for($j = $i - $shell;
           $j >= 0 && ++$ncomp &&
              $array->[$j] > $array->[$j + $shell ];
             $j -= $shell ){
             @$array[ $j, $j + $shell ] = @$array[$j+ $shell, $j];
             $nswap++;
          }
     }
 } while $shell > 1;
 print "shellsort:  ",scalar @$array,
        " elements, $ncomp comparisons, $nswap swaps\n";
}

#########################
sub mergesort {
   mergesort_recurse ($_[0], 0, $#{ $_[0] });
}
#########################
sub mergesort_recurse {
my ( $array,$first,$last )= @_;
my $mswap;
my $mcomp;

if( $last > $first) {
 local $^W=0;
 my $middle = int(($last + $first) / 2);

 mergesort_recurse($array,$first,      $middle);
 mergesort_recurse($array,$middle + 1, $last);
 merge($array,$first,$middle,$last);
 }
#print "mergesort: ", scalar @$array,
       # " $nswap swaps, and $ncomp comparisons\n";

}
my @work;	
##########################
sub merge{
my ($array,$first,$middle,$last)=@_;
my $n=$last-$first+1;
my $nswap;
my $ncomp;
#Initilize work with relevent elements in the array

for (my $i= $first,my $j=0; $i<= $last;){
    $work[$j++]=$array->[$i++];
    $mswap++;    
     }
#Now do the actual merge.
#
#
#
$middle = int(($first + $last) / 2) if $middle > $last;
my $n1 = $middle - $first + 1;
for (my $i=$first,my $j =0, my $k= $n1; $i <= $last && $mcomp++; $i++){
    $array->[$i] =
        $j < $n1 &&
         ($k == $n || $work[$j] < $work[$k] ) ?
           $work[$j++]:
           $work[$k++];
      $mswap++;
      }

}
#sub heapify;
#######################
sub heapsort {
my $array = shift;

foreach (my $index = 1+ @$array / 2;$index--;){
    heapify ($array,$index);
}
foreach (my $last = @$array; --$last;){
    @{ $array }[0,$last]=@{ $array }[$last,0];
    heapify ($array,0,$last);
    }
}
##########################
sub heapify{
my ($array,$index,$last)=@_;
$last = @$array unless defined $last;
my $swap = $index;
my $high = $index * 2 + 1;

foreach (my $try = $index * 2;
            $try < $last && $try <= $high && $hcomp++;
            $try++){
       $swap = $try if $array->[$try] > $array->[$swap]; 
       }
  unless ($swap == $index){
        #The heap is in disorder,reshuffle
        @{ $array }[$swap,$index] =@{ $array }[$index,$swap];
        $hswap++;
        heapify ($array, $swap, $last);
        }

}
###########################
sub quicksort_iterate{
my ($array,$first,$last)=@_;
my @stack = ($first,$last);

do {
   if ($last > $first){
       my ($last_of_first,$first_of_last)=
               partition ($array,$first,$last);
          #Larger first
       if($first_of_last - $first > $last-$last_of_first){
           push (@stack,$first,$first_of_last);
           $first = $last_of_first;
        } else {
           push (@stack,$last_of_first,$last);
           $last = $first_of_last;
        }
  } else {
        ($first,$last)=splice @stack,-2,2;
  }
} while @stack;
}
#############################
sub  quicksort{
 quicksort_iterate ($_[0],0,$#{ $_[0] });
}
#############################
sub partition {
my ($array,$first,$last)= @_;
my $i=$first;
my $j=$last-1;
my $pivot = $array->[$last];

SCAN: {
     do {
        #first <=$i <= $j <= $last-1;
        #point 1
        #move $i as far as possialbe
        while ($array->[$i] < $pivot && $qcomp++){
           $i++;
           last SCAN if $j < $i;
        }
        #Move $j as far as possiable  
        while ($array->[$j] > $pivot && $qcomp){
             $j--;
         last SCAN if $j < $i;
         }
        #$i and $j did not cross over, so swap a low and a high value.
        @$array[$j,$i]=@$array[$i,$j];
        $qswap++;
        } while (--$j >= ++$i && $qcomp);
     }
     #$first - 1 <= $j < $i <= $last
     #point 2
     #swap the pivot wwith the first larger element (if there is one).
     if ($i < $last && $qcomp) {
           $qswap++; 
           @$array[$last,$i]=@$array[$i,$last];
           ++$i;
      } 
        #point 3
       return ($i,$j);
}
