Merge Sort

Il Merge Sort,  inventato da John Von Neumann nel 1945, è molto simile al Quick Sort, ma  l’elemento pivot, in questo caso, viene scelto sempre nel centro.

L’idea principale è che, avendo due array ordinati, è molto semplice fonderli in un unico array ordinato. Inoltre,  un’array di un elemento  è sempre ordinato.

Unendo questi concetti,  si ha un algoritmo che, dopo aver suddiviso ricorsivamente l’array iniziale A in n sotto-array, costituiti da un solo elemento,  fonde i sotto-array e fino a ottenere  un’unico array ordinato.

Codificando il tutto si ha:

L’algoritmo è diviso in due metodi: il MergeSort e il Merge.

Il MergeSort riceve in input l’array A e i due indici p e r, che permettono di identificare l’elemento ap e l’elemento ar, ossia il primo e l’ultimo elemento.

Esso divide, ricorsivamente,  l’array in due parti, in modo tale che i due sotto-array ottenuti abbiano un ugual numero di elementi (a meno di uno, nel caso di insiemi con cardinalità dispari). Durante la suddivisione l’array non viene modificato.

La riga 2 del codice individua l’indice q dell’elemento che si trova a metà dell’array.

Dopodiché, viene chiamato ricorsivamente il metodo MergeSort sulla prima metà e sulla seconda metà.

La procedura si ripete ricorsivamente fino a quando si arriva ad array composti da un solo elemento, ossia  quando p = r .

A questo punto, entra in gioco la procedura Merge, che provvede alla “fusione” dei due array  A0 = {ap ,ap+1,…,aq } e A 00 = {aq+1,aq+2,…,ar }.

La fusione avviene scansionando in parallelo entrambe le sequenze (ciclo principale, righe 2–8), e copiando nell’insieme di appoggio B l’elemento minore tra ai e aj.

Nel caso in cui una delle due sequenze è stata copiata completamente in B, la procedura prosegue copiando in B gli elementi rimanenti dell’altra sotto-sequenza. Infine gli elementi ordinati dell’insieme B vengono copiati nuovamente in A, ottenendo alla fine l’ordinamento di A.

Esempio

La complessità computazionale del Merge Sort è sempre O(n log2 n), a prescindere dai dati in input,  quindi ha la più bassa complessità degli algoritmi visti fino ad ora.

Gli svantaggi sono che necessita di un vettore di appoggio ed effettua spostamenti anche nel caso in cui  il vettore di partenza è già ordinato

Quick Sort

L’algoritmo Quick Sort, ideato da Charles Antony Richard Hoare nel 1960, è forse il più famoso algoritmo di ordinamento, ed ha, nel caso medio, le migliori prestazioni tra gli algoritmi basati su confronto. 

Adotta una strategia di tipo divide et impera, ossia divide il problema in tanti sotto problemi, fino a raggiungere dei sotto problemi facilmente risolvibili.

Questo approccio è conveniente solo se lo sforzo per ricomporre le soluzioni dei sotto problemi ed ottenere la soluzione del problema iniziale, è inferiore allo sforzo per risolvere il problema nella sua interezza.

In termini più tecnici abbiamo:

  1. Scelta di un elemento dell’array, detto “pivot
  2. Suddivisione del vettore in due “sub-array”
  3. Nel primo array tutti gli elementi minori o uguali al pivot, nel secondo quelli maggiori
  4. Ordinare i due sub-array separatamente, ossia applicare ricorsivamente per ognuno i passi dal 1 al 4
  5. Fondere i due sub-array ordinati insieme.

Riassumendo, abbiamo che l’ordinamento avviene mediante un algoritmo ricorsivo, che viene applicato a sotto-array sempre più piccoli, fino ad arrivare a sotto-array di pochi elementi, che possono essere risolte direttamente, senza altre chiamate ricorsive.

Codificando il tutto si ha:

Procedure Quicksort(A)
Input A, vettore a1, a2, a3 .. an
  begin
    if n ≤ 1 then return A
    else
      begin
        scegli un elemento pivot ak
        calcola il vettore A1 dagli elementi ai di A tali che i ≠ K e ai ≤ ak
        calcola il vettore A2 dagli elementi aj di A tali che j ≠ K e aj > ak
        A1 ← Quicksort(A1)
        A2 ← Quicksort(A2)
        return A1 · (ak) · A2;
      end

Esempio

Per semplicità di esposizione, è stato scelto come pivot sempre l’elemento centrale.

Rimane da specificare come scegliere il pivot.

E’ stato dimostrato che scegliendo in modo random il pivot, il Quick Sort ha una complessità media di O(n*log n) ma nel caso peggiore di O(n2).

L’ideale sarebbe però che tale risultato fosse raggiunto sempre: a ciò provvede il Merge Sort.

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  è basato sullo scambio di elementi adiacenti. Ogni coppia di elementi adiacenti viene comparata e invertita di posizione, se il primo è più grande del secondo. Quando questa operazione è stata ripetuta  per tutti gli elementi, si ha che l’elemento  più grande si trova in fondo, a destra, della sequenza considerata.

Dopodiché, si ripete questa procedura sugli elementi rimanenti, togliendo elemento più grande trovato prima.

L’algoritmo, iterando più volte  questi passaggi, fino a quando non ci saranno scambi. Allora l’array ottenuto sarà ordinato.

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 

In Java si ha:

		int[] v = { 2, 4, 7, 3, 5 };
		boolean scambiFatti= false;
		for (int i = v.length - 1; i > 0; i--) {
			for (int j = 0; j <i; j++) {
				
				if (v[j] > v[j + 1])// inverti
				{
					int tmp = v[j];
					v[j] = v[j + 1];
					v[j + 1] = tmp;
					scambiFatti = true;
				}
				
			}
			
			if(!scambiFatti) {
				break;
			}
		}

		for (int i = 0; i < v.length; i++)
			System.out.println(v[i]);

Notare che il Bubble Sort corregge il difetto principale del selection sort, ossia il non accorgersi se l’array, a un certo punto, è già ordinato.

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 ).

Selection Sort

L’algoritmo Selection Sort è quello più semplice, quello che seguirebbe istintivamente qualsiasi persona. Da un gruppo da ordinare seleziona il più piccolo, lo toglie,  e lo inserisce nella giusta posizione in un gruppo ordinato.

In termini un po’ più tecnici, l’algoritmo 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. 

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

In java diventa:

 		public void selectionSort(int [] array) {

	        for(int i = 0; i < array.length-1; i++) {
	            int minimo = i; //Partiamo dall' i-esimo elemento
	            for(int j = i+1; j < array.length; j++) {

	            //Qui avviene la selezione, ogni volta
	            //che nell' iterazione troviamo un elemento piú piccolo di minimo
	            //facciamo puntare minimo all' elemento trovato
	                    if(array[minimo]>array[j]) {
	                        minimo = j;
	                    }
	            }

	            //Se minimo e diverso dall' elemento di partenza
	            //allora avviene lo scambio
	            if(minimo!=i) { 
	                int k = array[minimo];
	                array[minimo]= array[i];
	                array[i] = k;
	            }
	        }
	    }

Esempio

Supponiamo di applicare il selection 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 selection 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. Quali delle seguenti affermazioni relative all’istruzione ‘return’ sono vere?

a) L’istruzione return viene utilizzata solo nei metodi statici.
b) L’istruzione return è obbligatoria nei metodi che non hanno void come tipo di ritorno
c) L’istruzione return si può usare in qualsiasi metodo per controllare il flusso di esecuzione.
d) L’istruzione return è obbligatoria in tutti i metodi.

 
 
 
 

2. Quali delle seguenti affermazioni relativa alle Transazioni sono vere?

a) I task contenuti in una transazione hanno priorità diverse in base all’importanza dell’operazione che effettuano.
b) Le transazioni non garantiscono la consistenza del dato in caso di crash del sistema che ospita il software
c) Una transazione è un insieme di operazioni che deve essere portata a termine nella sua interezza.
d) I dati diverranno persistenti solamente nel momento in cui tutti i task contenuti nella transazione saranno terminati.

 
 
 
 

3. 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(); 
    } 
}
 
 
 
 

4. Considerando il seguente frammento di codice:

Quale output verrà prodotto:

 

 

 

 
 
 
 

5. 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(); 
    } 
}
 
 
 
 

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

 
 
 

7. Quale sarà l’output?

class SSBool 
{
    public static void main(String [] args) 
    {
        boolean b1 = true;
        boolean b2 = false;
        boolean b3 = true;
        if ( b1 & b2 | b2 & b3 | b2 ) /* Line 8 */
            System.out.print("ok ");
        if ( b1 & b2 | b2 & b3 | b2 | b1 ) /*Line 10*/
            System.out.println("dokey");
    }
}
 
 
 
 

8. La parola chiave final, applicata ad un metodo, cosa indica?

 
 
 

9. Qual’è l’output di questo programma?

public class Test 
{
    public int aMethod()
    {
        static int i = 0;
        i++;
        return i;
    }
    public static void main(String args[])
    {
        Test test = new Test();
        test.aMethod();
        int j = test.aMethod();
        System.out.println(j);
    }
}
 
 
 
 

10. Quale codice crea e lancia correttamente un Thread

 
 
 
 

11. Quale sarà l’output

class output {
        public static void main(String args[])
        { 
           String s1 = "Hello i love java";
           String s2 = new String(s1);
           System.out.println((s1 == s2) + " " + s1.equals(s2));
        }
    }
 
 
 
 

12.

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

13. Quale sarà l’output?

public class If1 
{
    static boolean b;
    public static void main(String [] args) 
    {
        short hand = 42;
        if ( hand < 50 && !b ) /* Line 7 */
            hand++;
        if ( hand > 50 );     /* Line 9 */
        else if ( hand > 40 ) 
        {
            hand += 7;
            hand++;    
        }
        else
            --hand;
        System.out.println(hand);
    }
}
 
 
 
 

14. Quale sarà l’output?

class s1 extends Thread
{ 
    public void run() 
    { 
        for(int i = 0; i < 3; i++) 
        { 
            System.out.println("A"); 
            System.out.println("B"); 
        } 
    } 
} 
class Test120 extends Thread 
{ 
    public void run() 
    { 
        for(int i = 0; i < 3; i++) 
        { 
            System.out.println("C"); 
            System.out.println("D"); 
        } 
    } 
    public static void main(String args[]) 
        { 
        s1 t1 = new s1(); 
        Test120 t2 = new Test120(); 
        t1.start(); 
        t2.start(); 
    } 
}

 

 
 
 
 

15. Se un insieme di metodi di uno o più bean ha definiti i seguenti attributi per le transazioni:
Metodo-1 -> Supports

Metodo-2 -> Required

Metodo-3 -> NotSupported

Metodo-4 -> RequiresNew
nei diagrammi che seguono, una freccia indica che il metodo sulla sinistra chiama quello sulla destra, e tra parentesi è indicata la transazione all’interno della quale viene eseguito (‘No Tx’ indica che il metodo viene eseguito senza transazioni). Quale dei seguenti diagrammi si adatta agli attributi elencati sopra ?

 
 
 
 

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