type sort.ada

with TEXT_IO;
package INTEGER_IO is new TEXT_IO.INTEGER_IO(INTEGER);

with TEXT_IO, INTEGER_IO;
use  TEXT_IO, INTEGER_IO;
 
with Random;
use Random;
 
procedure Sort is
  ListSize : INTEGER;
 
  function GetLSize return INTEGER is
  Size : INTEGER;
  begin
    NEW_LINE(2);
    PUT("Enter the size of list to sort: ");
    GET(Size); NEW_LINE;
    return Size;
  end GetLSize;
 
  procedure DoSorts(LSize : in INTEGER) is
  type LArray is array (INTEGER range 1..LSize) of INTEGER;
  Unsorted, List : LArray; 
  Comps, Swaps : INTEGER := 0;
    
    procedure InitList(List : in out LArray; Size : in INTEGER) is
    T : INTEGER;
    begin
      InitRandom;
      for T in 1..Size loop
        List(T) := RangeRand(50000);
      end loop;
    end InitList;

    procedure CopyList(L1, L2 : in out LArray; Size : in INTEGER) is
    T : INTEGER;
    begin
      for T in 1..Size loop
        L2(T) := L1(T);
      end loop;
    end CopyList;

    procedure Switch(X1, X2, Count : in out INTEGER) is
    Temp : INTEGER;
    begin
      Temp := X1;
      X1 := X2;
      X2 := Temp;
      Count := Count + 1;
    end switch;

    procedure PrintList(List : in LArray; Size : in INTEGER) is
    T : INTEGER;
    begin
      for T in 1..Size loop
        PUT(List(T)); NEW_LINE;
      end loop;
    end PrintList;

    procedure InSort(List : in out LArray; Size : in INTEGER; 
  		     Comp, Swap : in out INTEGER) is
    T1, T2, Temp : INTEGER;
    Done : BOOLEAN;
    begin
      for T1 in 1..Size loop
        T2 := T1;
        Done := FALSE;
        while (T2>=2) and (not Done) loop
 	  if (List(T2)<List(T2-1)) then
	    Switch(List(T2), List(T2-1), Swap);
            T2 := T2 - 1;
 	  else
	    Done := TRUE;
	  end if;
	  Comp := Comp + 1;
	end loop;
      end loop;
    end InSort;

    procedure Quick1(List : in out LArray; Low, High : in INTEGER; 
		     Comp, Swap : in out INTEGER) is
    Pivot, Lo, Hi : INTEGER;

      procedure Part(List : in out LArray; Low, High : in INTEGER;
		     Pivot : out INTEGER; C, S : in out INTEGER) is
      PivotVal, Lo, Hi : INTEGER;
      begin
        Lo := Low; Hi := High;
	PivotVal := List(Lo);
        while (Lo<Hi) loop
  	  while (PivotVal<List(Hi)) and (Lo<Hi) loop
	    Hi:=Hi-1;  C := C + 1;
	  end loop;
	  if (Hi/=Lo) then
	    List(Lo) := List(Hi);  S := S + 1;
            Lo := Lo + 1;
	  end if;
	    
	  while (List(Lo)<PivotVal) and (Lo<Hi) loop
	    Lo := Lo + 1; C := C + 1;
	  end loop;
          if (Hi/=Lo) then
	    List(Hi) := List(Lo); S := S + 1;
            Hi := Hi - 1;
	  end if;
	end loop; 
	List(Hi) := PivotVal;
	Pivot := Hi; 
      end Part;
      
    begin
      Lo := Low; Hi := High;
      Part(List, Lo, Hi, Pivot, Comp, Swap);
      if (Lo<Pivot) then Quick1(List, Lo, Pivot-1, Comp, Swap);
      end if;
      if (Hi>Pivot) then Quick1(List, Pivot+1, Hi, Comp, Swap);
      end if;
    end Quick1;

    procedure Quick2(List : in LArray; Size : in INTEGER;
  		     Comp, Swap : out INTEGER) is
    begin
      Comp := 0; Swap := 0;
    end Quick2;

    procedure Quick3(List : in LArray; Size : in INTEGER;
		     Comp, Swap : out INTEGER) is
    begin
      Comp := 0; Swap := 0;
    end Quick3;

    procedure HpSort(List : in out LArray; Size : in INTEGER; 
 		     Comp, Swap : in out INTEGER) is
    Y, Temp : INTEGER;
      
      procedure WalkDown(List : in out LArray; N, J : in INTEGER;
			 C, S : in out INTEGER) is
      L, K, Data : INTEGER;
      Done :  BOOLEAN := FALSE;
      begin
	L := J;
	Data := List(L);
	K := 2*L;
	while (K<=N) and (not Done) loop
	  if (K<N) then
	    C := C+1;
	    if not(List(K+1)< List(K)) then K := K+1; end if;
	  end if;
	  C := C+1;
	  if not(List(K)< Data) then
	    List(L) := List(K);
	    L := K;
	    K := 2*L;
	  else
	    Done := TRUE;
	  end if;
	end loop;
	List(L) := Data;
      end WalkDown;

    begin
      Y := Size/2;
      while (Y>0) loop
        WalkDown(List, Size, Y, Comp, Swap);
 	Y := Y-1;
      end loop;
      Y := Size;
      while (Y>1) loop
	Switch(List(1), List(y), Swap);
	Y := Y-1;
	WalkDown(List, Y, 1, Comp, Swap);
      end loop;     
    end HpSort;
 
  begin
    InitList(UnSorted, LSize);
    NEW_LINE(2);
    PUT_LINE("*************************************");
    PUT_LINE("               Comparsions    Swaps");

    CopyList(Unsorted, List, LSize);
    InSort(List, LSize, Comps, Swaps);
    PUT("INSERTION   "); PUT(Comps); PUT(Swaps); NEW_LINE;

    Comps := 0; Swaps := 0;
    CopyList(Unsorted, List, LSize);
    Quick1(List, 1, LSize, Comps, Swaps);
    PUT("QUICKSORT 1 "); PUT(Comps); PUT(Swaps); NEW_LINE;

    Comps := 0; Swaps := 0;
    CopyList(Unsorted, List, LSize);
    Quick2(List, LSize, Comps, Swaps);
    PUT("QUICKSORT 2 "); PUT(Comps); PUT(Swaps); NEW_LINE;

    Comps := 0; Swaps := 0;
    CopyList(Unsorted, List, LSize);
    Quick3(List, LSize, Comps, Swaps);
    PUT("QUICKSORT 3 "); PUT(Comps); PUT(Swaps); NEW_LINE;

    Comps := 0; Swaps := 0;
    CopyList(Unsorted, List, LSize);
    HpSort(List, LSize, Comps, Swaps);
    PUT("HEAPSORT    "); PUT(Comps); PUT(Swaps); NEW_LINE;

    PUT_LINE("*************************************");
    PUT(LSize); PUT(" Elements"); NEW_LINE(2);
  end DoSorts;
 
begin
  ListSize := GetLSize;
  DoSorts(ListSize);
end Sort;


$ e EGER] => The number of swaps
	
    Pivot : INTEGER;

    procedure Part1(List : in out LArray; Low, High : in INTEGER;
    		   Pivot : out INTEGER; C, S : in out INTEGER) is
	--WHAT:	This is the partition part for the Quicksort algorithms.  It
	--	basically takes the first number and moves it and all the
	-- 	others so that all numbers > than it are on one side and all
	--	numbers less than it are on the other.
	--IN:	List [LArray] => The array to partition
	--	Low [INTEGER] => The starting place of the partitioning
	--	High [INTEGER] => The ending place of the partitioning
	-- 	C [INTEGER] => A count of the number of comparisions
	--	S [INTEGER] => A count of the number of swaps
	--OUT:	List [LArray] => The sorted array of integers
	--	Pivot [INTEGER] => The place that the array is 'split'
	--	C [INTEGER] => The number of comparisons
	--	S [INTEGER] => The number of swaps

      PivotVal, Lo, Hi : INTEGER;
      begin
        Lo := Low; Hi := High; 
        PivotVal := List(Lo);
        while (Lo<Hi) loop
      	  while (PivotVal<List(Hi)) and (Lo<Hi) loop
	    Hi:=Hi-1;  C := C+1;
	  end loop;
	  if (Hi/=Lo) then
	    List(Lo) := List(Hi);  S := S+1;
            Lo := Lo+1;
     	  end if;
	    
	  while (List(Lo)<PivotVal) and (Lo<Hi) loop
	    Lo := Lo+1; C := C+1;
	  end loop;
          if (Hi/=Lo) then
	    List(Hi) := List(Lo); S := S+1;
            Hi := Hi-1;
       	  end if;
        end loop; 
        List(Hi) := PivotVal;
        Pivot := Hi; 
      end Part1;

    begin
      Part1(List, Lo, Hi, Pivot, Comp, Swap);
      if (Lo<Pivot) then Quick1(List, Lo, Pivot-1, Comp, Swap); end if;
      if (Hi>Pivot) then Quick1(List, Pivot+1, Hi, Comp, Swap); end if;
    end Quick1;

    procedure Quick2(List : in out LArray; Lo, Hi : in INTEGER;
		     Comp, Swap : in out INTEGER) is

      Pivot : INTEGER;

      procedure Part2(List : in out Larray; low, High : in INTEGER;
		      Pivot : out INTEGER; C, S : in out INTEGER) is
	--WHAT:	This is the partition part for the Quicksort algorithms.  It
	--	basically takes the first number and moves it and all the
	-- 	others so that all numbers > than it are on one side and all
	--	numbers less than it are on the other.
	--IN:	List [LArray] => The array to partition
	--	Low [INTEGER] => The starting place of the partitioning
	--	High [INTEGER] => The ending place of the partitioning
	-- 	C [INTEGER] => A count of the number of comparisions
	--	S [INTEGER] => A count of the number of swaps
	--OUT:	List [LArray] => The sorted array of integers
	--	Pivot [INTEGER] => The place that the array is 'split'
	--	C [INTEGER] => The number of comparisons
	--	S [INTEGER] => The number of swaps
     Mid : INTEGER;
      begin
	Mid := ((High-Low)/2)+Low;
        if (List(Low)>List(Mid)) then Switch(List(Low), List(Mid), S); end if;
	if (List(Mid)>List(High)) then Switch(List(Mid), List(High), S); end if;
	if (List(Low)>List(Mid)) then Switch(List(Low), List(High), S);end if;
	C := C+3;
	Pivot := Mid;
      end Part2;

    begin
      Part2(List, Lo, Hi, Pivot, Comp, Swap);
      if (Lo<Pivot) then Quick2(List, Lo, Pivot-1, Comp, Swap); end if;
      if (Hi>Pivot) then Quick2(List, Pivot+1, Hi, Comp, Swap); end if;
    end Quick2;

    procedure Quick3(List : in out LArray; Lo, Hi : in INTEGER;
		     Comp, Swap : in out INTEGER) is
	--WHAT:	Your basic recursive Quicksort routine.  Read a book on
	--	algorithms for more details.
	--IN:	List [LArray] => The array (partial?) to be sorted
	--	Lo [INTEGER] => The place to start the sort
	--	Hi [INTEGER] => The place to end the sort
	--	Comp [INTEGER] => A tab on the comparisons
	--	Swap [INTEGER] => A tab on the Swaps
	--OUT	List [LArray] => The Sorted List
	--	Comp [INTEGER] => The number of comparisons
	--	Swap [INTEGER] => The number of swaps

    Pivot, Med, T : INTEGER;
        
      procedure Part3(List : in out Larray; low, High : in INTEGER;
		      Pivot : out INTEGER; C, S : in out INTEGER) is
	--WHAT:	This is the partition part for the Quicksort algorithms.  It
	--	basically takes the first number and moves it and all the
	-- 	others so that all numbers > than it are on one side and all
	--	numbers less than it are on the other.
	--IN:	List [LArray] => The array to partition
	--	Low [INTEGER] => The starting place of the partitioning
	--	High [INTEGER] => The ending place of the partitioning
	-- 	C [INTEGER] => A count of the number of comparisions
	--	S [INTEGER] => A count of the number of swaps
	--OUT:	List [LArray] => The sorted array of integers
	--	Pivot [INTEGER] => The place that the array is 'split'
	--	C [INTEGER] => The number of comparisons
	--	S [INTEGER] => The number of swaps

      PivotVal, Lo, Hi : INTEGER;
      begin
        Lo := Low; Hi := High; 
        PivotVal := List(Lo);
        while (Lo<Hi) loop
      	  while (PivotVal<List(Hi)) and (Lo<Hi) loop
	    Hi:=Hi-1;  C := C+1;
	  end loop;
	  if (Hi/=Lo) then
	    List(Lo) := List(Hi);  S := S+1;
            Lo := Lo+1;
     	  end if;
	    
	  while (List(Lo)<PivotVal) and (Lo<Hi) loop
	    Lo := Lo+1; C := C+1;
	  end loop;
          if (Hi/=Lo) then
	    List(Hi) := List(Lo); S := S+1;
            Hi := Hi-1;
       	  end if;
        end loop; 
        List(Hi) := PivotVal; 
        Med := ((Hi-Low)/2)+Low;
        Pivot := Med;
        if (List(Low)<List(Med)) and (List(Low)>List(Hi)) then Pivot := Low; end if;
        if (List(Low)>List(Med)) and (List(Low)<List(Hi)) then Pivot := Low; end if;
        if (List(Hi)<List(Med)) and (List(Hi)>List(Low)) then Pivot := Hi; end if;
        if (List(Hi)>List(Med)) and (List(Hi)<List(Low)) then Pivot := Hi; end if;
      end Part3;

    begin
      Part3(List, Lo, Hi,  Pivot, Comp, Swap);
      if(Lo<Pivot) then Quick3(List, Lo, Pivot-1, Comp, Swap); end if;
      if(Hi>Pivot) then Quick3(List, Pivot+1, Hi, Comp, Swap); end if;
    end Quick3;

    procedure HpSort(List : in out LArray; Size : in INTEGER; 
 		     Comp, Swap : in out INTEGER) is
	--WHAT: This is your basic array implemented Heapsort algorithm.
	--IN:	List [LArray] => The array to be sorted
	--	Size [INTEGER] => The size of the array
	--	Comp [INTEGER] => A count of the comparisons
	--	Swap [INTEGER] => A count of the Swaps
	--OUT:	List [LArray] => The sorted array
	--	Comp [INTEGER] => The number of comparisons
	--	Swaps [INTEGER] => The number of swaps

    Y, Temp : INTEGER;
      
      procedure WalkDown(List : in out LArray; N, J : in INTEGER;
			 C, S : in out INTEGER) is
	--WHAT: Moves a number from the top of an array implemented heap to the
	--	appropriate place at the bottom.  Esentially it moves the first
	--	element though the list until it makes a heap.
	--IN:	List [LArray] => The array which the walk down is operated on
	--	N [INTEGER] => The size of the array (heap)
	--	J [INTEGER] => The place (for comparisons) in the array (heap)
	--	Comp [INTEGER] => A count of the comparisons
	--	Swap [INTEGER] => A count of the Swaps
	--OUT:	List [LArray] => Hopefully a heap (implement as an array)
	--	Comp [INTEGER] => The number of comparisons
	--	Swaps [INTEGER] => The number of swaps

      L, K, Data : INTEGER;
      Done :  BOOLEAN := FALSE;
      begin
	L := J;
	Data := List(L);
	K := 2*L;
	while (K<=N) and (not Done) loop
	  if (K<N) then
	    C := C+1;
	    if not(List(K+1)< List(K)) then K := K+1; end if;
	  end if;
	  C := C+1;
	  if not(List(K)< Data) then
	    List(L) := List(K);
	    L := K;
	    K := 2*L;
	  else
	    Done := TRUE;
	  end if;
	end loop;
	List(L) := Data;
      end WalkDown;

    begin
      Y := Size/2;
      while (Y>0) loop
        WalkDown(List, Size, Y, Comp, Swap);
 	Y := Y-1;
      end loop;
      Y := Size;
      while (Y>1) loop
	Switch(List(1), List(y), Swap);
	Y := Y-1;
	WalkDown(List, Y, 1, Comp, Swap);
      end loop;     
    end HpSort;
 
  begin
    InitList(UnSorted, LSize);
    for T in 1..10 loop
      Comps := 0; Swaps := 0;
      CopyList(Unsorted, List, LSize);
      InSort(List, LSize, Comps, Swaps);
      InC := InC+Comps; InS := InS+Swaps;

      Comps := 0; Swaps := 0;
      CopyList(Unsorted, List, LSize);
      Quick1(List, 1, LSize, Comps, Swaps);
      Q1C := Q1C+Comps; Q1S := Q1S+Swaps;
 
      Comps := 0; Swaps := 0;
      CopyList(Unsorted, List, LSize);
      Quick2(List,1, LSize, Comps, Swaps);
      Q2C := Q2C+Comps; Q2S := Q2S+Swaps;
 
      Comps := 0; Swaps := 0;
      CopyList(Unsorted, List, LSize);
      Quick3(List, 1, LSize, Comps, Swaps);
      Q3C := Q3C+Comps; Q3S := Q3S+Swaps;
 
      Comps := 0; Swaps := 0;
      CopyList(Unsorted, List, LSize);
      HpSort(List, LSize, Comps, Swaps);
      HpC := HpC+Comps; HpS := HpS+Swaps;
 
    end loop;
 
    NEW_LINE(2);
    PUT_LINE("*************************************");
    PUT_LINE("               Comparsions    Swaps");
    PUT("INSERTION   "); PUT(InC/10); PUT(InS/10); NEW_LINE;
    PUT("QUICKSORT 1 "); PUT(Q1C/10); PUT(Q1S/10); NEW_LINE;
    PUT("QUICKSORT 2 "); PUT(Q2C/10); PUT(Q2S/10); NEW_LINE;
    PUT("QUICKSORT 3 "); PUT(Q3C/10); PUT(Q3S/10); NEW_LINE;
    PUT("HEAPSORT    "); PUT(HpC/10); PUT(HpS/10); NEW_LINE;
    PUT_LINE("*************************************");
    PUT(LSize); PUT(" Elements"); NEW_LINE(2);
  end DoSorts;
 
begin
  ListSize := GetLSize;
  DoSorts(ListSize);
end Sort;