Programa:

/****************************************************************************
*
* "ordena.c"
*
* Descripción del funcionamiento:
* - Toma del fichero de definición de la línea de argumentos los datos a ordenar.
* - Ordena por el método del "quicksort", usando procesos de ejecución concurrente, con la función
* quick().
* - Vuelca el resultado sobre el mismo fichero de datos.
* - Genera procesos hasta un tamaño de partición adecuado, para luegoc continuar de forma
* secuencial, de esta forma disminuye el tiempo de ordenación.
*
* Autores:
* Montserrat Encinas Villota
* Antº Manuel Herrera Fernández
*
****************************************************************************/

#include "rshmem.h"
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int nelm; /* variable externa que contiene el número de elementos del fichero a ordenar */

/* Intercambia x[i] con x[j] */

void swap(int x[],int i,int j) {
        int aux;
        aux=x[i];
        x[i]=x[j];
        x[j]=aux;
        return;
}

/* Función que en cada partición propuesta por la función quick( ) pone su pivote en la posición correcta */

void particion(int x[],int iz,int dcha, int *pivot) {
        int sup=dcha;
        int inf=iz;
        int piv;
        piv=*pivot;

/* Buscar las posiciones adecuadas de x[iz] y x[dcha] */

do {
     while(x[iz]<=x[piv] && iz<sup)

              iz++;

     while(x[dcha]>x[piv] && dcha>inf)

              dcha--;

     if(dcha>iz) swap(x,dcha,iz);

     }while(dcha>iz);

/* Hacer que el pivote apunte correctamente para construir la partición */

swap(x,dcha,piv);
*pivot=dcha;
return;
}

/* Algoritmo secuencial de quicksort */

void secuencial(int x[],int inf,int sup,int pivote) {

        if(sup<=inf)
        return;

particion(x,inf,sup,&pivote);
secuencial(x,inf,pivote-1,inf);
secuencial(x,pivote+1,sup,pivote+1);

}

/* Función recursiva que organiza el tratamiento de las particiones. Ordena en orden ascendente.
*  Algoritmo concurrente de quicksort */

void quick(int x[],int inf,int sup,int pivote) {

int pid,estado;

/* Cuando la partición tiene un tamaño menor que 'nelem', lo óptimo es seguir
*  con el algoritmo en forma secuencial */

if(sup-inf<nelem || sup<=inf) {
    
     secuencial(x,inf,sup,pivote);
     return;
}

particion(x,inf,sup,&pivote);

if(fork( )==0) /* creamos un hijo para que haga su parte de ordenación */ {

     quick(x,inf,pivote-1,inf);
     exit(5);
}

else {

 quick(x,pivote+1,sup,pivote+1);  /* ahora ordena el padre */
 pid=wait(&estado);   /* el padre espera al hijo */
 }
}

/* Función principal */

void main(int argc, char *argv[]) {
        int sup;  /* variable con la posición superior de cada partición */
        int inf=0;  /* variable con la posición inferior de cada partición */
        int pivote=0;  /* pivote de la partición */
        int j,i=0;  /* variables índice */
        int *x;  /* puntero a los datos en memoria compartida */
        FILE *pf;  /* fichero de datos, donde también volcaremos la solución */

        if(argc>2){
            fprintf(stderr,"Introduzca:\n ordena nombre_de _fichero\n");
            exit(0);
        }

        if((pf=fopen(argv[1],"r+"))==NULL){
            fprintf(stderr,"error en apertura fichero\n");
            exit (1);
        }

/* Crear zona de memoria compartida con la función crearMemoria()
*  cuya declaración se encuentra en rshmem.h */

        if(!crearMemoria()){
            fprintf(stderr,"error en crearMemoria\n");
            exit(2);
        }

        x=(int *)memoria;

        do {

              fscanf(pf,"%d",x+i); i++;
        } while(!feof(pf));

        sup=i-2;

/* Buscar el tamaño óptimo de partición de manera que minimicemos el tiempo de ejecución del programa. */

       if (sup>=100) nelem=10;

       else nelem=((sup+1)/10)+1;

       quick(x,inf,sup,pivote);

       for(j=0;j<=i-2;j++)
             fprintf(pf,"%d ",x[j]);

/* Eliminar memoria compartida con la función eliminarMemoria( ) su declaración se encuentra en rshmem.h */

       if(!eliminarMemoria( )){
            fprintf(stderr,"error en eliminaMemoria\n");
            exit(3);
       }
 /* Cerrar el fichero de trabajo */
    
      if((fclose(pf))==EOF){
            fprintf(stderr,"error en a la hora de cerrar el fichero\n");
            exit(4);
      }
}

Volver