Gli esercizi

Testi e soluzioni di alcuni esercizi

Algoritmo di ordinamento Heap sort

/*
**  heap_sort.c
**
**  Codifica in linguaggio C dell'algoritmo Heap Sort
**  per l'ordinamento di un array di numeri interi.
**
**
**  Pseudo-codifica dell'algoritmo
**
**  HeapSort(A, n):
**    1. per i=0, 1, 2, ..., n-1 ripeti:
**    2.   Inserisci(A(i), H)
**    3. per i=n-1, n-2, ..., 1, 0 ripeti:
**    4.   A(i) = Estrai_Max(H)
**  End
**
**  Inserisci(H, x)
**    1. sia l l'indice della prima posizione libera in H
**    2. sia H(l) = x
**    3. fintanto che l>1 e H(l/2)<H(l) ripeti:
**       3.1. scambia H(l) e H(l/2)
**       3.2. poni l = l/2
**  End
**
**  EstraiMax(H)
**    1. max = H(1)
**    2. sia l l'indice dell'ultimo elemento di H
**    3. H(1) = H(l), l = l-1
**    4. i = 1
**    5. fintanto che 2i<=l e H(i) e' minore di almeno uno dei
**       suoi figli ripeti:
**       5.1. se H(2i) > H(2i+1) allora scambia H(i) con H(2i)
**            e poni i=2i
**       5.2. altrimenti scambia H(i) con H(2i+1) e poni i=2i+1
**    6. restituisci max
**  End
**
**  Marco Liverani (liverani@mat.uniroma3.it) - Aprile 2001
**
*/

#include <stdlib.h>
#include <stdio.h>
#define MAX 300

/*
 *  Scambia: scambia il valore delle due variabili.
 */

void scambia(int *x, int *y) {
  int z;
  z = *x;
  *x = *y;
  *y = z;
  return;
}

/*
 * Legge in input il numero n ed n numeri interi
 * che memorizza nell'array. Restituisce il numero
 * di elementi letti (n).
 */

int leggi_array(int V[]) {
  int n, i;
  printf("Numero di elementi: ");
  scanf("%d", &n);
  printf("Inserisci %d numeri: ", n);
  for (i=0; i<n; i++)
    scanf("%d", &V[i]);
  return(n);
}

/*
 * Stampa in output l'array.
 */

void stampa_array(int V[], int n) {
  int i;
  for (i=0; i<n; i++) {
    printf("%d ", V[i]);
  }
  printf("\n");
  return;
}

/*
 *  Inserisci: inserisce l'elemento x nell'heap H.
 */

void Inserisci(int x, int H[]) {
  int l;
  l = H[0]+1;
  H[0] = H[0]+1;
  H[l] = x;
  while (l>1 && H[l/2]<H[l]) {
    scambia(&H[l], &H[l/2]);
    l = l/2;
  }
  return;
}

/*
 *  EstraiMax: restituisce il massimo elemento
 *  dell'heap H (la radice) e ricostruisce la
 *  struttura di heap.
 */

int EstraiMax(int H[]) {
  int max, i;
  max = H[1];
  H[1] = H[H[0]];
  H[0] = H[0]-1;
  i = 1;
  while (2*i<H[0] && (H[i]<H[2*i] || H[i]<H[2*i+1])) {
    if (H[2*i] > H[2*i+1]) {
      scambia(&H[i], &H[2*i]);
      i = 2*i;
    } else {
      scambia(&H[i], &H[2*i+1]);
      i = 2*i+1;
    }
  }
  if (2*i == H[0] && H[i] < H[2*i])
    scambia(&H[i], &H[2*i]);
  return(max);
}

/*
 *  HeapSort: ordina l'array A mediante l'algoritmo Heap Sort.
 */

void HeapSort(int A[], int n) {
  int i, H[MAX];
  H[0] = 0;
  for (i=0; i<n; i++)
    Inserisci(A[i], H);
  for (i=n-1; i>=0; i--)
    A[i] = EstraiMax(H);
  return;
}

/*
 *  Funzione principale
 */

int main(void) {
  int n, V[MAX];
  n = leggi_array(V);
  HeapSort(V, n);
  stampa_array(V, n);
  return(0);
}