8 Algoritmi

INFORMATICA

Algoritmi fondamentali

2 © Piero Demichelis

Riordinamento di un vettore

• Il problema del riordinamento di un vettore è frequente e talvolta condiziona addirittura le prestazioni di un programma.

• La prima idea che viene in mente è quella di ricostruire il vettore in un altro vettore inserendo i dati uno dopo l’altro nell’ordine richiesto (ascendente o discendente).

• Generalmente però i vettori sono così grandi da non poter essere “duplicati” in memoria: il riordinamento dunque deve essere effettuato all’interno del vettore stesso senza ausilio di altre strutture dati.


Riordinamento di un vettore

• Il problema di trovare un algoritmo efficiente dipende dal fatto che il numero di confronti che devono essere eseguiti tra gli elementi del vettore può essere così grande da rendere il programma inefficiente.

• Una prima idea per risolvere il problema potrebbe essere quella di cercare il massimo (o il minimo) dell’intero vettore, portarlo in prima posizione scambiandolo con l’elemento che attualmente la occupa, poi ripetere l’operazione considerando tutti gli elementi tranne il primo, e così via fino alla penultina posizione.

• Questo algoritmo è noto col nome di selection sort .


Riordinamento di un vettore: esempio

• Realizzare un programma che legge da tastiera una sequenza di 10 numeri interi e li salva in un vettore. Successivamente li riordina dal più piccolo al più grande senza uso di altre strutture dati, e infine li visualizza.

• Analisi:

dopo aver letto i 10 valori da tastiera (mediante un semplice ciclo for) dobbiamo trovare un algoritmo che ci permetta di riorganizzare il nostro vettore scambiando di posizione i vari elementi in modo da riordinarli;


Riordinamento con selection sort

• Utilizziamo come algoritmo di riordinamento quello che abbiamo appena enunciato e noto col nome di selection sort.

• Pseudocodice:

Sia n il numero di elementi del vettore vett; con un indice i che va da 0 a n-1: /* definisce il vettore dentro cui

cercare il minimo (inizia da i e finisce a n) */• inizializza min col valore di vett[i];• inizializza ind = i;• con un indice j che va da i+1 a n: /* cerca il minimo del vettore

*/ se vett[j] < min: /* se l’elemento attuale è < del minimo

*/· min = vett[j]; /* lo salva come nuovo minimo */· ind = j; /* memorizza l’indice in cui si trova */

• scambia l’elemento di indice i con l’elemento di indice j.



#include <stdio.h>#include <conio.h>

#define lmax 10

/* Funzione riordina: riordina un vettore di interi lungo n */

void riordina (int vett[ ], int n) /* prototipo della funzione */

main(){ int vett [lmax], ind;

clrscr();



printf ("Introduci i valori\n");

for (ind=0; ind<lmax; ind++) /* legge gli elementi del vettore */ { printf ("\nElemento di indice %d: ", ind); scanf ("%d", &vett[ind]); }

riordina (vett, lmax); /* riordina il vettore */

printf ("\n Vettore riordinato \n"); /* visualizza il vettore riordinato */

for (ind = 0; ind < lmax; ind++) printf ("%d\n", vett[ind]);}



void riordina (int vett[ ], int n) /* funzione di riordino */{ int min, ind, i, j; for (i = 0; i < n-1; i++) /* definisce il vettore in cui cercare il min. */ { min = vett[i]; /* inizializzazioni per ogni nuovo “sottovettore” */ ind = i; for (j = i + 1; j < n; j++) /* cerca il minimo del “sottovettore” */

if (vett[j] < min) { min = vett[j]; ind = j; }

vett[ind] = vett[i]; /* scambia il primo elemento del “sottovettore” */

vett[i] = min; /* con l’elemento minimo appena trovato */ }}


Riordinamento con bubble sort

• L’algoritmo di riordinamento più interessante è però quello noto col nome di bubble sort. Si può dimostrare che questo è l’algoritmo di riordinamento che mediamente usa il minor numero di confronti fra gli elementi del vettore.

• Pseudocodice:

Sia n il numero di elementi del vettore vett; inizializza una variabile logica (inordine) a FALSO; finché non ho finito (ovvero inordine è FALSO):

• ipotizza che vett sia ordinato (inordine = VERO)• con un indice i che va dal primo al penultimo elemento:

confronto: se vett[i] > vett[i+1] :· scambia i due elementi tra loro;· assegna a inordine il valore FALSO (fatto uno

scambio).



#include <stdio.h>

#define NELEM 10

#define FALSO 0#define VERO 1 /* Funzione bubble: riordina un vettore di interi lungo n */

void bubble (int vett[ ], int n); /* prototipo */



main( ){int vett [NELEM], ind;printf ("Introduci i valori\n");for (ind = 0; ind < NELEM; ind++) { /* riempie il vettore con nelem numeri interi */ printf ("\nElemento di indice %d: ", ind); scanf ("%d", &vett[ind]); }

bubble (vett, NELEM); /* riordina il vettore */

printf ("\n Vettore riordinato \n"); /* visualizza il vettore riordinato */

for (ind = 0; ind < NELEM; ind++) printf ("%d\n", vett[ind]);}



void bubble (int vett[ ], int n){int provv, i, inordine;inordine = FALSO; /* inizializza inordine a FALSO */while (!inordine) /* Finché il vettore non è ordinato */ { inordine = VERO; /* ipotizza che sia ordinato, cioè di aver finito */ for (i = 0; i < (n - 1); i++) /* i va dal primo al penultimo elem. */ if (vett[i] > vett[i+1]) /* se quello che segue è più piccolo */ { provv = vett[i]; /* scambia i due elementi tra loro */ vett[i] = vett[i+1]; vett[i+1] = provv; inordine = FALSO; /* è stato fatto uno scambio! */ } }}


Riordinamento alfabetico

• Realizzare un programma che legge da tastiera una sequenza di nomi (10), li riordina in ordine alfabetico mediante l'algoritmo di bubble-sort e infine li visualizza.

• Analisi:

il problema è identico al precedente ma occorre considerare il fatto che i nomi sono delle stringhe;

bisogna pertanto modificare la funzione bubble nella definizione, quando esegue il confronto fra i due elementi del vettore e quando scambia fra di loro gli elementi.



#include <stdio.h>

#define NELEM 10#define LUNGMAX 50#define FALSO 0#define VERO 1 /* Funzione bubble: riordina un vettore di stringhe lungo n */

void bubble (char vett[ ][LUNGMAX], int n) /* prototipo */



main( ){char parole [NELEM][LUNGMAX];int ind;

printf ("Introduci le parole\n");for (ind = 0; ind < NELEM; ind++) { /* Riempie il vettore con NELEM parole

*/ printf ("\nParola di indice %d: ", ind); scanf ("%s", parole[ind]); }bubble (parole, NELEM); /* Riordina il vettore */printf ("\n Vettore riordinato \n"); /* Visualizza il vettore

riordinato */for (ind = 0; ind < ind; ind++) printf ("%s\n", parole[ind]);}



void bubble(char vett[ ][LUNGMAX], int n){int i, inordine; char provv[LUNGMAX];inordine = FALSO; /* inizializza inordine a FALSO */while (!inordine) /* Finché il vettore non è ordinato */ { inordine = VERO; /* ipotizza che sia ordinato, cioè di aver finito */ for (i = 0; i < (n - 1); i++) /* i va dal primo al penultimo elem. */ if (strcmp (vett[i], vett[i+1]) > 0) /* se quello che segue è > */ { strcpy (provv, vett[i]); /* scambia i due elementi tra loro */ strcpy (vett[i], vett[i+1]); strcpy (vett[i+1], provv); inordine = FALSO; } /* è stato fatto uno scambio! */ }}


Ricerca dicotomica

• La ricerca di un elemento in un vettore può essere molto laboriosa in termini di tempo di esecuzione.

• Se la base dati è molto grande è opportuno minimizzare questo tempo riducendo il numero di confronti tramite un semplice algoritmo detto di ricerca dicotomica.

• Il vettore deve essere dapprima riordinato, poi si confronta l’elemento posto a metà vettore (indice = n/2) con l’elemento cercato. Si hanno 3 possibilità: a) é quello cercato; b) l’elemento cercato è più grande; c) l’elemento cercato è più piccolo.

• Se l’elemento cercato è più grande si considera un nuovo vettore formato dalla sola seconda metà dell’intero vettore e si ricomincia la ricerca col confronto tra elemento cercato e elemento posto a metà del nuovo vettore; e così via.


Ricerca dicotomica

#include <stdio.h>#include <conio.h>

#define MAX_DATI 20#define FALSE 0#define VERO 1 /* prototipo delle funzioni di ricerca e di riordinamento */int trovato (int vett[ ], int elemento, int *p_posiz, int n_dati);void bubble (int vett[ ], int n);

main(){int num_dati, dato, indice, p_posiz, cercato;int vett [MAX_DATI];

clrscr();


Ricerca dicotomica

for ( indice=0, indice < MAX_DATI, indice++) { printf ("Introduci vett[%d]: " ,indice); scanf ("%d",&vett[indice]) }

bubble (vett, MAX_DATI); /* riordina il vettore di interi */

printf (“\nVettore riordinato:”); /* visualizza il vettore riordinato */

for (indice = 0; indice < MAX_DATI; indice++) printf (“\nElemento di indice %d = %d”, indice, vett

[indice]);


Ricerca dicotomica

/* richiede il dato da cercare */printf ("\nQuale dato vuoi cercare? ");scanf ("%d", &cercato);

/* cerca il dato con la funzione trovato che restituisce col suo nome un valore logico (vero o falso) a seconda che il dato sia presente o meno nel vettore e, se presente, l’indice del dato nella variabile p_posiz */

if ( trovato (vett, cercato, &p_posiz, MAX_DATI) ) printf ("\nDato presente in posizione %d", p_posiz);

else printf ("\nDato non presente");

}


Ricerca dicotomica

int trovato (int vett[ ], int dato, int *p_posiz, int n_dati){int meta, limite_inf, limite_sup;int presente;

limite_inf = 0; /* indice inferiore della porzione di vettore */

limite_sup = n_dati - 1; /* indice superiore della porzione di vettore */

presente = FALSE;while ((!presente) && (limite_inf <= limite_sup))

{ meta = (limite_sup + limite_inf) / 2;

/* confronto il dato cercato con l’elemento di metà del vettore */

if (vett[meta] == dato) presente = TRUE; /* è lui, finito! */


Ricerca dicotomica

else {/* non è lui, procedo usando il metodo di bisezione

*/ if (vett[meta] > dato) limite_sup = meta - 1;

else limite_inf = meta + 1;

}}

if (presente) *p_posiz = meta; return (presente);}



void bubble (int vett[ ], int n){ int provv, i, inordine;inordine = FALSE; /* inizializza inordine a FALSE */while (!inordine) /* Finché il vettore non è ordinato */ { inordine = TRUE; /* ipotizza che sia ordinato, cioè di aver finito */ for (i = 0; i < (n - 1); i++) /* i va dal primo al penultimo elem. */ if (vett[i] > vett[i+1]) /* se quello che segue è più grande */ { provv = vett[i]; /* scambia i due elementi tra loro */ vett[i] = vett[i+1]; vett[i+1] = provv; inordine = FALSE; /* è stato fatto uno scambio! */ } }}

8 Algoritmi

Documents

Transcript of 8 Algoritmi