Algoritmi di ricerca

1) Cosa si intende per ricerca dicotomica di un elemento in un vettore ordinato:

È un tipo di ricerca che richiede un vettore ordinato, essa itera sin quando l´estremo inferiore del vettore è maggiore della estremo superiore, il passo della iterazione è invece la aggiornamento di uno dei 2 estremi sulla base del valore della elemento intermedio M, se M è maggiore del valore ricercato allora M-1 diventa il nuovo estremo superiore, altrimenti se M è minore della elemento ricercato allora M+1 diventa il nuovo estremo inferiore.

 

Algoritmi di ordinamento

 

2) Descrivere la algoritmo di ordinamento di un vettore per selezione (SELECTIONSORT) :

Si itera dal 1° elemento del vettore sino all´ultimo, ed il passo iterativo consiste nella sostituzione della elemento in questione con un altro elemento del vettore che sia minore.

 

3) Descrivere la algoritmo di ordinamento a bolle di un vettore (BUBBLESORT) :

Sono necessari ( n_elementi - 1 ) passi ricorsivi in ognuno dei quali si scandisce il vettore rimanente facendo scambi tra celle adiacenti in modo da portare verso la alto l´elemento minore. Al termine si ottiene il vettore ordinato.

 

4) Descrivere la algoritmo di ordinamento di un vettore per fusione (MERGESORT) :

Si divide il vettore in segmenti contenenti gruppi di dati ordinati in maniera crescente e si smistano alternativamente questi segmenti su 2 supporti di memorizzazione( Files o Vettori ) dopodiché si efettua la fusione dei valori contenuti nei 2 supporti a coppie di 2 segmenti alla volta. Eseguendo più volte questo passo si ottiene il vettore ordinato.

 

5) Descrivere la algoritmo di ordinamento veloce di un vettore (QUICKSORT) :

Si sceglie un elemento appartenente alla array e si divide la array in 2 parti, una contenente gli elementi inferiori al pivot ed un´altra parte contenente gli elementi superiori al pivot dopodiché si esegue lo stesso ordinamento su ognuno dei 2 sottoinsiemi creati sin quando non si ottiene il vettore ordinato.

 

6) Algoritmo per la scrittura di un algoritmo ;

a) Farsi un´idea chiara di quello che è il problema, analizzandolo prima completamente e poi scendendo nel dettaglio.

b) Scrivere la algoritmo in linguaggio naturale, tale descrizione diverrà il commento della algoritmo

c) Sostituire al linguaggio naturale delle procedure o laddove possibile delle istruzioni Pascal

d) Per ogni procedura ritornare al punto 2