program Uso_Array

const Imax = 100;

type VettInt = array [1..Imax] of integer;

var a:VettInt;
    n,max:integer;


procedure ReadArray(var v:VettInt; n:integer);

 var i:integer;

 begin
  for i:=1 to n do
   begin
    writeln('Elemento numero ',i,':');
    readln(v[i]);
   end
 end;


procedure WriteArray(var v:VettInt; n:integer);

 var i:integer;

 begin
  for i:=1 to n do
   begin
    writeln('Elemento numero ',i,' : ');
    writeln(v[i]);
   end
 end;


function MaxVett(var v:VettInt; n:integer):integer;

var i, max: integer;

begin
   max:=v[1];
   for i:=2 to n do
     if (v[i]>max) then max:=v[i];
   MaxVett:=max
end;


procedure scambia (var a,b:integer);

 var temp:integer;

 begin
  temp:=a;
  a:=b;
  b:=temp
 end;


procedure SelectionSort (var v:VettInt; n:integer);
 
 {pre:}
 {post: restituisce l'array ordinato in ordine crescente}

 var pos,i,j:integer;

 begin
  for i:=1 to n-1 do    {rendi v[1..i] ordinato e tale che sia <= di v[i+i..n]}
   begin {trova la posizione del piu` piccolo elemento in a[i..n]}
    pos:=i;
    for j:=i+1 to n do {trova la posizione del piu` piccolo elemento in a[i..j]}
     if (v[j] < v[pos]) then pos:=j;
    scambia(v[i],v[pos]); {questa istruzione fa parte del ciclo 'for' piu' esterno!}
   end
 end;

{NOTA 1: A lezione, insieme, avevamo trovato la soluzione seguente:

procedure SelectionSort (var v:VettInt; n:integer);

 var i,j:integer;

 begin
  for i:=1 to n-1 do
   for j:=i+1 to n do
    if (v[j] < v[i]) then scambia(v[i],v[j]);
 end;

Questa soluzione (B) differisce da quella data sopra (A) solo per il numero di scambi 
effettuati.  Infatti la versione A fa uno scambio soltanto (tra a[i] e a[pos]), dopo
aver ultimato la ricerca della posizione dell'elemento minimo (che si trovera` appunto
in posizione 'pos'). La versione B, invece, scambia v[i] con v[j] ogni volta che 
v[j] e` piu' piccolo di v[i] (calcola il minimo fra gli elementi compresi tra i e j, e, 
ovviamente, quando j = n in v[i] ci sara` il minimo assoluto tra i e n).

NOTA 2: dal punto di vista della complessita` in termini di tempo (misurata in termini
del numero di iterazioni fatte), il SelectionSort e` O(n^2), ovvero l'istruzione
dentro il 'for' piu' interno viene eseguita un numero di volte proporzionale a
n^2 (dove n e` il numero di elementi nel vettore). Infatti tale istruzione viene 
eseguita (n-1) volte quando i=1, (n-2) volte quando i=2,... , 1 volta quando i=n-1. La
somma (n-1)+(n-2)+...+1 e` uguale a (n(n-1))/2 (siccome la sommatoria dei primi
'k' numeri naturali e` uguale a ((k+1)k)/2), per cui il numero di volte che tale
istruzione e` eseguita e` (n^2-n)/2 (per cui proporzionale a n^2).
}




procedure InsertionSort (var v:VettInt; n:integer);

LA SOLUZIONE SARA` PRESENTATA IN UNA DELLE PROSSIME LEZIONI
 




{main program}

begin

 repeat
  begin
   writeln('Inserisci il numero degli elementi (0 < num elem <= 100):');
   readln(n);
  end
 until (n>0) AND  (n <= Imax);
 writeln;
 writeln('Inserisci gli elementi nel vettore (', n, '):');
 ReadArray(a,n);
 writeln;
 readln;

 max:=MaxVett(a,n);
 writeln('Stampa del Vettore');
 WriteArray(a,n);
 writeln;
 writeln('Il massimo e` ', max);
 writeln;
 readln;

 {Uso del SelectionSort1}
 writeln('** Vettore non ordinato **');
 WriteArray(a,n);
 writeln;
 SelectionSort(a,n);
 writeln('** Vettore Ordinato con SelectionSort **');
 WriteArray(a,n);
 writeln;
 readln;

 {Uso dell'InsertionSort}
 writeln('Inserisci gli elementi nel vettore (', n, '):');
 writeln;
 ReadArray(a,n);
 writeln;
 readln;
 InsertionSort(a,n);
 writeln('** Vettore Ordinato con InsertionSort **');
 WriteArray(a,n);
 readln;

end.