! Metodos Numericos y Simulaciones en Astrofisica
! FCEFN - UNSJ, 2010
!
! ejemplo 3a
!
! Ordenamiento de arrays - Metodo de Shell
!
!
program eje3a
implicit none
  integer, parameter ::d=selected_real_kind(16,200)
  integer :: ii
  real(d), dimension(50) :: ori,dat
  real(d) :: val

! inicializa generador de numeros aleatorios
!
  call random_seed()

! arma un array de numeros reales al azar
!
  do ii=1,50
    call random_number(val)
    dat(ii)=float(int(10000._d*val))/10._d
  enddo

! guarda el array original
!
  ori=dat

! lo ordena usando insercion
!
  call shell(50,dat)

! salida a pantalla
!
  write(*,*)'Array original: '
  write(*,*)ori
  write(*,*)' '
  write(*,*)'Array ordenado: '
  write(*,*)dat

end program eje3a

! subrutina para efectuar un ordenamiento
! utilizando el metodo de Shell con intervalos
! dados por la serie recursiva de Knuth
!
! se ingresa con:
!
! N   numero de elementos del array
! ARR array a ordenar
!
! en la salida se devuelve el array ordenado en ARR.
!
subroutine shell(n,arr)
implicit none
  integer, parameter ::d=selected_real_kind(16,200)
  integer :: ii,jj,n,inc
  real(d),dimension(n) :: arr
  real(d) :: vv

! encuentra el incremento mayor de la serie que resulte util
!
  inc=1
  do while(inc <= n)
    inc=inc*3+1
  enddo

! inicio del bucle de seleccion
!
  do while(inc > 1)
    inc=inc/3
    do ii=inc+1,n
      vv=arr(ii)
      jj=ii

! inicia el bucle de insercion
!
      do while(arr(jj-inc) > vv)
        arr(jj)=arr(jj-inc)
        jj=jj-inc
        if(jj <= inc)exit
      enddo
      arr(jj)=vv
    enddo
  enddo
  return
end subroutine
