Lezione 12

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

 

Lascia un commento