Algoritmi di ordinamento

Che cos'è un algoritmo di ordinamento?

Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue. In assenza di altre specifiche, la relazione d'ordine viene sempre considerata totale (cioè tale da rendere sempre possibile il confronto tra due elementi dell'insieme): le relazioni d'ordine parziale danno origine agli algoritmi di ordinamento topologico. A seconda del verso della relazione considerato, un ordinamento può essere ascendente o discendente.

Quanti diversi tipi di ordinamento esistono?

Selection sort

Ordinamento per selezione

Questo algoritmo ordina una sequenza di elementi eseguendo vari passaggi. Inizialmente va a trovare l'elemento minore e lo porta nella posizione iniziale della sequenza, e l'elemento in posizione iniziale nella posizione occupata dal valore minore.

Quindi sulla sotto-sequenza non ordinata effettua la stessa operazione fino a che rimane un solo elemento (che è ordinato)

L'algoritmo quindi andrà ad operare su una sequenza non ordinata come se fosse composta di due sotto-sequenze: la prima ordinata e la seconda non-ordinata, andando a cercare il valore minimo nella sequenza non-ordinata e portandolo nell'ultima posizione della sequenza ordinata.L'ordinamento sarà terminato quando la sotto sequenza non ordinata sarà composta da un solo elemento (l'elemento maggiore)

Selection Sort in Java

Usiamo due indici i e j: j scorre su tutto l'array, mentre i scorre sulla parte dell'array non ordinata.

All'inizio si assume che la posizione dell'elemento minore è 0 e dalla posizione 1 fino alla fine si cerca il valore minimo. Se questo è più piccolo dell'elemento nella posizione 0 viene scambiato.

Quindi incrementiamo l'indice j (che identifica la prima posizione della parte non ordinata) e si esegue nuovamente la ricerca del minimo nella sotto-sequenza rimanente.

Alla fine l'elemento che rimarrà nell'ultima posizione dell'array (v [v.length-1]) è il valore maggiore.

Bubble sort

Ordinamento per scambio

Questo algoritmo ordina una sequenza di elementi andando a confrontare gli elementi a coppie e scambiandoli di posto se il secondo è minore del primo.

L'algoritmo termina quando dopo aver scandito tutta la sequenza senza che non sia stato effettuato alcuno scambio. In questo caso la sequenza risulta già ordinata.

Dopo la prima scansione ne seguono altre. L'algoritmo risulta ordinato quando nell'ultima scansione non verranno effettuati scambi

Bubble sort in Java

Gli algoritmi di ordinamento selection sort e bubble sort sono algoritmi abbastanza semplici, ma non sono i più efficienti.

Altri ordinamenti sono più complessi ma più efficienti perchè effettuano un numero minore di scansioni degli elementi di una sequenza

Marge 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 provvede alla loro fusione ordinandole.Il vettore viene diviso in due meta', se e' formato da un numero pari di elementi la prima parte ha un elemento in piu'. Si ordinano le parti separatamente e per unirle l'algoritmo estrae il minimo dalle due parti e li fonde in un'unica sequenza.

Insertion sort

L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice per ordinare un array. Esso è un algoritmo in place, cioè ordina l'array senza doverne creare un altro “di appoggio”, quindi risparmia memoria.

Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo di carte. L'algoritmo utilizza due indici: il primo punta inizialmente al secondo elemento dell'array, il secondo inizia dal primo. Se il primo elemento è maggiore del secondo, i due valori vengono scambiati. Poi il primo indice avanza di una posizione e il secondo indice riparte dall'elemento precedente quello puntato dal primo. Se l'elemento puntato dal secondo indice non è maggiore di quello a cui punta il primo indice, il secondo indice indietreggia; e così fa, finché si trova nel punto in cui il valore del primo indice deve essere inserito (da qui insertion). L'algoritmo così tende a spostare man mano gli elementi maggiori verso destra.

QUick sort

Quicksort è un algoritmo di ordinamento ricorsivo in place che, come merge sort, si basa sul paradigma divide et impera. La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.

Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto.

Possiamo concludere dicendo che esistono molti altri tipi di ordinamento come per esempio heap sort; shaker sort; ecc..

Metodi di Ricerca

In generale una sequenza di elementi si può realizzare come un array. E la scansione avviene usando un indice. „ Se la sequenza non è ordinata a priori occorre eseguire una ricerca lineare o sequenziale. „ Se la sequenza è ordinata è opportuno eseguire una ricerca binaria

Ricerca lineare

L’algoritmo di ricerca lineare (o sequenziale) in una sequenza (array) è basato sulla seguente strategia: „ Gli elementi dell’array vengono analizzati in sequenza, confrontandoli con l’elemento da ricercare (chiave) per determinare se almeno uno degli elementi è uguale alla chiave. „ Quando si trova un elemento uguale alla chiave la ricerca termina. „ La ricerca è sequenziale, nel senso che gli elementi dell’array vengono scanditi uno dopo l’altro sequenzialmente. „ L’algoritmo prevede che al più tutti gli elementi dell’array vengano confrontati con la chiave. Se l’elemento viene trovato prima di raggiungere la fine della sequenza non sarà necessario proseguire la ricerca. L’algoritmo di ricerca lineare può essere usato per verificare quante volte un elemento è presente in una sequenza: 1. Gli elementi dell’array vengono analizzati in sequenza, confrontandoli con l’elemento da ricercare (chiave) per determinare se uno degli elementi è uguale alla chiave. 2. Quando si trova un elemento uguale alla chiave si incrementa un contatore e il passo 1 viene rieseguito fino alla fine della sequenza.

Ricerca binaria

L’algoritmo di ricerca lineare richiede che al più tutti gli elementi dell’array vengano confrontati con la chiave. Questo è necessario perché la sequenza non è ordinata. „ Se la sequenza su cui occorre effettuare la ricerca è ordinata si può usare un algoritmo di ricerca molto più efficiente che cerca la chiave sfruttando il fatto che gli elementi della sequenza sono già disposti in un dato ordine. „ Esempi di sequenze ordinate: elenco telefonico, agenda, etc. „ In questi casi si usa un algoritmo di ricerca binaria che è più efficiente perché riduce lo spazio di ricerca.

L’algoritmo di ricerca binaria cerca un elemento in una sequenza ordinata in maniera crescente (o non decrescente) eseguendo i passi seguenti finché l’elemento viene trovato o si è si è completata la ricerca senza trovarlo: 1. Confronta la chiave con l’elemento centrale della sequenza, 2. Se la chiave è uguale all’elemento centrale, allora la ricerca termina positivamente, 3. Se invece la chiave è maggiore dell’elemento centrale si effettua la ricerca solo sulla sottosequenza a destra, 4. Se invece la chiave è minore dell’elemento centrale dello spazio di ricerca, si effettua la ricerca solo sulla sottosequenza a sinistra

Valeria Iervolino

Comment Stream