c___________________________________________________________________________Prog
c
c     Programa Prog:
c
c       - genera un vector de numeros aleatorios con distribucion U[0,1],
c       - lo ordena [opciones: BubbleSort, HeapSort, QuickSort] y
c       - lo imprime (indicando el tiempo de CPU consumido en la ordenacion)
c
c_______________________________________________________________________________

      implicit real*8 (a-h,o-z)
      character*1 siono

      allocatable v(:)

c.....Lectura del numero de componentes
    1 write(6,100) ' Introduce el numero de componentes: '
  100   format(/a,$)
        read(5,*) n
      if (n.lt.1) goto 1

c.....Dimensionamiento del vector por asignacion dinamica
      allocate(v(n),STAT=ist)
      if (ist.ne.0) then
        write(6,200) ' Error en la asignacion dinamica de memoria'
  200   format(/a/)
        call exit(1)
      endif

c.....Generacion de numeros aleatorios en el intervalo [0,1]
      call Generar(n,v)

c.....Ordenacion del vector (cronometrando el tiempo de CPU consumido)
      write(6,300) ' Algoritmos de ordenacion disponibles:',
     .             '      1 = Bubble Sort / T[n^2]',
     .             '      2 = Heap Sort   / T[n log(n)]',
     .             '      3 = Quick Sort  / T[n log(n)]'
  300 format(//a//a/a/a//)

    3 write(6,310) ' Opcion [1, 2, 3]: '
  310   format(/a,$)
        read(5,*) iopcn
      if (iopcn.lt.1.or.iopcn.gt.3) goto 3 

      call GetCPUTime(dtim0)

      if (iopcn.eq.1) then
        call BubbleSort(n,v)
      else if (iopcn.eq.2) then
        call HeapSort(n,v)
      else if (iopcn.eq.3) then
        call QuickSort(n,v)
      endif

      call GetCPUTime(dtim1)

      dt=dtim1-dtim0
      write(6,320) ' Tiempo de CPU = ',dt,' segundos'
  320 format(//a,f24.16,a//) 

c.....Impresion de resultados
    4 write(6,400) ' Desea imprimir el vector ordenado? [s/n]: '
  400   format(/a$)
        read(5,*) siono
      if ((siono.eq.'s').or.(siono.eq.'S')) then
        call Imprimir(n,v)
        read(5,'()')
      else if ((siono.ne.'n').and.(siono.ne.'N')) then
        goto 4
      endif

      call exit(0)

      end


c________________________________________________________________________Generar
c
c     Subrutina Generar: inicializa un vector real*8 v(n) con números aleatorios
c
c     Utiliza las funciones intrinsecas:
c
c         srand(iseed) -> usa iseed (entero no negativo) como semilla de una
c                         secuencia de numeros pseudo-aleatorios
c         rand()       -> devuelve un numero pseudo-aleatorio
c                         (real*4) en el rango 0.0 - 1.0
c
c_______________________________________________________________________________

      Subroutine Generar(n,v)
      implicit real*8 (a-h,o-z)
      dimension v(n)

    1 write(6,100) ' Introduce semilla (No. entero > 0): '
  100   format(/a,$)
        read(5,*) iseed
      if (iseed.lt.0) goto 1

      call srand(iseed)

      do i=1,n
        v(i)=dble(rand())
      enddo

      return
      end


c_______________________________________________________________________Imprimir
c
c     Subrutina Imprimir: imprime los componentes de un vector real*8 v(n)
c
c_______________________________________________________________________________

      Subroutine Imprimir(n,v)
      implicit real*8 (a-h,o-z)
      dimension v(n)

      write(6,100) ' RESULTADO:'
  100 format(//a/)

      do i=1,n
        write(6,200) i, v(i)
  200   format('    v(',i12,') = ',f24.16)
      enddo

      return
      end


c_____________________________________________________________________GetCPUTime
c
c     Proporciona dtime = tiempo de CPU consumido (en segundos) 
c     Nota: El valor inicial de dtime cuando arranca un programa no es 0.0.
c           Por tanto, el valor de dtime no es significativo pero
c           la diferencia entre dos valores de dtime sí lo es.
c     (Version para GFortran)
c
c_______________________________________________________________________________

      Subroutine GetCPUTime(dtime)
      real*8 dtime
      real*4 time

      call cpu_time(time)
      dtime=dble(time)

      return
      end

