Algoritmi di Ricerca e Ordinamento

Ordinamento

Moltissime volte potrà capitare che si abbia l’esigenza di ordinare una lista di oggetti in Java.  Per ordinamento (SORT) di un qualsiasi insieme di dati s’intende la tecnica che dispone un gruppo di elementi secondo un certo criterio, stabilito in base agli elementi da trattare.

Esistono molti algoritmi di ordinamento. Tutti ricevono in input una sequenza non ordinata di elementi e restituiscono la sequenza ordinata.

Algoritmi di ordinamento:

  • selection sort
  • insertion sort
  • bubble sort
  • merge sort

SELECTION SORT

L' algoritmo selection sort è un algoritmo di ordinamento. In genere viene utilizzato per ordinare in maniera crescente o decrescente un vettore di numeri o parole.

Prendiamo in esempio il seguente vettore contenente i valori :52,34,47,97 e 77

L'algoritmo opera nel seguente modo:

Prende il primo elemento (o meglio l'i-esimo elemento) e lo confronta con tutti gli altri elementi del vettore (i j-esimi elementi).

Ad ogni confronto se l'i-esimo elemento è maggiore o minore, in base alla condizione che mettiamo, del j-esimo elemento, i due elementi vengono scambiati.

Una volta confrontati tutti gli elementi del vettore con il primo, al i-esimo posto si trova l'elemento con valore minore.

Quindi viene incrementato l'indice i e l'i-esimo elemento, adesso il secondo elemento del vettore, viene confrontato con i successivi elementi.

Il vettore, come abbiamo gia detto, si può ordinare in modo crescente o decrescente, basta modificare la condizione. Quando vogliamo ordinarlo in maniera crescente mettiamo v[i]>v[j], mentre usiamo v[i]<v[j] quando vogliamo ordinarlo in maniera decrescente.

INSERTION SORT

L’algoritmo di Insertion Sort è una delle varie strategie di ordinamento; simula la comune modalità umana di ordinare una serie di oggetti.

Il suo meccanismo si basa nell’ordinare gli elementi partendo dall’elemento 1 del vettore (uno dei valori da ordinare) effettuando i confronti con i valori degli elementi a sinistra, terminato tale confronto si prosegue con gli altri elementi a destra del vettore confrontandoli con quelli alla loro sinistra.

BUBBLE SORT

Il bubble sort è un algoritmo di ordinamento che come il selection sort viene utilizzato per ordinare un vettore di numeri o parole, ma a differenza di quest'ultimo può essere ottimizzato. Abbiamo trattato il bubble sort già in passato, alleghiamo il link della spiegazione (BubbleSort).

MERGE SORT

Il Merge sort e' un algoritmo di ordinamento ricorsivo. Alla base di questo metodo c'e' il procedimento Divide et Impera, che consiste nella divisione di un problema in problemi via via più piccoli. Il merge sort opera quindi dividendo l'insieme da ordinare in 2 meta'. Una volta ottenute le meta' si provede alla loro fusione ordinandole.
Procedimento:

Il vettore viene diviso in due metà, se è formato da un numero pari di elementi la prima parte ha un elemento in più. Si ordinano le parti separatamente e per unirle l'algoritmo estrae il minimo dalle due parti e li fonde in un'unica sequenza.

Supponiamo di avere un array:

dividiamo l'array in 2 meta' e ripetiamo il processo ricorsivamente fino ad ottenere coppie di 2 elementi:

ordiniamo le coppie ottenute:

e fondiamo in un unico vettore estraendo dagli array ordinati:

Ricerca

La "ricerca" deve la propria importanza alla necessità di verificare l'esistenza di determinati elementi (detti chiavi) all'interno di un insieme, o di estrarre tali elementi dall'insieme stesso.
I tipi di ricerca presentati sono due:

  • Ricerca esaustiva, ovvero la ricerca elemento per elemento, fino a trovare quello voluto.
  • Ricerca binaria, ovvero la ricerca più veloce.

Ricerca esaustiva
La ricerca esaustiva è il tipo di ricerca più banale. In pratica, dato un insieme di elementi sul quale sia possibile definire un ordinamento, si scandiscono tutti gli elementi fino a trovare quello cercato, oppure fino alla fine dell'insieme. Nel primo caso, l'algoritmo restituisce il valore "vero", per indicare che l'elemento e' stato trovato. Nel secondo caso, invece, l'algoritmo restituisce il valore booleano "falso", per indicare che l'elemento non e' stato trovato.

Ricerca binaria
Un criterio di ricerca notevole e' la ricerca binaria.
Dato un insieme di elementi ordinato, in modo crescente, l'algoritmo prende l'elemento centrale e lo confronta con la chiave. Se la chiave è maggiore, allora si ripete lo stesso passo sulla meta' superiore degli elementi. Se invece la chiave e' minore, allora si passa alla metà inferiore. Il tutto procede finche' non si arriva ad avere un solo elemento che può essere o meno quello cercato. Se l'elemento è quello voluto, allora l'algoritmo restituisce il valore booleano "vero". Altrimenti, il valore booleano restituito è "falso".

Comment Stream