Gli esercizi
Testi e soluzioni di alcuni esercizi
Algoritmo di ordinamento Merge sort
/*
** merge_sort.c
**
** Codifica in linguaggio C dell'algoritmo Merge Sort
** per l'ordinamento di un array di numeri interi.
**
**
** Pseudo-codifica dell'algoritmo
**
** MergeSort(A, p, r):
** 1. se p<r allora
** 2. q = (p+r)/2
** 3. MergeSort(A, p, q)
** 4. MergeSort(A, q+1, r)
** 5. Merge(A, p, q, r)
** End
**
** Merge(A, p, q, r)
** 1. siano i=p, j=q+1, k=0
** 2. fintanto che i<=q e j<=r ripeti:
** 3. se A(i)<A(j) allora B(k)=A(i), i=i+1, k=k+1
** altrimenti B(k)=A(j), j=j+1, k=k+1
** 4. fine-ciclo
** 5. copia (A(i), ..., A(q)) in B
** 6. copia (A(j), ..., A(r)) in B
** 7. copia B in A
** End
**
** Marco Liverani (liverani@mat.uniroma3.it) - Aprile 2001
**
*/
#include <stdlib.h>
#include <stdio.h>
#define MAX 300
/*
* 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);
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;
}
/*
* Funzione Merge per la fusione di due
* componenti ordinate dell'array.
*/
void Merge(int A[], int p, int q, int r) {
int i, j, k, B[MAX];
i = p;
j = q+1;
k = 0;
while (i<=q && j<=r) {
if (A[i]<A[j]) {
B[k] = A[i];
i++;
} else {
B[k] = A[j];
j++;
}
k++;
}
while (i <= q) {
B[k] = A[i];
i++;
k++;
}
while (j <= r) {
B[k] = A[j];
j++;
k++;
}
for (k=p; k<=r; k++)
A[k] = B[k-p];
return;
}
/*
* Funzione ricorsiva MergeSort.
*/
void MergeSort(int A[], int p, int r) {
int q;
if (p < r) {
q = (p+r)/2;
MergeSort(A, p, q);
MergeSort(A, q+1, r);
Merge(A, p, q, r);
}
return;
}
/*
* Funzione principale
*/
int main(void) {
int n, V[MAX];
n = leggi_array(V);
MergeSort(V, 0, n-1);
stampa_array(V, n);
return(0);
}