DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Esercizi Hash e sort ======

(sono quelli specificati a lezione e presenti sui lucidi)

===== Esercizio 1: Chi è più veloce ? =====

Scrivere una funzione 
<code>
int* random_array(int n)
</code> 
che restituisce un array contenente ''n'' elementi casuali (va allocato sullo heap!! altrimenti viene deallocato!)

Utilizzare la funzione per scrivere due programmi C distinti che creano un array e lo ordinano  con //selection sort//, oppure //quicksort//.

Osservare le differenze di performance tra i due algoritmi al crescere di n (e.g., n > 1000000) misurando il tempo necessario all'ordinamento

===== Esercizio 2: Ordinato è meglio ? =====

Dato un array di interi ordinato, come posso verificare se contiene un intero x?
Devo davvero leggere ogni valore, o esiste un modo più veloce?

===== Esercizio 3: Hash o non Hash ?=====

Scrivere un programma che legga da tastiera una sequenza di ''n'' interi NON distinti e li inserisca (senza duplicati) in una tabella hash di dimensione $m=2n$ utilizzando liste di trabocco per risolvere conflitti. 
Utilizzare la funzione hash $h(x) = ((ax + b) \% p)\%m$ dove $p$ è il numero primo $999149$ e $a$ e $b$ sono interi positivi minori di 10.000 scelti casualmente. 

Una volta inseriti tutti gli interi, stampare 
  -  gli elementi nella tabella
  -  il numero totale di conflitti, 
  -  la lunghezza massima delle liste e 
  -  il numero di elementi distinti nella tabella.

Provare lo stesso con funzione hash $h(x) = x\%m$ e osservare se c’è differenza nella performance.