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.   heapInserit(A(i), H)
**    3. per i=0, 1, 2, ..., n-1 ripeti:
**    4.   A(i) = heapExtractMin(H)
**  End
**
**  heapInsert(H, x)
**    1. sia i l'indice della prima posizione libera in H
**    2. sia H(i) = x
**    3. fintanto che l>1 e H(i/2)>H(i) ripeti:
**       3.1. scambia H(i) e H(i/2)
**       3.2. poni i = i/2
**  End
**
**  heapExtractMin(H)
**    1. min = H(1)
**    2. sia i=H(0) l'indice dell'ultimo elemento di H
**    3. H(1) = H(i), H(0) = H(0) - 1
**    4. i = 1
**    5. fintanto che 2i<=l e H(i) e' maggiore 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 min
**  End
**
**  Marco Liverani (marco.liverani@uniroma3.it) - Novembre 2024
**
*/

#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 leggiArray(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 stampaArray(int V[], int n) {
  int i;
  for (i=0; i<n; i++) {
    printf("%d ", V[i]);
  }
  printf("\n");
  return;
}

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

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

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

int heapExtractMin(int H[]) {
  int min, i;
  min = 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(min);
}

/*
 *  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++)
    heapInsert(A[i], H);
  for (i=0; i<=n; i++)
    A[i] = heapExtractMin(H);
  return;
}

/*
 *  Funzione principale
 */

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