Insert Sort

L’algoritmo di ordinamento InsertSort (ordinamento diretto) nasce dal concetto che per ordinare un array ordinato è sufficiente costruirne uno nuovo ordinato, inserendo gli elementi al posto giusto da subito. Nella pratica, non è necessario crearne uno nuovo ma dividere quello esistente in due parti, una ordinata e l’altra no.

Esempio:

Vogliamo ordinare l’insieme A = {5, 3, 2, 1, 4}.

Iterazione 1. A = {5 | 2, 3, 1, 4} → A = {2, 5 | 3, 1, 4}

Iterazione 2. A = {2, 5 | 3, 1, 4} → A = {2,3, 5 | 1, 4}

Iterazione 3. A = {2, 3, 5 | 1, 4} → A = {1, 2, 3, 5 | 4}

Iterazione 4. A = {1, 2, 3, 5 | 4} → A = {1, 2, 3,4, 5}

Codificando l’Insert Sort abbiamo:

1: per i = 2, 3,...,n ripeti 
	2: k = i −1 
	3: fintanto che k ≥ 1 e ak > ak+1 ripeti 
		4: scambia ak e ak+1 
		5: k = k −1 
	6: fine-ciclo 
7: fine-ciclo 

Nel caso migliore, ossia quando l’array ègia ordinato, il numero di operazioni svolte dall’algoritmo è dell’ordine di n.

Nel caso peggiore, il numero di operazioni eseguite dall’algoritmo è:

La complessità dell’algoritmo nel caso peggiore è quindi O(n 2 ).

Bubble Sort

L’algoritmo Bubble Sort corregge il difetto principale del naïve sort, ossia il non accorgersi se l’array, a un certo punto, è già ordinato.

L’algoritmo è basato sullo scambio di elementi adiacenti. Ogni coppia di elementi adiacenti viene comparata e invertita di posizione se sono nell’ordine sbagliato. L’algoritmo itera questi passaggi, sulla porzione di array considerata, finché non vengono più eseguiti scambi, situazione che indica che la lista è ordinata.

Deve il suo nome al modo in cui gli elementi vengono ordinati ossia quelli più piccoli “emergono” verso un’estremità della lista, così come fanno le bolle gassose in un bicchiere di acqua minerale; al contrario quelli più grandi “sprofondano” verso l’estremità opposta della sequenza.

Esempio

Abbiamo un array A = {3,5, 2, 4, 1} su cui applichiamo il bubble sort:

1. A = {3,5, 2, 4, 1} → A = {3,5,2, 4, 1} → A = {3, 2,5,4, 1} → A = {3, 2, 4,5,1} → A = {3, 2, 4, 1 | 5}

2. A = {3,2, 4, 1 | 5} → A = {2,3,4, 1 | 5} → A = {2, 3,4,1 | 5} → A = {2, 3, 1 | 4, 5}

3. A = {2,3, 1, | 4, 5} → A = {2,3,1 | 4, 5} → A = {2, 1 | 3, 4, 5}

4. A = {2,1 | 3, 4, 5} → A = {1, 2, 3, 4, 5}

Notare che, alla fine di ogni iterazione, l’elemento più grande del sottoinsieme ancora da ordinare, finisce in fondo alla sequenza, nella sua posizione definitivamente corretta, mentre la sottosequenza ancora in disordine si riduce di volta in volta di un elemento.

Codificando il Bubble Sort si ha:

1: flag = 1 
2: stop = n −1 
3: fintanto che flag = 1 ripeti
	 4: flag = 0 
	 5: per i = 1, 2,...,stop  ripeti 
		6: se ai > ai+1 allora 
			7: scambia ai e ai+1 
			8: flag = 1 
		9: fine-condizione 
	10: fine-ciclo 
	11: stop = stop −1 
12: fine-ciclo 

Anche in questo caso abbiamo due cicli annidati, ma, stavolta, l’algoritmo usa la variabile flag per terminare l’esecuzione, nel caso in cui l’insieme risulti ordinato.

Nel caso migliore, ossia quando l’insieme è già ordinato, l’algoritmo esegue un’unica scansione, quindi il numero di operazioni eseguite sarà dell’ordine di n.

Nel caso peggiore, alla prima iterazione vengono eseguite dunque sono necessarie n − 1 iterazioni del ciclo esterno per ordinare l’intera sequenza. Alla seconda n-2, e cosi via. Quindi il numero di operazioni svolte è:

Concludendo la complessità computazionale del Bubble Sort è di O(n 2 ).

Naive Sort ( o SelectionSort)

L’algoritmo naive sort, anche detto per selezione diretta o SelectionSort, ripete per n volte una procedura in grado di selezionare alla i-esima iterazione l’elemento più piccolo nell’insieme e di scambiarlo con l’elemento che in quel momento occupa la posizione i-esima.

Ossia, alla prima iterazione verrà selezionato l’elemento più piccolo dell’intero insieme e sarà scambiato con quello che occupa la prima posizione; alla seconda iterazione sarà selezionato il secondo elemento più piccolo dell’insieme ridotto (cioè costituito dagli elementi {a2,a3,…,an} ) e sarà scambiato con l’elemento che occupa la seconda posizione, e così via fino ad aver collocato nella posizione corretta tutti gli n elementi.

Considerando un vettore di n elementi l’algoritmo può essere codificato nel seguente modo :

per i = 1, 2,...,n ripeti
	per j = i +1,...,n ripeti
		se aj < ai allora
			scambia ai e aj
		fine-condizione
	fine-ciclo
fine-ciclo

Esempio

Supponiamo di applicare il naive sort al seguente array

A = {4, 2, 1, 3}

Ad ognuno dei passi dell’algoritmo, viene selezionato l’elemento più piccolo nella porzione di insieme ancora da ordinare, scambiandolo con l’elemento che si trova nella prima posizione di tale sottoinsieme.

i = 1 A = (4, 2,1, 3) → A = (1 | 2, 4, 3)

i = 2 A = (1 | 2, 4, 3) → A = (1, 2 | 4, 3)

i = 3 A = (1, 2, | 4,3) → A = (1, 2, 3 | 4)

i = 4 A = (1, 2, 3 | 4) → A = (1, 2, 3, 4)

Dopo 4 iterazioni, l’array sarà ordinato.

Per misurare le prestazioni dell’algoritmo (anche detta complessità) conteremo il numero di confronti.

Alla prima ripetizione del ciclo esterno vengono compiute n −1 operazioni con il ciclo interno; alla seconda ripetizione del ciclo esterno vengono eseguite n−2 operazioni con il ciclo interno, e così via fino a quando i = n.

Il numero di confronti totali sarà:

(N-1) + (N-2) + (N-3) + … + 2 + 1 = N*(N-1)/2 = O(N2)

Da notare che l’algoritmo fa gli stessi confronti sia per un array disordinato, sia per un array già ordinato, ossia per il naive sort non esiste un caso migliore o peggiore ma fa sempre tutti i confronti.

Viene usato quando l’insieme da ordinare è composto da pochi elementi e quindi, anche se non è molto efficiente, ha il vantaggio di non essere troppo difficile da implementare.

Test Java Online

1. Considerando il seguente frammento di codice:

[java]

public class SuperInheritance {
public void print() {
System.out.print(“super”);
}

private void printHello() {
System.out.println(“hello”);
}
}

class Inheritance extends SuperInheritance {
@Override
public void print() {
System.out.println(“this”);
}

public static void main(String[] args) {
Inheritance inheritance = new Inheritance();
inheritance.print();
inheritance.printHello();
}

}

[/java]

Quale output verrà prodotto?

 
 
 

2. Considerando il seguente frammento di codice:

private int field;

public DefaultConstructor (int field)       {this.field = field;}

public static void main(String [] args){

DefaultConstructor instanceOne = new DefaultConstructor(1);

System.out.println(“IstanceOneValue: “  +instanceOne.getField());

DefaultConstructor defaultInstance = new DefaultConstructor( );

System.out.println(“DefaultInstanceValue: “+defaultInstance.getField());

}

Public int getField() { return field; }

 

Quale output verrà prodotto:

 
 
 

3. Quanti tipi di EJB Session conosci?

 
 
 

4. Quale delle seguenti affermazioni, riferita ad una classe anonima, è vera?

 
 
 

5. Le interfacce devono essere estese o implementate?

 
 

6. Considerando il seguente frammento di codice:

Quale output verrà prodotto:

 

 

 

 
 
 
 

7. Un Ejb Session può essere deployato su Tomcat

 
 

8.

Una classe astratta deve avere per avere per forza almeno un metodo astratto?
 
 

9. Quali delle seguenti affermazioni relative agli Ejb sono vere?

a) Se non diversamente specificato la transazione è sempre gestita dal container.
b) Gli ejb necessitano di un Web Server per essere eseguiti
c) È consigliabile l’utilizzo dell’interfaccia Locale nel caso in cui ejb e client si trovino nello stesso server.

 
 
 

10. Considerando il seguente frammento di codice:

int x = 1;
while(x>0) x++;

Quali delle seguenti affermazioni è vera?

 
 
 
 

11. Quale sarà l’output del programma?

class PassA 
{
    public static void main(String [] args) 
    {
        PassA p = new PassA();
        p.start();
    }

    void start() 
    {
        long [] a1 = {3,4,5};
        long [] a2 = fix(a1);
        System.out.print(a1[0] + a1[1] + a1[2] + " ");
        System.out.println(a2[0] + a2[1] + a2[2]);
    }

    long [] fix(long [] a3) 
    {
        a3[1] = 7;
        return a3;
    }
}
 
 
 
 

12. Quale sarà l’output

for(int i = 0; i < 3; i++) 
{ 
    switch(i) 
    { 
        case 0: break; 
        case 1: System.out.print("one "); 
        case 2: System.out.print("two "); 
        case 3: System.out.print("three "); 
    } 
} 
System.out.println("done")
 
 
 
 

13. Quale sarà l’output?

 

public class X 
{  
    public static void main(String [] args) 
    {
        try 
        {
            badMethod();  
            System.out.print("A");  
        } 
        catch (RuntimeException ex) /* Line 10 */
        { 
            System.out.print("B"); 
        } 
        catch (Exception ex1) 
        { 
            System.out.print("C"); 
        } 
        finally 
        {
            System.out.print("D"); 
        } 
        System.out.print("E"); 
    } 
    public static void badMethod() 
    { 
        throw new RuntimeException(); 
    } 
}
 
 
 
 

14. Quale sarà l’output

interface calculate {
        void cal(int item);
    }
    class display implements calculate {
        int x;
        public void cal(int item) {
            x = item * item;            
        }
    }
    class interfaces {
        public static void main(String args[]) {
            display arr = new display;
            arr.x = 0;      
            arr.cal(2);
            System.out.print(arr.x);
        }
    }
 
 
 
 

15. Quale sarà l’output?

class s1 implements Runnable 
{ 
    int x = 0, y = 0; 
    int addX() {x++; return x;} 
    int addY() {y++; return y;} 
    public void run() { 
    for(int i = 0; i < 10; i++) 
        System.out.println(addX() + " " + addY()); 
} 
    public static void main(String args[]) 
    { 
        s1 run1 = new s1(); 
        s1 run2 = new s1(); 
        Thread t1 = new Thread(run1); 
        Thread t2 = new Thread(run2); 
        t1.start(); 
        t2.start(); 
    } 
}
 
 
 
 

Question 1 of 15

Esempio di WebServices con Annotation – Client SOAPUI

Per creare un Web Services esistono vari modi.
In questo esempio useremo l’annotation @WebService. In particolare avremo un web services con due operazioni:

  • public String prova(String msg)
  • public Persona getPerson(String codFisc)

Il primo prende in input una stringa e restituisce un’altra stringa.
Il secondo in input  sempre una stringa ma restituisce un oggetto di tipo Persona.
Per invocarli useremo il tool SOAPUI.

Tools Usati

  • Eclipse Mars 2
  • Wildfly 10
  • SoapUI

Continua a leggere

MDB (Message Driven Bean) in 5 minuti

MDB: Cosa sono

Di solito le comunicazioni fra i componenti di un’applicazione sono sincrone, ossia l’oggetto che effettua la chiamata e l’oggetto che viene invocato devono essere entrambi presenti affinché la comunicazione possa avvenire.
Un message-oriented middleware (MOM) è un software che consente a due componenti di comunicare in maniera asincrona. Java Messaging Service (JMS) fornisce uno standard di accesso ai MOM che costituisce un’alternativa all’utilizzo di API proprietarie; ad eccezione di Microsoft Message Queuing, la maggior parte dei prodotti MOM infatti supporta JMS. Il client notifica una certa operazione al server inviando un messaggio (il client in questo caso è detto producer). Il server inserisce i messaggi in un canale sulla quale stanno in ascolto altri client che prelevano il messaggio ed eseguono le operazioni richieste (i componenti in ascolto vengono detti consumer).
Un modello di messaging definisce il modo in cui il processo di messaging coinvolge mittenti e destinatari. I due modelli più popolari, standardizzati in Java EE, sono il point-to-point e il pubish-subscribe.
Nello schema point to point il mittente (Producer) invia un messaggio verso una particolare destinazione. Il ricevente (Consumer) sta in ascolto e riceve i messaggi su quella destinazione(chiamata coda o queue). L’intento del producer è inviare un messaggio ad uno specifico consumer che sarà l’unico a riceverlo, anche se al momento dell’invio non è disponibile. (ci sarà solo un consumer per quella coda queue). Sarà infatti il JMS Broker (servizio che gestisce lo scambio dei messaggi) a tenerlo in coda finché non sarà prelevato dal consumer.
Nello schema publish-subscribe un singolo produttore invia un messaggio ad una destinazione ( che prende il nome di topic) e tutti i consumatori che sono registrati presso quel topic possono riceverlo. Questo modello lavora si adatta particolarmente bene nel caso in sui si voglia effettuare il broadcasting di informazioni verso diversi sistemi.
Un Message-Driven Bean (MDB) è un componente EJB che consuma messaggi da una queue/topic, inviati da un valido client JMS. Per crearlo è sufficiente usare l’annotation:

@MessageDriven

e implementare l’interfaccia MessageListener.

MDB: Esempio

Continua a leggere

Ejb Session Stateless Esempio

EJB Session Staleless: cosa sono

Gli EJB Session Bean sono delle classi con dei metodi invocabili da remoto (semplificando molto possiamo dire che sono come le servlet, ma le servlet hanno solo due metodi doget e dopost, i session invece possono avere tutti i metodi che vogliamo). Sono composti da una classe e due interfacce. Per poter invocare un EJB Session bisogna avere una delle interfacce. Le interfacce sono dette locali o remote, in basa a dove permettono di richiamare il session. Da remoto vengono utilizzati i protocolli distribuiti come RMI-IIOP (Remote Method Invocation o RMI è una tecnologia che consente l’invocazione remota dei metodi);
Gli EJB Session sono transazionali, ossia permettono di gestire le transazioni.
Esistono due tipi di session bean:

  • stateful:  viene memorizzato lo stato fra una richiesta e l’altra del client, ossia garantisce che tutti i campi   dell’EJB Session saranno salvati per la successiva richiesta dello stesso client.
  • stateless: non viene mantenuto alcun stato e vengono utilizzati per modellare quelle elaborazioni che si completano con una sola richiesta

 

 

EJB Session Staleless: esempio

Continua a leggere

Java Syncronized: Come si usa esempio

Java Syncronized: Cos’è

Ad ogni oggetto (o anche ad un pezzo di codice) si può associare un semaforo (un lock). Ogni semaforo ha due operazioni: Get e Release. Quando un thread accede ad una zona critica tenta di prendere possesso del semaforo (Get); se non ci riesce verrà messo a dormire e ci ritenterà fino a quando un altro thread rilascerà (Release) tale semaforo.
Questi “semafori” in java vengono introdotti con la parola chiave “syncronized“. Si possono sincronizzare sia classi che metodi.
Quando un thread vuole accedere ad un metodo/blocco synchronized, deve acquisire il lock dell’oggetto (impedendo così l’accesso ad ogni altro thread).  Il lock viene automaticamente rilasciato quando il thread esce dal metodo/blocco synchronized(o se viene interrotto da un’eccezione).
Un thread che non riesce ad acquisire un lock rimane sospeso sulla richiesta della risorsa fino a che il lock non è disponibile. Ad ogni oggetto viene assegnato un solo lock: due thread non possono accedere contemporaneamente a due metodi/blocchi synchronized diversi di uno stesso oggetto.Tuttavia altri thread sono liberi di accedere a metodi/blocchi non synchronized associati allo stesso oggetto.

Java Syncronized: Esempio

Continua a leggere