RICERCA COMPLETA - SOTTOPROGRAMMA COMPLETA

i (indicatore elemento in esame)

finché i< n° elementi e non si 757b13h è trovato l'elemento da ricercare

i i+1  (passa all'elemento successivo)

fine finché

se i = numero di elementi

allora

trovato falso

altrimenti

trovato vero

pos i

fine se

PROTOTIPO:

int  completa(int num[],int n,int *numero,int *pos);

CHIAMATA AL SOTTOPROGRAMMA:

esiste=completa(num,n,&numero,&pos);

DEFINIZIONE di FUNZIONE:

int  completa(int num[],int n,int *numero,int *pos)

return trovato;

RICERCA CON SENTINELLA

rispetto al metodo della ricerca completa il numero dei confronti è dimezzato

SOTTOPROGRAMMA SENTINELLA

FUNZIONE: effettua la ricerca in un vettore non ordinato

DATI IN INGRESSO: numero di elementi del vettore, vettore, valore da cercare

DATI IN USCITA: trovato: vero se l'elemento è contenuto nel vettore, falso altrimenti

prima posizione (pos) dell'elemento da cercare se esiste

posiziona il valore da cercare come sentinella nella posizione immediatamente successiva a quella dell'ultimo elemento del vettore

i 0 (indicatore elemento in esame)

finchè non si è trovato l'elemento

i i+1 (passa all'elemento successivo)

fine finché

se i < numero di elementi

allora

trovato vero

pos i

altrimenti

trovato falso

fine se

PROTOTIPO:

int  sentinella(int num[],int n,int numero,int *pos);

CHIAMATA al SOTTOPROGRAMMA:

esiste=sentinella(num,n,numero,&pos);

DEFINIZIONE di FUNZIONE:

int  sentinella(int num[],int n,int numero,int *pos)

RICERCA SEQUENZIALE

SOTTOPROGRAMMA SEQUENZIALE

FUNZIONE: effettua la ricerca in un vettore ordinato

DATI IN INGRESSO: numero di elementi del vettore, vettore, valore da cercare

DATI IN USCITA: trovato: vero se l'elemento è contenuto nel vettore, falso altrimenti

prima posizione (pos) dell'elemento da cercare se esiste

trovato falso

i 0 (indicatore elemento in esame)

finché i < numero di elementi e non si è trovato l'elemento cercato e l'elemento corrente è del valore da cercare

se l'elemento in posizione i è l'elemento cercato

allora

trovato vero

pos i

altrimenti

i i+1 (passa all'elemento successivo)

fine se

fine finché

il codice della ricerca è presentato in due versioni

PROTOTIPO:

int  sequenziale(int num[],int n,int numero,int *pos);

CHIAMATA:

esiste=sequenziale(num,n,numero,&pos);

prima versione della ricerca sequenziale

DEFINIZIONE di FUNZIONE:

int  sequenziale1(int num[],int n,int numero,int *pos)

else

++i;

return trovato;

seconda versione della ricerca sequenziale

DEFINIZIONE di FUNZIONE:

int  sequenziale2(int num[],int n,int numero,int *pos)

return trovato;

RICERCA BINARIA

SOTTOPROGRAMMA BINARIA

FUNZIONE: effettua la ricerca in un vettore ordinato

DATI IN INGRESSO: numero di elementi del vettore, vettore, valore da cercare

DATI IN USCITA: trovato: vero se l'elemento è contenuto nel vettore, falso altrimenti

prima posizione (pos) dell'elemento da cercare se esiste

inf 0 (indicatore limite inferiore dell'array)

sup numero elementi dell'array-1 (indicatore limite superiore dell'array)

finché inf<sup

calcola la posizione centrale del rimanente segmento di array da esaminare

se il valore cercato è > del valore centrale corrente

allora

aggiorna in conseguenza il limite inferiore

altrimenti

aggiorna in conseguenza il limite superiore

fine se

fine finché

se l'elemento dell'array in posizione inf è uguale al valore cercato

allora

trovato vero

pos inf

altrimenti

trovato falso

fine se

PROTOTIPO:

int  binaria(int num[],int n,int numero,int *pos);

CHIAMATA:

esiste=binaria(num,n,numero,&pos);

DEFINIZIONE di FUNZIONE:

int  binaria(int num[],int n,int numero,int *pos)

trovato=(num[inf]==numero);

*pos=inf;

return trovato;

ORDINAMENTO PER SELEZIONE

N.B. il sort per selezione è uno dei migliori poiché riduce al minimo il numero degli scambi eseguiti.

SOTTOPROGRAMMA SELECTION

FUNZIONE: ordina l'array in modo non decrescente

DATI IN INGRESSO: numero di elementi del vettore

vettore

DATI IN USCITA: vettore ordinato

finché vi sono ancora elementi nella parte non ordinata dell'array

individua il minimo (min) e la sua posizione nella parte non ordinata dell'array

scambia il minimo (min) nella parte non ordinata dell'array con il primo elemento dell'array non ordinato

fine finché

PROTOTIPO:

void selection(int num[],int n);

CHIAMATA:

selection(num,n);

DEFINIZIONE di FUNZIONE:

void selection(int num[],int n)

num[p]=num[i];

num[i]=min;

ORDINAMENTO PER SCAMBIO O BUBBLE SORT

N.B. l'algoritmo si basa su interscambi più pesantemente della maggior parte degli altri metodi. Poiché tali scambi sono abbastanza dispendiosi in termini di tempo, questa caratteristica rende il metodo molto costoso per ordinare GROSSI insiemi di dati casuali. Se i dati hanno solo una piccola percentuale di elementi fuori posto allora questo metodo risulta efficiente.

SOTTOPROGRAMMA BUBBLESORT

FUNZIONE: ordina l'array in modo non decrescente

DATI IN INGRESSO: numero di elementi del vettore

vettore

DATI IN USCITA: vettore ordinato

finché l'array non è ancora ordinato

sorted vero

per tutte le coppie contigue di elementi nella parte di array non ancora ordinata

se la coppia corrente di elementi non è in ordine non decrescente

allora

scambia gli elementi della coppia

poni l'indicatore trovato al valore falso

fine se

fine per

fine finché

PROTOTIPO:

void bubblesort(int num[],int n);

CHIAMATA:

bubblesort(num,n);

DEFINIZIONE di FUNZIONE:

void bubblesort(int num[],int n)

ORDINAMENTO PER INSERZIONE

SOTTOPROGRAMMA INSERTION

FUNZIONE: ordina l'array in modo non decrescente

DATI IN INGRESSO: numero di elementi del vettore

vettore

DATI IN USCITA: vettore ordinato

trova il minimo e posizionalo con funzione di sentinella

finché ci sono ancora elementi da inserire nella parte ordinata

preleva il prossimo elemento (elem) da inserire

finché elem è inferiore all'elemento precedente

sposta in avanti di una posizione l'elemento precedente

estendi la ricerca all'indietro di un altro elemento ancora

fine finché

inserisci elem nella posizione corrente

fine finché

PROTOTIPO:

void insertion(int num[],int n);

CHIAMATA:

insertion(num,n);

DEFINIZIONE di FUNZIONE:

void insertion(int num[],int n)

num[p]=num[0];

num[0]=min;

for (i=2;i<n;i++)

/*inserisce elemento in modo ordinato */

num[j]=elem;

FUSIONE DI DUE VETTORI ORDINATI

STRUTTURE DATI

num1: contiene la prima sequenza da fondere. Array di massimo 10 elementi di tipo intero

num2: contiene la seconda sequenza da fondere. Array di massimo 10 elementi di tipo intero

unione: contiene la sequenza finale. Array di massimo 20 elementi di tipo intero

SOTTOPROGRAMMA MERGE

FUNZIONE: fonde due sequenze ordinate in modo non decrescente in un'unica sequenza ordinata

DATI IN INGRESSO: i due vettori (num1,num2),dimensione dei due vettori(n1,n2)

DATI IN USCITA: vettore contenente le due sequenze (unione), dimensione del vettore unione (n)

i1 (indice del primo vettore)

i2 (indice del secondo vettore)

iun (indice del vettore unione)

ripeti

se il valore corrente di num1 < del valore corrente di num2

allora

poni nella componente corrente del vettore unione il valore di num1

i1 i1+1

altrimenti

poni nella componente corrente del vettore unione il valore di num2

i2 i2+1

fine se

iun iun+1

finché uno dei due vettori non è terminato

se è terminato num1

allora

trasferisci gli elementi rimasti di num2 in unione

altrimenti

trasferisci gli elementi rimasti di num1 in unione

fine se

n n1+n2

DICHIARAZIONE STRUTTURE DATI:

#define max 10

int num1[max],num2[max],unione[2*max],

n1,  /*numero elementi del vettore num1 */

n2, /*numero elementi del vettore num2 */

n,    /*numero elementi del vettore unione */

i; /*indice del ciclo */

PROTOTIPO:

void merge(int num1[],int n1,int num2[],int n2,int unione[],int *n);

CHIAMATA:

merge(num1,n1,num2,n2,unione,&n);

DEFINIZIONE di FUNZIONE:

void merge(int num1[],int n1,int num2[],int n2,int unione[],int *n)

while (i1<n1 && i2<n2);

/*trasferisce gli elementi rimasti del vettore non terminato nel vettore unione */

if (i1==n1)

for(;i2<n2;unione[iun++]=num2[i2++]);

else

for(;i1<n1;unione[iun++]=num1[i1++]);

/*calcolo dimensione globale del vettore unione */

*n=n1+n2;