--Mondada Elia 

--programma per il test degli algoritmi di ordinamento

--BUBBLE SORT & QUICK SORT



   with Ada.Text_Io;                    use Ada.Text_Io;

   with Ada.Integer_Text_Io;            use Ada.Integer_Text_Io;

   with Ada.Calendar;                   use Ada.Calendar;

   with Supsi;                          use Supsi;

   with Ada.Numerics.Discrete_Random;







--inizio procedura test dei programmi di ordinamento

   procedure Provasort is

   

   

      type Lista is array (1..10) of Integer;

   

   --Dicchiarazione variabili

      C,D,Lst : Lista;

      Temp,X,Confrontiq,Cambiq,Cambib,Confrontib,Tmp,K : Integer;

      Fin: Character;

   

   --inizio procedura creazione dei vettori

      procedure Creanumeri is

      

      --inizio random

         subtype Rdm is Integer range 1..100;

         package My_Rdm is new Ada.Numerics.Discrete_Random (Rdm);

         use My_Rdm;

      

         G:Generator;

      --fine random

      begin

      

         Reset (G);

      --inizio creazione vettore 

         for I in 1..10 loop

         

            C(I):= Random(G);

         

         end loop;

      --fine creazione random

      

      --creazione di due vettori uguali al vettore iniziale 

         D:= C;

         Lst:=C;

      

      end Creanumeri;

   --fine procedura creazione dei vettori

   

   

   --inizio procedura bubble

      procedure Bubble is

      begin

         Inizio:= Clock; --inizio cronometro  

      

         Cambib:= 0;     --contatori per cambi e confronti

         Confrontib:= 0;

      

      --inizio loop per far girare bubble 1000 volte

         for Y in 1..1000 loop

            Creanumeri;

            X:= 10; --dichiaro x come ultima pos del vettore

         

            loop

            

               Confrontib:= Confrontib + 1;

            

            --inizio controllo dei valori

               if D(X)< D(X-1) then

               --inizio cambio

                  Temp:= D(X);

                  D(X) := D(X-1);

                  D(X-1):= Temp;

               --fine cambio

                  X:=10; --dichiaro x come ultima pos del vettore

               

                  Cambib:= Cambib + 1;

               else

               

                  X:=X-1; --cambio la x nella posizione precedente

               

               end if;

            --fine controllo valori

            

               exit when X=1;

            end loop;

         

         

         end loop;

         Fine:= Clock; --fine cronometro

      

         Cambib:= Cambib/1000;          --calcoli delle medie dei cambi e confronti

         Confrontib:= Confrontib/1000;

      

      --inizio stampa medie controlli e tempo impiegato per il metodo bubble

         Put("Medie su 1000 controlli utilizzando il metodo Bubble Sort");

         New_Line(2);

         Put("sono stati fatti ");

         Put(Confrontib);

         Put(" Confronti");

         New_Line(2);

         Put("sono stati fatti ");

         Put(Cambib);

         Put(" Cambi");

         Stampa_Tempo(Inizio,Fine);

         New_Line;    

         Put("========================================================");

      --fine stampa

      

      end Bubble;

   --fine procedura bubble

   

   --inizio procedura quick

      procedure Quick is

      

      

      --inizio procedura ricorsiva quick

         procedure Qs (Left: in Integer;

                       Right: in Integer;

                       A: in out Lista) is

         begin

         

            if Left < Right then

            

            -- inizio cambio

               Tmp:= A(Left);

               A(Left):= A((Left+Right)/2);

               A((Left+Right)/2):= Tmp;

            -- fine cambio

            

            

               K:= Left;

            

            -- inizio controllo numeri

               for I in Left+1..Right loop

               

                  if A(I) < A(Left) then

                     K:= K+1;

                  

                  -- cambio

                     Tmp:= A(K);

                     A(K):= A(I);

                     A(I):= Tmp;

                  -- fine cambio

                  

                     Cambiq:=Cambiq + 1;

                     Confrontiq:=Confrontiq + 1;

                  else

                     Confrontiq:=Confrontiq + 1;

                  

                  end if;

               

               end loop;

            

            -- cambio

               Tmp:= A(Left);

               A(Left):= A(K);

               A(K):= Tmp;

            -- fine cambio

            

            --ricchiamo la procedura ricorsiva quick

               Qs(Left,K-1,A);

               Qs(K+1,Right,A);

            end if;

         

         end Qs;

      --fine controllo numeri

      

      begin

      

         Cambiq:= 0;     --contatori per cambi e confronti

         Confrontiq:= 0;

      

         Inizio:=Clock; --inizio cronometro

      

      --inizio loop per far girare il quick 1000 volte

         for W in 1..1000 loop

            Qs(1,10,Lst); --richiamo la procedura ricorsiva quick

         end loop;

      --fine loop quick

      

         Fine:=Clock; --fine cronometro

      

      

         Cambiq:= Cambiq/1000;          --calcolo medie cambi e confronti

         Confrontiq:= Confrontiq/1000;

      

      ----inizio stampa medie controlli e tempo impiegato per il metodo quick     

         New_Line(2);

         Put("Medie su 1000 controlli utilizzando il metodo Quick Sort");

         New_Line(2);

         Put("sono stati fatti ");

         Put(Confrontiq);

         Put(" Confronti");

         New_Line(2);

         Put("sono stati fatti ");

         Put(Cambiq);

         Put(" Cambi");

         Stampa_Tempo(Inizio,Fine);

         new_line;

         Put("========================================================");

      --fine stampa

      

      end Quick;

   --fine procedura quick

   

   --inizio procedura stampa

      Procedure stampa is

      

      begin

      --inizio stampa lista non ordinata

         new_line(2);

         Put("Lista:");

         New_Line;

         for I in 1..10 loop

         --       Put(Character'Val(C(I)+65));

            Put(C(I),1);

            Put(" ");

         end loop;

      --fine stampa

      

      --inizio stampa lista ordinata dal bubble sort

         New_Line(2);

         Put("Lista ordinata utilizzando il bubble sort: ");

         New_Line;

         for I in 1..10 loop

         --       Put(Character'Val(D(I)+65));

            Put(D(I),1);

            Put(" ");

         end loop;

      -- fine stampa

      

      

      --inizio stampa lista ordinata dal quick sort

         New_Line(2);

         Put("Lista ordinata utilizzando il quick sort: ");

         New_Line;

         for I in 1..10 loop

         --       Put(Character'Val(lst(I)+65));

            Put(Lst(I),1);

            Put(" ");

         end loop;

      -- fine stampa

      end Stampa;

   

   

   begin

      Creanumeri;            --richiama procedura creazione dei vettori

      Bubble;

      get_immediate(fin);

      Quick;                 --richiama procedura Quick sort

      get_immediate(fin);

      Stampa;                --richiama procedura Bubble sort

      get_immediate(fin);

   end Provasort;

--fine procedura test dei programmi di ordinamento