Corso di informatica Athena – Periti Informatici Algoritmi Ricerche e Ordinamenti Docente: Daniele...

Corso di informatica Athena – Periti Informatici

Algoritmi

Ricerche eOrdinamenti

Docente: Daniele Prevedello


Ripasso: Array: Insieme di dimensione

arbitrariamente grande, ma fissata, di elementi omogenei (dello stesso tipo).

int primi[5] = {1, 2, 3, 5, 7};

char str[] = "una stringa";

float* puntatori[10];



Ripasso: Accedere a un array:

primi[3] => 5

str[4] => 's'

primi[5] => ERRORE

Assegnamenti:

primi[0]=11



Algoritmi di ricercaAlgoritmi di ricerca

Un algoritmo è un metodo per la soluzione di un problema adatto a essere implementato sotto forma di programma.

Un algoritmo di ricerca è un algoritmo che permette di trovare un elemento avente determinate caratteristiche all'interno di un insieme di elementi.



Problema… Ho questo array: int prodotti[5]={5, 23, 1, 9,

52};

Come faccio a sapere se nel mio array è presente il valore 9? E il valore 13?

E se il mio array invece che avere solo 5 elementi, ne avesse 100 oppure 1000 o ancora 1000000000000000000???



Soluzione 1… Ci posso fare ben poco… Bisogna scorrere l’array (o la lista) finché

non trovo l’elemento che mi interessa (sempre che ci sia!).

RICERCA SEQUENZIALERICERCA SEQUENZIALE



In informatica la ricerca sequenziale è un algoritmo utilizzabile per trovare un elemento in un insieme non ordinato.

Il problema grosso di una struttura dati del genere e che per capire se l'elemento non c'è bisogna effettuare una scansione totale dell'array (questo da un costo lineare all'algoritmo dato che nel caso peggiore dobbiamo leggere tutti i dati).



int ricercaSequenziale(int insieme[], int x, int n) {

int i = 0;

while (i<n && x!=insieme[i]) i++;

if (i==n)

return -1;

return i;

}



Soluzione 2… Ma solo se ho un caso particolare… Poniamo ora il caso che il mio array non

sia esattamente come quello di prima, ma abbia la caratteristica di avere gli elementi ordinati (crescenti o decrescenti).

int prodotti[5]={5, 23, 1, 9, 52};int prodotti[5]={1, 5, 9, 23, 52};



RICERCA DICOTOMICA O BINARIARICERCA DICOTOMICA O BINARIA

In informatica, la ricerca dicotomica (o ricerca binaria) è un algoritmo di ricerca per individuare un determinato valore all'interno di un insieme ordinato di dati.

La ricerca dicotomica richiede un accesso casuale ai dati in cui cercare (quindi NO LISTE).



Questo algoritmo permette di trovare più rapidamente un elemento all'interno di un array ordinato.

Esso non è molto diverso dal metodo che un uomo utilizza per trovare una parola sul dizionario. Inoltre supera il limite imposto dalla ricerca sequenziale.



Sapendo che il vocabolario è ordinato alfabeticamente, l'idea è quella di cominciare la ricerca non dal primo nome, ma da quello centrale, cioè a metà del dizionario.

A questo punto si confronta l'elemento con l’oggetto della nostra ricerca. Se dobbiamo cercare un nome che sta nella seconda metà della lista, si elimina dalla ricerca in maniera automatica la prima metà (e viceversa).

La ricerca continua fino all’ultimo confronto che ci darà l'informazione richiesta, o fino a scoprire che l'elemento non si trova nel dizionario (array).



/*x è il valore da cercare!*/int ricerca_binaria(int array[], int x, int dim) {

int m, start=0, end=dim;while(start <= end) {

m= (start + end) / 2;if(x == array[m]) return m;if(x < array[m])

end = m-1;else

start = m+1;}return -1;

}



Ma se non mi piacciono gli array?

Voglio una struttura dati dinamica (come le liste) che permetta l’inserimento di un numero arbitrario di elementi, ma che al contrario delle liste, mi permetta di accedere (e cercare) un elemento nel minor tempo possibile…



Soluzione: alberi binari di ricerca:

Ora sai che esistono, ma non li vedremo a lezione!



Algoritmi di ordinamentoAlgoritmi di ordinamento

Un algoritmo di ordinamento è un algoritmo che viene utilizzato per elencare gli elementi di un insieme secondo una sequenza stabilita da una relazione d'ordine, in modo che ogni elemento sia minore (o maggiore) di quello che lo segue.



Quanti ne esistono? Avl sort, Bubble sort, B sort, B-Tree sort,

Bitonic sort, Btm sort, Bucket sort, Comb sort, Counting sort, Gnome sort, Heap sort, Insertion sort, Integer sort, Intro sort, Jump sort, Merge sort, Ms sort, Oet sort, Partition sort, Plasel sort, Quicksort, Radix sort, Ripple sort, Selection sort, Several unique sort, Shaker sort, Shear sort, Simple sort, Shell sort, Smooth sort, Stupid sort, Sunrise sort, Trippel sort



Bubble sort Il bubble sort (letteralmente: ordinamento a

bolle) è un semplice algoritmo di ordinamento per ordinare array.

Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine in un bicchiere di champagne. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente.



Non è un algoritmo efficiente: ha una complessità computazionale dell'ordine di O(n2) confronti, con n numero degli elementi da ordinare.

Si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità.



Il bubblesort è un algoritmo iterativo, ovvero basato sulla ripetizione di un procedimento fondamentale.

La singola iterazione dell'algoritmo prevede che gli elementi dell'array siano confrontati a due a due, procedendo in un verso stabilito.



void bubbleSort(int numbers[], int array_size) {int i, j, temp;for (i = (array_size - 1); i >= 0; i--) {

for (j = 1; j <= i; j++) {if (numbers[j-1] > numbers[j]) {

temp = numbers[j-1];numbers[j-1] = numbers[j];numbers[j] = temp;

}}

}}



Quicksort Quicksort è un ottimo algoritmo di

ordinamento ricorsivo che si basa sul paradigma divide et impera.

La base del suo funzionamento è l'utilizzo ricorsivo della procedura partition: preso un elemento da una struttura dati (es. array) si pongono gli elementi minori a sinistra rispetto a questo e gli elementi maggiori a destra.



Divide et impera: dal latino «dividi e domina» viene talvolta tradotto in italiano anche come dividi e conquista.

In politica e sociologia si utilizza per definire una strategia finalizzata al mantenimento di un territorio e/o di una popolazione, dividendo e frammentando il potere dell'opposizione in modo che non possa riunirsi contro un obiettivo comune.



In informatica il divide et impera rappresenta un approccio molto potente per la risoluzione di vari problemi computazionali.

Gli algoritmi divide et impera dividono ricorsivamente un problema in due o più sotto-problemi sino a che questi ultimi diventino di semplice risoluzione, quindi, si combinano le soluzioni al fine di ottenere la soluzione del problema dato.



Il Quicksort, termine che tradotto letteralmente in italiano indica ordinamento rapido, è l'algoritmo di ordinamento che ha, in generale, prestazioni migliori tra quelli basati su confronto.

Per effettuare l'ordinamento di N elementi richiede mediamente solo nlog n operazioni.



void quicksort(int array[], int left, int right) {

int i;

if (right <= left)

return;

i=partition(array, left, right);

quicksort(array, left, i-1);

quicksort(array, i+1, right);

}



int partition(int array[], int left, int right) {int i=left-1, j=right;int v = array[right];for(;;) {

while(array[++i] < v);while(v < array[--j])

if(j == left) break;if(i >= j) break;swap(&(array[i]),

&(array[j]));}swap(&(array[i]), &(array[right])); return i;

}Docente: Daniele Prevedello


void swap(int* v1, int* v2) {

int temp = *v1;

*v1 = *v2;

*v2 = temp;

}



Compito:

IMPARARE A MEMORIA GLI IMPARARE A MEMORIA GLI ALGORITMI DI RICERCA E ALGORITMI DI RICERCA E

ORDINAMENTO!ORDINAMENTO!


Corso di informatica Athena – Periti Informatici Algoritmi Ricerche e Ordinamenti Docente: Daniele...

Documents

Transcript of Corso di informatica Athena – Periti Informatici Algoritmi Ricerche e Ordinamenti Docente: Daniele...