Strumenti Utente

Strumenti Sito


fisica:informatica:201819:esercitazioni:esercitazione11l

Esercizi Hash e sort

(sono quelli specificati a lezione e presenti sui lucidi)

Esercizio 1: Chi è più veloce ?

Scrivere una funzione

int* random_array(int n)

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

  1. gli elementi nella tabella
  2. il numero totale di conflitti,
  3. la lunghezza massima delle liste e
  4. il numero di elementi distinti nella tabella.

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

fisica/informatica/201819/esercitazioni/esercitazione11l.txt · Ultima modifica: 20/03/2019 alle 11:05 (21 mesi fa) da Alessio Conte