Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- ** 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 iniz, int mediano, int fine) {
- int i, j, k, B[MAX];
- i = iniz;///i scorrerà da iniz a mediano
- j = mediano+1; ///j scorrerà da mediano+1 a fine
- k = 0;///indice di B
- while (i<=mediano && j<=fine) {
- if (A[i]<A[j]) {
- B[k] = A[i];
- i++;
- } else {
- B[k] = A[j];
- j++;
- }
- k++;
- }
- while (i <= mediano) {
- B[k] = A[i];
- i++;
- k++;
- }
- while (j <= fine) {
- B[k] = A[j];
- j++;
- k++;
- }
- for (k=iniz; k<=fine; k++)
- A[k] = B[k-iniz];
- //return;
- }
- /*
- * Funzione ricorsiva MergeSort.
- */
- void MergeSort(int A[], int iniz, int fine) {
- int mediano;
- if (iniz < fine) ///se abbiamo solo 1 elemento
- {
- mediano = (iniz+fine)/2;
- MergeSort(A, iniz, mediano);
- MergeSort(A, mediano+1, fine);
- Merge(A, iniz, mediano, fine);
- }
- //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);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement