Precisazione sulla visibilita delle variabili durante

l’esecuzione delle funzioni

var a = new Array (4);

var y= 7;

function foo(vet,x) {var i=0;

...

} //fine foo

foo(a,y);

print(y);

✲

Stato

a e vet sono 2 nomi diversi per lo stessoarray, mentre y e x sono due variabili diverseche per un accidente hanno lo stesso valore

{(a, ),(y,7) (foo, function (vet,x) {...}), (vet, ), (x,7) (i,0)}❄ ✛

0 61 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 1

Precisazione sulla visibilita delle variabili durante

l’esecuzione delle funzioni

var a = new Array (4);

var y= 7

function foo(vet,x) {var i=0;

x=34;

...

} //fine foo

foo(a,y);print(y);

✲

Stato

se modifico x, y rimane invariato. y e visibilee modificabile nella funzione ma e globale: davietato usarle in questo corso

{(a, ),(y,7) (foo, function (vet,x) {...}), (vet, ), (x,34) (i,0)}❄ ✛

0 61 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 2

Non e necessario usare nomi diversi

var a = new Array (4);

var y= 7

function foo(a,y) {var i=0;

y=34;

} //fine foo

foo(a,y);

print(y);

✲

Stato

le variabili locali alla funzione hanno gli stessinomi delle variabili globali ma sono variabilidiverse

{(a, ),(y,7) (foo, function (a,y) {...}), (a, ), (y,7) (i,0)}❄ ✛

0 61 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 3

Non e necessario usare nomi diversi

var a = new Array (4);

var y= 7

function foo(a,y) {var i=0;

y=34;

} //fine foo

foo(a,y);

print(y);

✲

Stato

le variabili globali non sono in questo casoaccessibili perche sono coperte dalle variabililocali.

{(a, ),(y,7) (foo, function (a,y) {...}), (a, ), (y,34) (i,0)}❄ ✛

0 61 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 4

Non e necessario usare nomi diversi

var a = new Array (4);

var y= 7

function foo(a,y) {var i=0;

y=34;

} //fine foo

foo(a,y);

print(y);✲

Stato

Quando l’esecuzione della funzione termina,il controllo torna al programma chiamante ele variabili ritornano accessibili. print(y)

stampa 7.

{(a, ),(y,7) (foo, function (a,y) {...}), (a, ), (y,34) (i,0)}❄ ✛

0 61 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 5

Funzioni che restituiscono array

In JavaScript le funzioni possono anche restituire array come risultatodella computazione:

Esempio: La funzione leggiVet puo essere scritta anche cosi‘:

var k = asknum(), a;

function leggiVet(n) {var vet=new Array(n), i;

for (i = 0; i < vet.length; i++)

vet[i]=asknum();

return vet; //fine leggiVet }a=leggiVet(k);

...

� Il chiamante passa alla funzione solo la dimensione (k) dell’array dacreare e inizializzare e dichiara la variabile a senza inizializzarla.

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 6

Evoluzione dello stato

var k=asknum(), a;

function leggiVet(n) {var i, vet=new Array(n), i;;

for (i=0; i<vet.length; i++)

vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);✲

Stato

Stato in cui viene invocata leggiVet nel casoin cui il valore in input sia 4. L’esecuzione delprogramma principale viene sospesa e passa adeseguire la funzione.

{(k,4), (a,undefined ), (leggiVet, function (n) {...})}

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 7

Evoluzione dello stato

var k=asknum(), a;

function leggiVet(n) {var vet=new Array(n), i;

for (i=0; i<vet.length; i++)

vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);

✲

Stato

Stato durante l’invocazione di leggiVet, dopola dichiarazione delle variabili

{(k,4), (a,undefined ), (leggiVet, function (n) {...}),(n,4),(vet, ), (i,undefined),}

❄0 undefined1 undefined2 undefined3 undefined

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 8

Evoluzione dello stato

var k=asknum(), a;

function leggiVet(n) {var vet=new Array(n), i;

for (i=0; i<vet.length; i++)

vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);

✲

Stato

Stato durante l’invocazione di leggiVet, dopol’esecuzione del for nel caso in input siano statiimmessi i valori 8,-2,0,1

{(k,4), (a,undefined ), (leggiVet, function (n) {...}),(n,4),(vet, ), (i,4),}

❄0 81 -22 03 1

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 9

Evoluzione dello stato

var k=asknum(), a;

function leggiVet(n) {var vet=new Array(n), i;

for (i=0; i<vet.length; i++)

vet[i]=asknum();

return vet;//fine leggiVet }a=leggiVet(k);✲

Stato

Stato dopo la terminazione dell’asecuzione dileggiVet e dell’assegnamento del reference,risultato della invocazione alla variabile a delchiamante.

{(k,4), (a, ), (leggiVet, function (n) {...})}�

��✠

0 81 -22 03 1

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 10

Ordinamento

Data una sequenza di elementi in ordine qualsiasi, ordinarla.

� Questo e un problema fondamentale, che si presenta in moltissimicontesti, ed in diverse forme.

� Nel nostro caso formuliamo il problema in termini di ordinamento divettori:

Dato un array A di n elementi, ordinarlo in modo crescente

� Per semplicita faremo sempre riferimento a vettori di interi.

5 2 4 6 1 3=⇒

1 2 3 4 5 6

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 11

Ordinamento per selezione del minimo (selection sort)

� Esempio: Ordinamento di un mazzo di carte� Ho 2 gruppi di carte: N carte non ordinate, O carte ordinate� si seleziona la carta piu piccola di N e la si inserisce in prima posizione

in O� delle rimanenti di N si seleziona la piu piccola e la si inserisce in

seconda posizione in O ecc.� rimane una sola carta in N e la si inserisce in ultima posizione in O� si termina quando non ci sono piu carte

� Ordinamento di un array, abbiamo 2 cicli :� per inserire l’elemento corretto in ogni posizione dell’array (scansione

di tutto l’array)� per ogni posizione e neccessario selezionare l’elemento piu piccolo tra i

rimanenti.

Per non perdere elementi e per lavorare sui rimanenti dobbiamoscambiare l’elemento piu piccolo selezionato con l’elemento che sitrova nella posizione corrente. In questo modo abbiamo una porzionedi array non ordinata (N) e una porzione di array ordinata (O).

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 12

� in nero la parte che rimane da analizzare (N)in blu l’elemento minimo selezionatoin verde lo scambio effettuatoin rosso la parte ordinata (O)in marrone gli indici

0 1 2 3 4 50 5 2 4 6 1 3

5 2 4 6 1 31 2 4 6 5 3

1 1 2 4 6 5 31 2 4 6 5 31 2 4 6 5 3

2 1 2 4 6 5 31 2 4 6 5 31 2 3 6 5 4

3 1 2 3 6 5 41 2 3 6 5 41 2 3 4 5 6

4 1 2 3 4 5 61 2 3 4 5 61 2 3 4 5 6

5 1 2 3 4 5 61 2 3 4 5 6

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 13

Implementazione dell’ordinamento per ricerca dei minimi in

JavaScript

Definiamo la funzione principale selSort

function selSort(vet){var i, temp,k;

for (i=0; i<vet.length-1; i++)

{k=minPos(vet,i,vet.length);temp=vet[i];

vet[i]=vet[k];

vet[k]=temp;

}Resta da definire minPos

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 14

Implementazione della ricerca della posizione dell’elemento

minimo in una porzione di array

Definizione della funzione minPos che calcola la posizionedell’elemento dell’array che contiene il valore minimo relativamente allporzione di array contenuta tra i valori dei 2 indici passati comeparametri (i, vet.length-1)

function minPos(vet,from, to){var min=from;

for (from++; from<=to; from++)

if (vet[from]<vet[min]) min=from;

return min;

}Sono tutti necessari i 3 parametri di minPos?

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 15

Programma principale per testare la procedura di

ordinamento definita

Usiamo la procedura leggiVet definita precedentemente e la print

predefinita.

var a=new Array(8);

leggiVet(a); //inizializzazione di a

print(a); //stampa di a

selSort(a); //ordinamento di a

print(a); //nuova stampa di a

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 16

Ordinamento a bolle (bubble sort)

E simile al precedente, cambia il modo di portare l’elemento minimodella porzione di array ancora non ordinata nella posizione corretta.

� l”idea e che si fanno galleggiare gli elementi piu piccoli (“piu leggeri”)verso l’inizio dell’array (“verso l’alto”), scambiandoli con quelliadiacenti.

� L’ordinamento e suddiviso in n-1 fasi:� fase 0: 0o elemento (il piu piccolo) in posizione 0� fase 1: 1o elemento in posizione 1� · · ·� fase n-2: (n-2)o elemento in posizione n-2, e quindi

(n-1)o elemento in posizione n-1

� Nella fase i: cominciamo a confrontare dal basso e portiamol’elemento piu piccolo (piu leggero) in posizione i

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 17

5 2 4 6 1 35 2 4 6 1 35 2 4 1 6 35 2 1 4 6 35 1 2 4 6 31 5 2 4 6 3

1 5 2 4 6 31 5 2 4 3 61 5 2 3 4 61 5 2 3 4 61 2 5 3 4 6

1 2 5 3 4 6

1 2 3 5 4 6

1 2 3 4 5 6

1 2 3 4 5 6

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 18

� Si usano due for annidati:� il piu esterno itera sulle i posizioni dell’array.� il piu interno per portare l’elemento piu piccolo (della porzione non

ordinata) in posizione i-esima

function bubbleSort(vet) {var temp,i,j;

for (i = 0; i < vet.length-1; i++)

for (j = vet.length-1; j > i; j--)

if (vet[j] < vet[j-1]){temp=vet[j];

vet[j]= vet[j-1];

vet[j-1]=temp;} }

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 19

Operazioni che sfruttano la dinamicita degli array

� L’operazione primitiva che permette di modificare il numero deglielementi di un array e l’aggiunta di uno o piu elementi in fondoall’array:

� Esempio: vet[vet.length]=asknum();

Aggiunge un elemento all’array vet di indice vet.length e valoreletto dall’input.

� Esempio: vet[vet.length+2]=asknum();

Aggiunge 3 elementi all’array vet due di indice vet.length evet.length+1 e valore undefined e uno di indice vet.length+2 evalore letto dall’input.

� esistono alcune operazioni (metodi) predefinite che permettono anchedi eliminare elementi da un array. Li vedremo piu avanti.

� tutti gli esempi visti considerano array il cui numero di elementi restacostante durante tutta l’esecuzione. Vediamo ora degli esempi diprogrammi che aggiungono elementi ad un array.

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 20

Inserzione di un elemento in un array ordinato

� Se una struttura dati (array) e statica ovvero il numero dei suoielementi non cambia, ha senso avviare una procedura di ordinamentoal momento dell’inizializzazione.

� Se viceversa una struttura dati (array) e dinamica la cosa piu sensatae di mantenerla ordinata, inserendo i nuovi elementi in modo cherispettino l’ordinamento.

� notare che un array vuoto, dimensione 0 e ordinato per definizione e

� lo stesso vale per un array di un unico elemento.� per inserire un nuovo elemento al posto giusto dobbiamo

� scorrere gli elementi che lo precedono per decidere la posizione che glicompete

� spostare di un posto verso destra gli elementi maggiori per fargli spazio.

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 21

Un esempio

� In nero l’elemento da inserire,� in rosso gli elementi gia inseriti nell array []� in blu gli elementi gia inseriti che e stato necessario spostare al passo

precedente� se l’elemento da inserire andra ad occupare una posizione gia

occupata, l’elemento corrispondente e sottolineato.

5 [ ][5]

2 [5][2, 5]

4 [2, 5][2, 4, 5]

1 [2, 4, 5][1, 2, 4, 5]

3 [1, 2, 4, 5][1, 2, 3, 4, 5]

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 22

� Una volta individuata la posizione i in cui inserire il nuovo elementodobbiamo farle spazio, ovvero spostare verso destra di una posizionetutti gli elementi da i in poi.

Inserzione di 3, da inserire in posizione 2

0 1 2 3 43 1 2 4 53 1 2 4 5

1 2 3 4 5

E necessario spostare 5 in posizione 4 e 4 in posizione 3

� A questo punto la posizione 2 e libera e possiamo inserire l’elementoin modo ordinato

1 2 3 4 5

� Se l’elemento da inserire e maggiore di tutti gli elementi dell’arraynon dobbiamo spostare nulla, ma inserire in fondo.

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 23

Shift a destra per array dinamici

� Dobbiamo percio definire una procedura che sposta tutti gli elementidi un array (vet verso destra di una posizione a partire da una dataposizione from<vet.length).

� dobbiamo aggiungere un nuovo elemento all’array che ha come valoreil valore dell’elemento che si trova in ultima posizione, che quindi nonviene perso

� Bisogna procedere da destra verso sinistra per non perdere glielementi

function shiftRD(vet, from)

{var j;

for (j=vet.length; j>from; j--)

vet[j]=vet[j-1];

}

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 24

Possiamo ora definire la procedura di ordinamento per inserzione comesegue

function insOrd(vet, x){var i=0, trovato=false;

while (i<vet.length && !trovato) {if (a[i]<x) i++;

else trovato=true;}if (!trovato) a[vet.length]=x;

else { shiftRD(vet, i);

vet[i]=x; } }� i e la posizione in cui dobbiamo inserire il nuovo elemento, e cioe in

caso di ordinamento crescente la posizione del primo elemento cherisulta > del valore che stiamo inserendo.

� se sono ammessi elementi ripetuti cambia qualcosa?

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 25

Un’altra soluzione piu compatta

� Questa soluzione utilizza una funzione insertInPos con 3 parametri:

� l’array vet,� la posizione p in cui inserire l’elemento� l’elemento da inserire x

� La funzione si preoccupa di spostare a destra tutti gli elementi,aumentando la dimensione dell’array per poter memorizzare unelemento in piu.

function insertInPos(vet,p,x) {var j;

for (j=vet.length; j>p; j--)

vet[j]=vet[j-1];

vet[i]=x; }

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 26

La nuova definizione della funzione insOrd

� Notare la guardia del while (i<vet.length && a[i]<x).

� Questa condizione e corretta per la regola di valutazione strettadell’&&.

� Se la prima condizione i<vet.length e falsa, la seconda condizionea[i]<x non viene valutata.

function insOrd(vet, x){var i=0,

while (i<vet.length && a[i]<x) i++;

insertInPos(vet, i, x); }

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 27

Ancora un’altra soluzione per insOrd

� Questa soluzione usa un metodo predefinito su oggetti array, invecedella funzione insertInPos definita sopra:

il metodo splice viene invocato con nomeArray.splice(p,0,x),quindi abbiamo:

function insOrd(vet, x){var i=0,

while (i<vet.length && a[i]<x) i++;

vet.splice(i,0, x); }

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 28

Eliminazione di elementi da un array

� La rimozione di un elemento da un array non e un’operazioneprimitiva e puo essere effettuata solo attraverso i metodi: uno diquesti e ancora il metodo splice,

� indicando la posizione del primo elemento da rimuovere e il numero dielementi da rimuovere,

� ad esempio con nomeArray.splice(p,1), viene rimosso l’elementoin posizione p :

function EliminaElem(vet, x){var i=0,

while (i<vet.length && a[i]<=x) i++;

if (i!=vet.length) vet.splice(i,1); }

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 29

Merge di due array ordinati

a2 4 6 8

0 1 2 3

b1 4 6 9 17

0 1 2 3 4

c

0

Si scandiscono a e b insieme finche entrambi contengono elementi e siseleziona l’elemento piu piccolo tra i due esaminati, che viene aggiunto a cdinamicamente. Abbiamo 3 indici uno per ogni array.

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 30

Merge di due array ordinati

a2 4 6 8

0 1 2 3

b1 4 6 9 17

0 1 2 3 4

c1 2 4 4 6 8 9 10 17

0 1 2 3 4 5 6 7 8

Situazione finale

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 31

Merge di due array ordinati

function merge (a,b){var c=new Array(), i=0,j=0,k=0;

while (i<a.length && j<b.length)

{if (a[i] < b[j]) {c[k]=a[i]; i++;}else {c[k]=b[j]; j++;}k++;}

while (i<a.length) {c[k]=a[i]; i++;k++;}while (j<b.length) {c[k]=b[j]; j++;k++;}return c;

}

E. Occhiuto – Fondamenti Teorici e Programmazione- 437AA – pag. 32