Articoli con tag confronti

Algoritmo di ordinamento HeapSort, implementazione in C.

1
2 anni fa
Scritto da Rocco Musolino in

L’HeapSort è un algoritmo di ordinamento basato sui confronti, molto efficente. Complessità computazionale al più O(nlog_2n), al pari di QuickSort e MergeSort.

L’algoritmo si compone di 3 funzioni essenzialmente:
- La prima Rendi_heap, riceve in ingresso: l’array a[], la sua dimensione n, un certo valore lh (lunghezza heap) ed un indice i (che è l’indice da cui vogliamo partire per rendere tale nodo un heap).
- La seconda Costruisci_heap, che si occupa di richiamare sulla prima metà di array la funzione rendi_heap, per far assumere a tutto l’array la caratteristica di uno heap (Un heap è la condizione in cui i figli sx e dx sono minori o uguali al padre).
- Infine vi è l’HeapSort che concilia queste 2 funzioni in modo che l’array alla fine della sua esecuzione risulti ordinato.

Qui di seguito l’algoritmo scritto in C.

Definiamo la struttura:

//Lavoriamo su una struttura di questo tipo:
typedef struct{
int chiave, attributo;
} t_id_tab;

Funzione Rendi_Heap:

void Rendi_Heap(t_id_tab a[], int n, int lh, int i){
int s, d, max;
t_id_tab temp;
 
s = 2*i + 1;
d = 2*i + 2;
 
if ((s < lh) && (a[s].chiave > a[i].chiave))
max = s;
else
max = i;
 
if ((d < lh) && (a[d].chaive > a[max].chiave))
max = d;
 
if (max != i){
temp = a[i];
a[i] = a[max];
a[max] = temp;
Rendi_Heap(a, n, lh, max);
}
 
}

Funzione Costruisci_Heap:

//Rende Heap, tutto l'array. la funzione parte dall'indice n/2 - 1 poichè se partisse più avanti, la funzione Rendì_heap sforerebbe a destra in cerca di figli sx (s) e dx (d) 
void Costruisci_Heap(t_id_tab a[], int n){
int i;
for(i = n/2 - 1; i >= 0; i--)
  Rendi_Heap(a, n, lh, i);
 
}

Funzione HeapSort:

void HeapSort(t_id_tab a[], int n){
int i;
t_id_tab temp;
int lh = n; //inizialmente tutto l'array è ancora da trattare.
 
Costruisci_Heap(a, n);
 
for(i = n-1; i > 0; i--){
temp = a[i];
a[i] = a[0];
a[0] = temp;
lh--;
Rendi_Heap(a, n, lh, 0);
}
 
}

Insertion Sort in C, algoritmo di ordinamento basato sui confronti

0
2 anni fa
Scritto da Rocco Musolino in

L’Insertion Sort è tra i primi algoritmi di ordinamento, che vengono affrontati nel linguaggio C.
E’ un algoritmo di ordinamento basato sui confronti, la sua complessità computazionale è quadratica: O(n^2).

L’implementazione così come il funzionamento è basilare, consiglio anche la visione di questo simpatico video-danza che ne mostra il funzionamento, InsertionSort AlgoRythmics :)


- Qui di seguito ecco l’algoritmo scritto in C:

void insertion_sort(int a[], int n){
int i, j, temp;
int p = 0; //indice del minimo. (consideriamo inizialmente il primo elemento come fosse il minimo)
 
    for (i = 1; i < n; i++)
     if (a[p] > a[i]) 
        p = i;
 
    temp = a[0];
    a[0] = a[p];
    a[p] = temp;
 
    //abbiamo messo il minimo nella prima posizione a[0].
    //In questo modo lo useremo come sentinella (per non sforare l'array a sinistra).
 
for(i = 2; i < n; i++){ //partiamo dal 2 indice poichè non c'è bisogno di confrontare inizialmente già con a[0] che sappiamo essere il minimo.
    j = i;
      while(a[j] < a[j-1]){
                 temp = a[j];
                 a[j] = a[j-1];
                 a[j-1] = temp;
                 j--;
                 }    
    }
 
}
Torna all'inizio