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:

#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;
}

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