c_____________________________________________________________________BubbleSort
c
c    Subrutina BubbleSort:
c
c      - ordena de menor a mayor un vector real*8 v(n)
c      - mediante el algoritmo Bubble Sort con T(n) ~ n^2
c
c_______________________________________________________________________________

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

      do i=1,n-1
        do j=n,i+1,-1
          if (v(i).gt.v(j)) then
            vc  =v(i)
            v(i)=v(j)
            v(j)=vc
          endif
        enddo
      enddo
 
      return
      end


c_______________________________________________________________________HeapSort
c
c    Subrutina HeapSort:
c
c      - ordena de menor a mayor un vector real*8 v(n)
c      - mediante el algoritmo Heap Sort con T(n) ~ n log(n)
c
c
c    Adaptacion de la subrutina original publicada en
c
c        S. Teukolsky, W.H. Press & W.T. Vetterling, 
c        "Numerical Recipes in Fortran 77, The Art of Scientific Computing",
c        Cambridge University Press (1986-1992)
c
c
c    Notas:
c
c      - FASE 1: CREACION DEL HEAP (arbol binario)
c
c                Se reordenan las componentes del vector v(n) de forma que
c
c                  v(j/2) .ge v(j),     psra 1 .le. j/2 .lt. j .le n
c
c                donde j/2 es una division entera (redondeada por truncamiento)
c
c                Al terminar esta fase cada nodo es mayor que sus descendientes.
c
c                                          v(1)
c                                       /        \
c                                    /               \
c                                 /                      \
c                            v(2)                         v(3)
c                          /      \                     /      \
c                         /        \                   /        \          
c                     v(4)          v(5)            v(6)         v(7)  
c                    /    \        /    \          /
c                 v(8)    v(9)  v(10)   v(11)   v(12) 
c
c      - FASE 2: EXTRACCION DE LAS COMPONENTES DEL VECTOR EN ORDEN CRECIENTE
c
c                Iterar (mientras queden nodos sin extraer) {
c                  Extraer el nodo superior.
c                  Recursivamente (hasta llegar al ultimo nivel) {
c                    Promover al nodo libre el mayor de sus dos descendientes
c                  } 
c                }
c 
c
c_______________________________________________________________________________

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

      if (n.lt.2) return

      k=n/2+1  ! Se postulan como sustitutos de v(1) los v(k), k = n/2, ___, 1
      ie=n     ! Los elementos extraidos se colocaran en v(ie), ie = n, ___, 1

      do

        if (k.gt.1) then               ! En FASE 1: CREACION DEL ARBOL BINARIO
          k=k-1                        ! k = n/2, ___, 1
          vc=v(k)                      ! Se salva el valor de v(k) en vc

        else                           ! En FASE 2: EXTRACCION DE COMPONENTES
          vc=v(ie)                     ! Se salva el valor de v(ie) en vc
          v(ie)=v(1)                   ! Se extrae v(1) y se coloca en v(ie) 
          ie=ie-1                      ! ie = n, ___, 1
          if (ie.eq.1) then            ! Si ya hemos terminado...
            v(1)=vc                    ! ... se coloca el menor valor en v(1) 
            return
          endif

        endif

        i=k                            ! Si estamos en FASE 1, i = n/2, ___, 1
                                       ! Si estamos en FASE 2, i = 1
        j=2*k                          ! Se compara v(i) con sus descendientes

        do while (j.le.ie)             ! Mientras haya descendientes de v(i)

          if (j.lt.ie) then            ! Se elige como v(j) el mayor
            if (v(j).lt.v(j+1)) j=j+1
          endif

          if (vc.lt.v(j)) then         ! Si v(j) es mayor que vc...
            v(i)=v(j)                  ! ... v(j) ocupa el lugar de v(i)... 
            i=j                        ! ... y se analiza el hueco que deja
            j=2*j

          else                         ! En caso contrario...
            j=ie+1                     ! ... rompemos el bucle

          endif
        enddo

        v(i)=vc                        ! Se coloca el menor valor en v(i)
      
      enddo

      end


c______________________________________________________________________QuickSort
c
c    Subrutina QuickSort:
c
c      - ordena de menor a mayor un vector real*8 v(n)
c      - mediante el algoritmo Quick Sort con T(n) ~ n log(n)   [en promedio]
c                                                  ~ n^2        [caso pesimo]
c
c    Notas:
c
c      - Normalmente requiere menos tiempo de CPU que el algoritmo Heap Sort.
c      - El caso pesimo es infrecuente.
c      - ESTA OPCION NO ESTA IMPLEMENTADA.
c_______________________________________________________________________________

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

      write(6,100) ' OPCION NO IMPLEMENTADA',
     .             ' No se ha ordenado el vector'
  100 format(//' >>>',a,':: ',a//)

      return
      end
