LabASD - Insertion Sort

Nicolas Farabegoli nicolas.farabegoli2@unibo.it

Moreno Marzolla moreno.marzolla@unibo.it

Ultimo aggiornamento: 2021-03-11

Implementare l'algoritmo Insertion sort in modo tale che i test forniti vengano superati. L'algoritmo deve ordinare l'array di input in senso crescente.

Insertion sort opera iterativamente: ad ogni passo l'array v[0..n-1] è composto da una parte iniziale wordinata v[0..i-1], e dal resto non ordinato. Durante la sua esecuzione, l'algoritmo mantiene la seguente invariante:

v[0..i-1] è ordinato

Per espandere di un elemento la parte ordinata, cioè per rendere ordinato v[0..i], occorre inserire v[i] nella posizione corretta di v[0..i-1] mediante scambi "a ritroso". Si faccia riferimento alla Figura 1 per un esempio.

Figura 1: Esempio Insertion Sort
Figura 1: Esempio Insertion Sort

Il programma fornito contiene alcuni test per verificare la parziale correttezza della funzione insertion_sort(). Nei test si confronta il risultato con quello prodotto dalla funzione qsort() della libreria standard C. La segnatura di qsort() è:

#include <stdlib.h>

void qsort(void *base, size_t nmemb, size_t size,
           int (*compare)(const void *, const void *));

dove:

Per approfondire

Questo programma misura in modo grossolano il tempo necessario a ordinare l'array. Considerando array di dimensioni sufficientemente grandi (es., 100000 elementi o più), come varia il tempo di esecuzione nei seguenti casi?

Per farsi un'idea, si può procedere come segue:

Per eseguire le prove occorre modificare opportunamente la funzione main() per generare input opportuni. Nel caso possano risultare utili, vengono fornite due funzioni randab() e random_shuffle(), la cui specifica è indicata nei commenti al codice.

File