ALGORITMO
Un algoritmo è un procedimento che risolve un determinato problema
attraverso un numero finito di passi.
Un formalismo che permette di rappresentare gli algoritmi è il
diagramma di flusso.
Esempio:
Problema del trasporto della capra, del lupo e del cavolo da una sponda ad un'altra del
fiume
1 Porta la capra sull'altra sponda
2 Torna indietro
3 Porta il cavolo sull'altra sponda
4 Porta la capra indietro
5 Porta il lupo sull'altra sponda
6 Torna indietro
7 Porta la capra sull'altra sponda
Proprietà di un algoritmo
È finito
 È definito e preciso
 Fornisce un risultato
 È eseguibile
 Risolve i problemi

Algoritmo 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
(ES. ordina dal maggiore al minore)
una relazione d'ordine o ordine su di un insieme è una relazione binaria tra
elementi appartenenti all'insieme
è un elenco di coppie ordinate di elementi appartenenti all'insieme
I diversi algoritmi di ordinamento
Esistono tre “grandi gruppi” di algoritmi di ordinamento:

ITERATIVI

RICORSIVI

I CASI PARTICOLARI
Suddivisi a loro volta in tre tipi diversi:
ITERATIVI
• insertion sort
• selection sort
• bubble sort
CASI PARTICOLARI
• counting sort
• radix sort
• bin sort
RICORSIVI
• merge sort
• quicksort
• heap sort
Iterativi
Un algoritmo iterativo è una tipologia di algoritmo costituito da una
sequenza di azioni che viene ripetuta, finché è necessaria la ripetizione stessa
(un ciclo). Ad ogni iterazione, l'esecutore svolge un compito. Al termine verifica
se tale compito vada ripetuto mediante una condizione di ripetizione.
Per spiegare meglio il concetto di
algoritmo iterativo, si consideri il lavoro di
un addetto ad una catena di montaggio:
egli deve eseguire le stesse azioni
ripetutamente finché ci sono pezzi
da assemblare.
L'algoritmo iterativo della catena di
montaggio può essere così descritto:
1.Preleva i componenti
2.Assembla i componenti
3.Passa i componenti al
collega
4.Se ci sono altri componenti
da assemblare, torna al
punto 1
#include<stdio.h>
Int main() {
Int a, i;
a= 10;
For(i=0; i < a; i++;)
Printf(“ %d”, i);
Return 0;
System(“PAUSE”)
}
Algoritmo che
stampa i numeri
da 0 a 9,
attraverso un
ciclo “for”
Insertion sort
L'Insertion sort, in italiano ordinamento a inserimento, è un algoritmo relativamente semplice
per ordinare un array. Non è molto diverso dal modo in cui un essere umano, spesso, ordina un mazzo
di carte. L'algoritmo utilizza due indici: uno punta all'elemento da ordinare e l'altro all'elemento
immediatamente precedente. Se l'elemento puntato dal secondo indice è maggiore di quello a cui punta
il primo indice, i due elementi vengono scambiati di posto; altrimenti il primo indice avanza. Il
procedimento è ripetuto finché si trova nel punto in cui il valore del primo indice deve essere inserito.
Es.
void InsertionSort(int x[], int n) {
int i, j, app;
for (i = 1; i < n; i++) {
app = x[i];
for (j = i - 1;(j >= 0) && (x[j] > app); j--)
x[j+1] = x[j];
x[j + 1] = app;
}
}
Selection sort
Anche l'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in
place ed in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza
di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti:
I passaggi sono
• si inizializza un puntatore i che va da 1 a n (dove n è la lunghezza dell'array).
• Si cerca il più piccolo elemento dell'array
• Scambia l'elemento più piccolo con l'elemento alla posizione i
• Incrementa l'indice i e si torna al passo uno fino alla fine dell'array
Es.
void selection(double a[], unsigned long N) {
int i, j, min;
double t;
for (i=0; i < N-1; i++) {
for (j= 0; j < N; j++)
if (a[j] < a[j+1]) {
t = a[j+1];
a[j+1] = a[i];
a[i] = t;
}
}
}
Bubble sort
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. Per esempio, saranno confrontati il primo e il secondo
elemento, poi il secondo e il terzo, poi il terzo e il quarto, e così via fino al confronto fra penultimo e
ultimo elemento. Per ogni confronto, se i due elementi confrontati non sono ordinati, essi vengono
scambiati. Durante ogni iterazione, almeno un valore viene spostato rapidamente fino a raggiungere la
sua collocazione definitiva.
Es.
void BubbleSort(int *array, int elemN) {
int i, tmp, ultimo;
int alto=elemN; /* elemN è il numero degli elementi del vettore da ordinare */
while (alto >= 0) { /* in questo modo si evita 1 passaggio*/
ultimo = -1;
for (i=0; i<alto; i++) {
if (array[i]>array[i+1]) { /* sostituire ">" con "<" per avere un ordinamento decrescente */
tmp = array[i];
array[i] = array[i+1];
array[i+1] = tmp;
ultimo = i;
}}
alto = ultimo;
}}
Ricorsivi
Una funzione ricorsiva è una funzione che richiama sé stessa (ricorsione diretta) o richiama una funzione che
a sua volta la richiama (ricorsione indiretta). Affinché il procedimento abbia fine è necessario che siano
verificate le due seguenti proprietà:
• Debbono esistere dei parametri (valori base) per cui la funzione non richiami sé stessa
• Ogni volta che la funzione richiama sé stessa i parametri devono essere più vicini ai valori base
Es.
/* Fattoriale di un numero */
#include <stdio.h>
int calcFatt(int numero); /*1*/
main() {
int n,fat;
printf("\nCalcola il fattoriale di un numero");
printf("\n\nIntrodurre il numero ");
scanf("%d",&n); fat=calcFatt(n); /*2*/
printf("\n Fattoriale di %d = %d",n,fat);
}
/* Calcola Fattoriale utilizzando la Ricorsione*/
int calcFatt(int numero) {
int f;
if (!numero) /*3*/
f=1;
else
f=numero*calcFatt(numero-1); /*4*/
return f;
}
Quicksort
Quicksort è un ottimo algoritmo di ordinamento ricorsivo in place 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 si pongono gli elementi minori a sinistra rispetto a questo
e gli elementi maggiori a destra.
Es.
void sort(int array[], int begin, int end) {
int pivot, l, r;
if (end > begin) {
pivot = array[begin];
l = begin + 1;
r = end+1;
while(l < r)
if (array[l] < pivot)
l++;
else {
r--;
swap(array[l], array[r]); }
l--;
swap(array[begin], array[l]);
sort(array, begin, l);
sort(array, r, end);
}
}
Merge sort
Il merge sort è un algoritmo di ordinamento basato su confronti che utilizza un processo di
risoluzione ricorsivo, sfruttando la tecnica del Divide et Impera, che consiste nella suddivisione del
problema in sottoproblemi della stessa natura di dimensione via via più piccola. Concettualmente,
l'algoritmo funziona nel seguente modo:
 Se la sequenza da ordinare ha lunghezza 0 oppure 1, è già ordinata. Altrimenti:
 La sequenza viene divisa (divide) in due metà (se la sequenza contiene un numero dispari di
elementi, viene divisa in due sottosequenze di cui la prima ha un elemento in più della seconda)
 Ognuna di queste sottosequenze viene ordinata, applicando ricorsivamente l'algoritmo(impera)
 Le due sottosequenze ordinate vengono fuse (combina).
1’ caso particolare counting sort
Il Counting sort è un algoritmo di ordinamento per valori numerici interi con complessità
lineare. L'algoritmo si basa sulla conoscenza a priori dell'intervallo in cui sono compresi i valori da
ordinare. L'algoritmo conta il numero di occorrenze di ciascun valore presente nell'array da
ordinare, memorizzando questa informazione in un array temporaneo di dimensione pari
all'intervallo di valori. Il numero di ripetizioni dei valori inferiori indica la posizione del valore
immediatamente successivo.
// counting.h
#ifndef COUNTING_H
#define COUNTING_H
void counting_sort(int* A, int Alen, int* B, int k);
#endif
// counting.c
#include "counting.h"
#include <stdio.h>
void counting_sort(int* A, int Alen, int* B, int k){
int i;
int C[k];
for(i=0; i<k; i++)
C[i] = 0;
int j;
for(j=0; j<Alen; j++)
C[A[j]] = C[A[j]]+1;
for(i=1; i<k; i++)
C[i] = C[i]+C[i-1];
for (j=Alen-1; j>=0; j--){
B[C[A[j]]-1] = A[j];
C[A[j]] = C[A[j]]-1;
}
}
2’ caso particolare Radix sort
Radix sort utilizza un procedimento contro intuitivo per l'uomo, ma più facilmente
implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno
significativa. Questo affinché l'algoritmo non si trovi a dovere operare ricorsivamente su
sottoproblemi di dimensione non valutabili a priori.
Es.
void RadixSort(int[] a) {
int[] t=new int[a.Length];
int r=4;
int int b=32;
int[] count=new int[1<<r];
int[] pref=new int[1<<r];
int groups=(int)Math.Ceiling((double)b/(double)r);
int mask = (1<<r)-1;
for (int c=0, shift=0; c<groups; c++, shift+=r) {
for (int j=0; j<count.Length; j++)
count[j]=0;
for (int i=0; i<a.Length; i++)
count[(a[i]>>shift)&mask]++;
pref[0]=0;
for (int i=1; i<count.Length; i++)
pref[i]=pref[i-1]+count[i-1];
for (int i=0; i<a.Length; i++) t[pref[(a[i]>>shift)&mask]++]=a[i];
t.CopyTo(a,0);
}}
FINE
Presentazione di Bonacorsi Giulio
Fonti:
• Wikipedia