C# - Algoritmi di ordinamento
C#
Note
- Nei paragrafi seguenti sono descritti alcuni algoritmi di ordinamento.
- Non sono presenti algoritmi 'lenti', quali il Selection Sort e il Bubble Sort.
- Per gli algoritmi esposti è riportato il metodo C# di ordinamento. Il suo utilizzo è molto semplice: basta richiamare il metodo con le poche righe di codice seguenti:
int[] dati = new int[] { 45, 9, 81, 27, 18, 90, 63, 36, 54, 72 };
InsertionSort(dati); // Oppure un altro metodo.
for (int i = 0; i < dati.Length; i++)
{
Console.WriteLine(dati[i].ToString());
}
- È necessario di volta in volta, sostituire il metodo con quello dell'algoritmo che si vuole utilizzare.
Insertion Sort
- L’algoritmo “Insertion Sort” è un algoritmo di ordinamento molto comune. È per esempio utilizzato dai giocatori di carte quando ordinano una mano nei giochi con più di dieci carte (Scala 40, Ramino, ecc.).
- Brevemente, si considera una carta per volta e la si inserisce nella posizione corretta tra le carte già considerate. Per esempio, si abbiano 10 carte da ordinare. Si comincia considerando la 2° carta e la si confronta con la 1°: se necessario si effettua lo scambio. Si procede considerando la 3° carta e la si confronta con la 2° ed eventualmente con la 1°; se necessario viene inserita nella posizione corretta spostando le carte con valore superiore. Si procede considerando la 4° carta e la si confronta con la 3° carta ed eventualmente con la 2° e la 1° carta; se necessario viene inserita nella posizione corretta spostando le carte con valore superiore. Si procede così fino all’ultima carta che viene confrontata con le altre carte di valore inferiore fino a trovarne la posizione corretta.
- Esempio, ordinare la sequenza:
45 9 81 27 18 90 63 36 54 72 - Si indica con le parentesi quadre, la parte della sequenza certamente in ordine. Inizialmente si considera il primo elemento già ordinato.
- Si indica in grassetto, quell’elemento che viene considerato nel passo dell’algoritmo.
[45] 9 81 27 18 90 63 36 54 72 - Si considera il 9 e lo si confronta con il 45; si inserisce il 9 prima del 45.
[9 45] 81 27 18 90 63 36 54 72 - Si considera l’81 e lo confronta con il 45; non si fanno inserzioni.
[9 45 81] 27 18 90 63 36 54 72 - Si considera il 27 e lo si confronta con l’81, con il 45 e con 9; si inserisce il 27 dopo il 9.
[9 27 45 81] 18 90 63 36 54 72 - Si considera il 18 e lo si confronta con l’81, con il 45, con il 27 e con 9; si inserisce il 18 dopo il 9.
[9 18 27 45 81] 90 63 36 54 72 - Si considera il 90 e lo si confronta con l’81; si inserisce il 90 dopo l’81.
[9 18 27 45 81 90] 63 36 54 72 - Si considera il 63 e lo si confronta con il 90, con l’81; si inserisce il 63 dopo il 45.
[9 18 27 45 63 81 90] 36 54 72 - Si considera il 36 e lo si confronta con il 90, con l’81, con il 63, con il 45 e con il 27; si inserisce il 36 dopo il 27.
[9 18 27 36 45 63 81 90] 54 72 - Si considera il 54 e lo si confronta con il 90, con l’81, con il 63 e con il 45; si inserisce il 54 dopo il 45.
[9 18 27 36 45 54 63 81 90] 72 - Si considera il 72 e lo si confronta con il 90, con l’81 e con il 63; si inserisce il 72 dopo il 63.
[9 18 27 36 45 54 63 72 81 90] - A questo punto la sequenza è ordinata.
- Il metodo seguente, accetta in input un array di integer, esegue l’ordinamento sull’array stesso che viene restituito al chiamante.
private void InsertionSort(int[] dati)
{
for (int i = 1; i < dati.Length; i++)
{
// Gli elementi con indice da 0 a i-1 sono ordinati.
// Si inserisce l'elemento di indice i.
int k = dati[i]; // Elemento da inserire.
int j = i - 1;
while (j >= 0 && dati[j] > k)
{
dati[j + 1] = dati[j];
j--;
}
// Si inserisce k nella posizione j+1, solo se è cambiata.
if (j + 1 != i)
{
dati[j + 1] = k;
}
}
}
Shell Sort
- L’algoritmo “Shell Sort” è un algoritmo di ordinamento molto efficiente. È un miglioramento dell’algoritmo “Insertion Sort”, dove i confronti non avvengono tra elementi adiacenti ma tra elementi con una distanza che inizia “grande” e via via diminuisce fino a distanza unitaria.
- Questo algoritmo consente quindi di spostare elementi fuori posto in modo più veloce, facendogli fare salti più grandi. Le distanze che vengono utilizzate, sono diverse in base all’implementazione dell’algoritmo. Una buona sequenza è quella di Knutt, dove si prendono in considerazione i passi 1, 4, 13, 40, … (ogni elemento è il triplo del precedente più uno), applicati in ordine inverso, dal più grande al più piccolo.
- Esempio, ordinare la sequenza:
45 9 81 27 18 90 63 36 54 72 - Le distanze da considerare sono 4 e 1 (La distanza successiva, 13, non si considera perché si hanno solo 10 elementi da ordinare).
- Si considera ora come distanza tra gli elementi: 4.
- Si applica un Insert Sort ai sotto-array indicati di volta in grassetto.
45 9 81 27 18 90 63 36 54 72 (ordinare 45 e 18)
18 9 81 27 45 90 63 36 54 72 (nessun ordinamento)
18 9 81 27 45 90 63 36 54 72 (ordinare 81 e 63)
18 9 63 27 45 90 81 36 54 72 (nessun ordinamento)
18 9 63 27 45 90 81 36 54 72 (nessun ordinamento)
18 9 63 27 45 90 81 36 54 72 (ordinare 9, 90, 72)
18 9 63 27 45 72 81 36 54 90 - Si considera ora come distanza tra gli elementi: 1.
18 9 63 27 45 72 81 36 54 90 (ordinare 18 e 9)
9 18 63 27 45 72 81 36 54 90 (nessun ordinamento)
9 18 63 27 45 72 81 36 54 90 (inserire il 27 nel sotto-array)
9 18 27 63 45 72 81 36 54 90 (inserire il 45 nel sotto-array)
9 18 27 45 63 72 81 36 54 90 (nessun ordinamento)
9 18 27 45 63 72 81 36 54 90 (nessun ordinamento)
9 18 27 45 63 72 81 36 54 90 (inserire il 36 nel sotto-array)
9 18 27 36 45 63 72 81 54 90 (inserire il 54 nel sotto-array)
9 18 27 36 45 54 63 72 81 90 (nessun ordinamento)
- Il metodo seguente, accetta in input un array di integer, esegue l’ordinamento sull’array stesso che viene restituito al chiamante.
private void ShellSort(int[] dati)
{
int h; // Passo.
// Calcolo del passo iniziale.
h = 1;
while (h <= dati.Length)
h = 3 * h + 1;
h = h / 3;
while (h >= 1)
{
// Questo è l'Insertion Sort con passo 'h'.
for (int i = h; i < dati.Length; i++)
{
for (int j = i; j >= h && dati[j] < dati[j - h]; j -= h)
{
// Eventuale scambio degli elementi.
int temp = dati[j];
dati[j] = dati[j - h];
dati[j - h] = temp;
}
}
// Prossimo passo.
h = h / 3;
}
}
Merge Sort
- L’algoritmo “Merge Sort” è un algoritmo di ordinamento ricorsivo molto efficiente. Il termine 'merge' in inglese significa 'fusione', quindi l'idea è quella di fondere assieme le due metà dell'array già ordinate separatamente.
- L'ordinamento di un array di n elementi viene quindi fatto con un merge tra due array di n/2 elementi ordinati. I due array da n/2 elementi vengono ottenuti con un merge di due array da n/4 elementi ordinati e così via. Ad un certo punto i sotto-array avranno lunghezza 2 (e anche lunghezza 1 se il numero di elementi non è una potenza di 2). Nel caso abbiano lunghezza 2, l'ordinamento è fatto scambiando gli elementi.
- Esempio, ordinare la sequenza:
45 9 81 27 18 90 63 36 54 72 - Sono presenti 10 elementi, per cui si divide l'array in due array da 5 elementi:
45 9 81 27 18 - 90 63 36 54 72 - Alla seconda ricorsione, si dividono i due array nei quattro array seguenti:
45 9 81 - 27 18 - 90 63 36 - 54 72 - Alla terza ricorsione, si dividono i quattro array in otto array, alcuni dei quali sono impropri (con solo un elemento):
45 9 - 81 - 27 - 18 - 90 63 - 36 - 54 - 72. - Si eseguono gli ordinamenti dove necessario, negli array di lunghezza 2, semplicemente scambiando gli elementi.
9 45 - 81 - 27 - 18 - 63 90 - 36 - 54 - 72. - Si fa il merge degli array della terza ricorsione:
9 45 81 - 18 27 - 36 63 90 - 54 72 - Si fa il merge degli array della seconda ricorsione:
9 18 27 45 81 - 36 54 63 72 90 - Si fa il merge della prima ricorsione:
9 18 27 36 45 54 63 72 81 90.
- C'è bisogno di una funzione che esegua il merge tra due sotto-array.
- Dato infatti l'array di dati, ad un certo punto occorre una funzione che faccia il merge tra una parte dell'array ed un'altra parte dell'array.
- Sia dati[] l'array da ordinare, i due sotto-array occupano posizioni consecutive:
- Il primo sotto-array dalla posizione a, alla posizione b.
- Il secondo sotto-array dalla posizione b+1, alla posizione c.
- Ecco la funzione di merge.
private void Merge(int[] dati, int a, int b, int c)
{
int i = a;
int j = b + 1;
int k = 0;
if (a >= 0 && a <= b && b <= c && c <= dati.Length)
{
// Array dove fare temporaneamente il merge.
int[] temp = new int[c - a + 1];
while (i <= b && j <= c)
{
// Questa è la parte principale dove si sceglie quale elemento prendere.
if (dati[i] < dati[j])
temp[k++] = dati[i++];
else
temp[k++] = dati[j++];
}
// Gli elementi residui vanno ricopiati.
if (i <= b)
while (i <= b)
temp[k++] = dati[i++];
else
while (j <= c)
temp[k++] = dati[j++];
// L'array temporaneo va ora copiato nell'array dati.
temp.CopyTo(dati, a);
}
}
- Questo è l'algoritmo Merge Sort.
- Il primo overload serve solo per poter chiamare il metodo senza argomenti e fa il MergeSort per tutti gli elementi dell'array.
private void MergeSort(int[] dati)
{
MergeSort(dati, 0, dati.Length - 1);
}
private void MergeSort(int[] dati, int a, int c)
{
if (a < c)
{
// Indice dell'elemento a metà.
int b = (a + c) / 2;
// Chiama ricorsivamente se stessa, con la prima metà degli elementi.
MergeSort(dati, a, b);
// Chiama ricorsivamente se stessa, con la seconda metà degli elementi.
MergeSort(dati, b + 1, c);
// Fa il merge delle due metà.
Merge(dati, a, b, c);
}
}
Quick Sort
- L’algoritmo “Quick Sort” è un algoritmo di ordinamento ricorsivo molto efficiente. Il termine 'quick' in inglese significa 'veloce'.
- L'idea dei questo algoritmo sta nello scegliere un elemento detto 'pivot', poi si fanno scorrere due indici rispettivamente da destra verso sinistra e vicevera. Il primo indice scorre finché il relativo elemento è inferiore al pivot, il secondo finché il relativo elemento è maggiore del pivot. Quando i due indici si fermano, i relativi elementi vengono scambiati. Una volta effettuato lo scambio, gli indici proseguono e se necessario vengono effettuati altri scambi. Questa fase dell'algoritmo termina quando i due indici si sovrappongono. Si sono così divisi gli elementi dell'array in due parti: quelli a sinistra sono tutti inferiori al pivot, quelli a destra sono tutti superiori al pivot.
- Si procede quindi ricorsivamente ordinando le due metà dell'array finché il sotto-array è di un solo elemento.
- Esempio, ordinare la sequenza:
45 9 81 27 18 90 63 36 54 72 - Quick Sort di [45 9 81 27 18 90 63 36 54 72], Pivot 18.
- Scambio 45 con 18:18 9 81 27 45 90 63 36 54 72
- Quick Sort di [18 9], Pivot 18.
- Scambio 18 con 9:
9 18 81 27 45 90 63 36 54 72 - Quick Sort di [81 27 45 90 63 36 54 72], Pivot 90.
- Scambio 90 con 72:
9 18 81 27 45 72 63 36 54 90 - Quick Sort di [81 27 45 72 63 36 54], Pivot 72.
- Scambio 81 con 54:
9 18 54 27 45 72 63 36 81 90 - Scambio 72 con 36:
9 18 54 27 45 36 63 72 81 90 - Quick Sort di [54 27 45 36 63], Pivot 45.
- Scambio 54 con 36:
9 18 36 27 45 54 63 72 81 90 - Scambio 45 45:
9 18 36 27 45 54 63 72 81 90
- Quick Sort di [36 27], Pivot 36.
- Scambio 36 27:
9 18 27 36 45 54 63 72 81 90
- Quick Sort di [54 63], Pivot 54.
- Scambio 54 con 54:
9 18 27 36 45 54 63 72 81 90
- Quick Sort di [72 81], Pivot 72.
- Scambio 72 72:
9 18 27 36 45 54 63 72 81 90
- Questo è l'algoritmo Quick Sort.
- Il primo overload serve solo per poter chiamare il metodo senza argomenti e fa il QuickSort per tutti gli elementi dell'array.
private void QuickSort(int[] dati)
{
QuickSort(dati, 0, dati.Length - 1);
}
private void QuickSort(int[] dati, int a, int b)
{
int i = a;
int j = b;
int p = dati[(a + b) / 2]; // Pivot.
while (i <= j)
{
// Scorrimento da sinistra dell'indice i.
while (dati[i] < p)
i++;
// Scorrimento da destra dell'indice j.
while (dati[j] > p)
j--;
// Scambio degli elementi (se non si sono incrociati gli indici i e j).
if (i <= j)
{
int temp = dati[i];
dati[i] = dati[j];
dati[j] = temp;
i++;
j--;
}
}
// Chiamate ricorsive sui sotto-array.
if (a < j)
QuickSort(dati, a, j);
if (i < b)
QuickSort(dati, i, b);
}