Categoria: Algoritmo Ordinamento

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.

Leggi tutto “Merge 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.

Leggi tutto “Quick 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:

Leggi tutto “Insert 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.

Leggi tutto “Bubble 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.

Leggi tutto “Selection Sort”