Algoritmi di Ordinamento cenni introduttivi:
- Bubble Sort, Shell Sort.
- Selection Sort: for all i, si seleziona il minimo in [i,N) e lo si mette in v[i]
- Insertion Sort: for all i, si estrae (la carta/il valore) v[i] e lo si mette nella sua corretta posizione nel sottovettore v[0..i-1] spostando verso destra fin quando necessario.
Implementazone in C:
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define N 100
void insertion_sort(int v[N], int size)
{
for (int i=1; i<size; i++)
{
int t = v[i];
int j = i-1;
while (j>=0 && v[j] > t) { v[j+1] = v[j]; j–; }
v[j+1] = t;
}
}
void vprint(int v[N], int size)
{
for (int i=0; i<size; i++) {
printf("%2d ",v[i]);
if ((i+1) % 20 == 0)
printf("\n");
}
}
int main(void)
{
int v[N];
for (int i=0; i<N; i++)
v[i] = rand() % 30 + 1;
vprint(v,N);
insertion_sort(v,N);
printf("——————–\n");
vprint(v,N);
return 0;
}
[/cpp]
Ricorsione:
- Funzioni Ricorsive, regole di visibilità
- Funzioni Ricorsive come sostituto all’iterazione (Turing Equivalenza)
- Ricorsione e Iterazione infinita: necessità del caso base.
- Alcuni esempi: fattoriale, fibonacci, mcd, potenza
Esercizi: scrivere tutte le funzioni sopra in modo ricorsivo.
- Ordinamento Ricorsivo: merge / mergesort