Guida Gli ordinamenti in Java [2017]

[xXxsimo]

Salve a tutti ! Quest'oggi ho intenzione di cominciare la prima di una lunga serie (o almeno si spera) di guide relative al linguaggio di programmazione JAVA.

Questa guida è per UTENTI SEMI-AVANZATI, quindi se non hai nessuna conoscenza del linguaggio trattato ti sconsiglio di leggerla o di tentare di capirne qualcosa.
Piuttosto comincia con l'aprire i libri e comincia a studiare da 0, qui non parleremo delle basi.

In breve, Cos'è Java ?

• Java è una tecnologia utilizzata per lo sviluppo di applicazioni che rendono il Web più divertente e utile. Java è diverso da JavaScript in quanto quest'ultimo è una semplice tecnologia utilizzata per la creazione di pagine Web e viene eseguita solo nel browser.
• Java consente di giocare, caricare foto, chattare in linea, eseguire presentazioni virtuali e utilizzare servizi, ad esempio formazione in linea, home banking e mappe interattive. Se non si dispone di Java, molte applicazioni e siti Web non funzionano.

In poche parole:
In informatica Java è un linguaggio di programmazione ad alto livello, orientato agli oggetti e a tipizzazione statica, specificatamente progettato per essere il più possibile indipendente dalla piattaforma di esecuzione.


Detto questo, cominciamo con la prima guida:

ARRAY E I LORO ORDINAMENTI
​

In breve, sappiamo che un array è un insieme di elementi disposti in delle "celle".
Pensiamo ad esempio ad un array di interi:

​

Come potrete notare dal primo all'ultimo blocco di celle i numeri vengono ORDINATI. E' proprio questo quello che faremo in questa guida. Vedere e scoprire i metodi (A livello di codice e pseudocodice) con i quali possiamo ordinare elementi in JAVA. Ovviamente ricorda che gli array di interi non sono l'unica cosa che può essere ordinata, ma di questo ne parleremo in caso più avanti.


Quindi, ecco le tipologie più conosciute di ordinamenti:


BUBBLE SORT

Spoiler: DEFINIZIONE

Tra i piú semplici algoritmi di ordinamento abbiamo il Bubble Sort, che in italiano significa naturalmente ordinamento a bolle, e già il nome dovrebbe dirci tutto, almeno.
Il meccanismo si basa infatti sull 'idea di far emergere man mano (come bollicine) gli elementi minori all' inizio del vettore mentre contemporaneamente quelli maggiori si posizionano in fondo al vettore.

Spoiler: RAPPRESENTAZIONE GRAFICA

Spoiler: PSEUDOCODICE

Iterativo:

Perfavore, Entra oppure Registrati per vedere i codici!

Ricorsivo:

Perfavore, Entra oppure Registrati per vedere i codici!

Ecco l' implementazione in java dell' algoritmo :

Perfavore, Entra oppure Registrati per vedere i codici!

SELECTION SORT

Spoiler: DEFINIZIONE

Il Selection Sort è un altro algoritmo di ordinamento decisamente semplice ed intuitivo. L' idea di base si fonda nel selezionare ad ogni iterazione l' i-esimo valore piú piccolo, e sostituirlo con quello che in quel momento occupa l' i-esimaposizione.

Spoiler: RAPPRESENTAZIONE GRAFICA

Spoiler: PSEUDOCODICE

Perfavore, Entra oppure Registrati per vedere i codici!

Implementazione del codice Java:

Perfavore, Entra oppure Registrati per vedere i codici!

INSERTION SORT

Spoiler: DEFINIZIONE

L' Insertion Sort é un' altro noto e semplice algoritmo di ordinamento che si basa sul concetto di ordinamento per inserzione, simile al modo in cui un essere umano, spesso, ordina un mazzo di carte.

Spoiler: RAPPRESENTAZIONE GRAFICA

Spoiler: PSEUDOCODICE

Iterativo:

Perfavore, Entra oppure Registrati per vedere i codici!

Ricorsivo:

Perfavore, Entra oppure Registrati per vedere i codici!

Implementazione codice Java:

Perfavore, Entra oppure Registrati per vedere i codici!

MERGE SORT (Il più complicato da comprendere)

In questo caso spezziamo la descrizione e il codice in quanto è da affrontare prima capendo e poi programmando.

Spoiler: SPIEGAZIONE MERGE SORT

Il Merge Sort (ordinamento per fusione) a differenza degli algoritmi visti in precedenza, é un algoritmo di ordinamento piú complesso, ma molto efficiente, infatti come vedremo ha una complessitá computazionale bassa.

Il meccanismo di ordinamento di questo algoritmo fa uso della tecnica Divide et Impera. Di questa tecnica ci sarebbe molto da dire, purtroppo ció esula dallo scopo di questa guida. Diciamo brevemente che é una tecnica che consiste nel suddividere ricorsivamente un problema complesso in due o piú sotto-problemi piú semplici e poi si ricombinano le soluzioni trovate per ricostruire la soluzione del problema complessivo.

Vediamo nei dettagli il meccanismo di ordinamento del Merge Sort : il metodo riceve un vettore con n elementi, se n ha una dimensione accettabile (che fissiamo a 20) viene ordinato con l 'Insertion Sort (scegliamo questo algoritmo poiché per piccole dimensioni di n ha buone prestazioni), altrimenti si scompone (Divide) il vettore in due parti uguali (se la dimensione é dispari la prima metà contiene un elemento in più) e su ogni meta del vettore viene richiamato ricorsivamente il metodo. Alla fine dell' invocazione dei due metodi le due sottoparti ordinate vengono fuse (Impera) con il metodo merge in un unico vettore ordinato.

Spoiler: RAPPRESENTAZIONE GRAFICA

Spoiler: PSEUDOCODICE

Perfavore, Entra oppure Registrati per vedere i codici!

Passiamo ora al codice:

Perfavore, Entra oppure Registrati per vedere i codici!

QUICK SORT

Spoiler: SPIEGAZIONE MERGE SORT

Il Quicksort è un algoritmo ricorsivo di ordinamento in place non stabile. Appartiene alla classe degli algoritmi divide et impera (che abbiamo già visto in altri ordinamenti sopra citati), dal momento che scompone ricorsivamente i dati da processare in sottoprocessi. Tale procedura ricorsiva viene comunemente detta partition: preso un elemento chiamato "pivot" da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto al pivot e gli elementi maggiori a destra. L'operazione viene quindi reiterata sui due insiemi risultanti fino al completo ordinamento della struttura.

Spoiler: RAPPRESENTAZIONE GRAFICA

Spoiler: PSEUDOCODICE

Perfavore, Entra oppure Registrati per vedere i codici!

Passiamo ora al codice:

Perfavore, Entra oppure Registrati per vedere i codici!

Per oggi è tutto, spero di essere stato chiaro e preciso. Ci si vede in una prossima guida !

SE QUALCOSA NON E' CHIARO FAMMI PURE UNA DOMANDA NEI COMMENTI O LASCIA UNA VALUTAZIONE. E SE TI VA, RISPONDI AL SONDAGGIO IN CIMA ALLA GUIDA. GRAZIE !

Spoiler: INFORMAZIONI GUIDA

Guida numero: 01
Prodotta da: xXxsimo
Codice: Java
Guida adatta a: Programmatori non alle primissime armi
Titolo: Array e come ordinarli
Difficoltà lezione: 7/10

 

[UNI▼ERS▲L]

Complimentoni ottima guida chiara esaustiva e coincisa! Grazie per aver condiviso

 

[xXxsimo]

Grazie mille, figurati. Al piú presto scriveró nuove guide

 

[Dvdxseo]

Ora, avrei qualche dubbio sulle prima cose su Java che hai scritto, forse era così nel 2008, o al limite nei siti fatti vecchi o fatti male. :P

A parte questo, trovo che la guida sia scritta abbastanza bene. Nel codice noto che utilizzi spesso il for come un while… capisco che sia più bello, più conciso, più quello che si vuole, ma spesso anche leggendo il codice si dovrebbe poter capire quali sono le intenzioni, e quindi direi che un while in alcuni casi sarebbe più appropriato! Così come gli indici i2 e i3 che tradizionalmente si preferirebbe chiamarli j, k, z o comunque altre lettere, sennò quando diventano tanti si rischia di impazzire! La decisione di utilizzare Insertion Sort quando Merge Sort ha pochi elementi da ordinare è giusta e lo sappiamo, sarebbe bello aggiungere una spiegazione un pochino più approfondita di questo. E invece i poveri Quick Sort e Heap Sort dove sono rimasti? :P

Per concludere direi che con qualche aggiustamento potremmo anche mettere la discussione in rilievo!

 

[Scanetatore]

Direi che si può anche migliorare.
C'è un'introduzione al linguaggio Java in una guida che si prefigge di essere indirizzata (principalmente) per utenti avanzati. Direi di lasciar perdere, anche perché il fatto che Java sia l'unica alternativa per fare "molte applicazioni Web" è anche errata.

Il codice è molto semplicistico, quindi a questo punto non era meglio utilizzare dello pseudocodice direttamente?
Ad esempio, vengono trattati gli array di soli interi (che a questo punto possiamo ordinare anche in tempo lineare) mentre il problema dell'ordinamento a cui questi algoritmi fanno riferimento è più generale.
Dovremmo passare quindi strutture di tipo generico da ordinare.

E a questo punto un minimo di informazioni sulle informazioni sulla complessità algoritmica sul tempo (medio e peggiore), spazio e stabilità direi che è necessaria se uno volesse scegliere in base alle sue necessità.
Sempre rimanendo sul fatto che Java implementa l'ordinamento meglio di chiunque lo implementi da sé durante l'apprendimento stesso.

Il codice, come diceva Dvdxseo, non è proprio elegantissimo. Ad esempio l'utilizzo di più espressioni su una sola riga diminuisce la leggibilità e porta facilmente a bug quando ci devi mettere le mani (chiaramente se fa parte di un progetto più grande).

Spero che siano venute fuori critiche costruttive. ;)

 

[xXxsimo]

Ora, avrei qualche dubbio sulle prima cose su Java che hai scritto, forse era così nel 2008, o al limite nei siti fatti vecchi o fatti male. :P

A parte questo, trovo che la guida sia scritta abbastanza bene. Nel codice noto che utilizzi spesso il for come un while… capisco che sia più bello, più conciso, più quello che si vuole, ma spesso anche leggendo il codice si dovrebbe poter capire quali sono le intenzioni, e quindi direi che un while in alcuni casi sarebbe più appropriato! Così come gli indici i2 e i3 che tradizionalmente si preferirebbe chiamarli j, k, z o comunque altre lettere, sennò quando diventano tanti si rischia di impazzire! La decisione di utilizzare Insertion Sort quando Merge Sort ha pochi elementi da ordinare è giusta e lo sappiamo, sarebbe bello aggiungere una spiegazione un pochino più approfondita di questo. E invece i poveri Quick Sort e Heap Sort dove sono rimasti? :P

Per concludere direi che con qualche aggiustamento potremmo anche mettere la discussione in rilievo!

Si, è vero, ti do ragione per le variabili. In ogni caso aggiungerò altri tipi di ordinamenti. Per ora ho inserito i più comuni, utilizzati e conosciuti. Effettuerò in questi giorni dei miglioramenti per rendere la guida più completa e meglio strutturata. Grazie mille !

 

[xXxsimo]

Direi che si può anche migliorare.
C'è un'introduzione al linguaggio Java in una guida che si prefigge di essere indirizzata (principalmente) per utenti avanzati. Direi di lasciar perdere, anche perché il fatto che Java sia l'unica alternativa per fare "molte applicazioni Web" è anche errata.

Il codice è molto semplicistico, quindi a questo punto non era meglio utilizzare dello pseudocodice direttamente?
Ad esempio, vengono trattati gli array di soli interi (che a questo punto possiamo ordinare anche in tempo lineare) mentre il problema dell'ordinamento a cui questi algoritmi fanno riferimento è più generale.
Dovremmo passare quindi strutture di tipo generico da ordinare.

E a questo punto un minimo di informazioni sulle informazioni sulla complessità algoritmica sul tempo (medio e peggiore), spazio e stabilità direi che è necessaria se uno volesse scegliere in base alle sue necessità.
Sempre rimanendo sul fatto che Java implementa l'ordinamento meglio di chiunque lo implementi da sé durante l'apprendimento stesso.

Il codice, come diceva Dvdxseo, non è proprio elegantissimo. Ad esempio l'utilizzo di più espressioni su una sola riga diminuisce la leggibilità e porta facilmente a bug quando ci devi mettere le mani (chiaramente se fa parte di un progetto più grande).

Spero che siano venute fuori critiche costruttive. ;)

Ottimo, grazie mille per le critiche / consigli. Il più presto possibile effettuerò delle modifiche sia nei codici che nella guida stessa. Vi terrò aggiornati

 

[xXxsimo]

AGGIORNAMENTO: Ho inserito per ogni ordinamento una rappresentazione grafica e pseudocodice. Ho migliorato le descrizioni e modificato alcuni frammenti di codice. (Non ho cambiato i nomi delle variabili di tipo i1,i2 ecc... perché comunque le ritengo comunque comprensibili in questo caso). Ho inoltre inserito il QUICK SORT (come richiesto) ma non l'Heap sort in quanto non penso faccia parte degli algoritmi di ordinamento base. Se ci sono altre richieste, consigli o domande sarò felice di modificare la guida o rispondere ad eventuali dubbi.
Scanetatore Dvdxseo UNI▼ERS▲L

 

[Mr_Joker]

Ti sei dimenticato Bongo Sort.

 

[xXxsimo]

Ti sei dimenticato Bongo Sort.

Volevi dire "Bogo sort" ? Se si non l'ho incluso in quanto non fa parte degli algoritmi di ordinamento base.

Inviato dal mio SM-G935F utilizzando Tapatalk

 

[Mr_Joker]

Volevi dire "Bogo sort" ? Se si non l'ho incluso in quanto non fa parte degli algoritmi di ordinamento base.

Inviato dal mio SM-G935F utilizzando Tapatalk

Si "Bogo". Naturalmente era un fail..