Program shell_sort_test
!------------------------------------------------------------------------------
!Program: Shell Sort
!Author: Chris Harper
!Date: 3/23/2008
!------------------------------------------------------------------------------

IMPLICIT NONE

!constants
integer, parameter :: ARRAY_SIZE = 100

interface
	subroutine  shell_sort(array)
	integer, intent(INOUT) :: array(0:)
	end subroutine
	real function random_range(min, max)
	integer, intent(IN) :: min, max
	end function
	subroutine init_random()
	end subroutine
end interface

!declarations
integer :: i
integer :: rand_array(0:ARRAY_SIZE-1)


!fill array with random numbers
call init_random
do i = 0, ARRAY_SIZE-1
	rand_array(i) = random_range(0, 10)
end do

!print unsorted
print "(14I5)", rand_array

call shell_sort(rand_array)

!print sorted
print "(14I5)", rand_array

end


subroutine shell_sort(array)
integer, intent(INOUT) :: array(0:)
integer :: gap, h, g, i, j, k

!find the starting gap
!which is the greatest number in the sequence (3^i-1)/2
!less than the size of the array to sort
h = 1
g = size(array)/2 !start g with a safe value
do
	gap = g
	g = (3**h - 1) / 2
	h = h + 1
	if (g > size(array)) exit
end do

do while (gap > 0)
	!insertion sort
	do i = gap, size(array)
      j = i
      k = array(i)
      do while ((j >= gap) .AND. (array(j-gap) > k))
        array(j) = array(j - gap)
        j = j - gap
      end do
      array(j) = k
    end do
    
    !decrease gap
	gap = gap / 3
end do
end subroutine


!returns a random value between min and max
function random_range(min, max)
integer, intent(IN) :: min, max
real :: random

call random_number(random)
random_range = nint(random * (max - min)) + min
end function


!initialize the random number generator (platform independent)
subroutine init_random()
integer :: i, seed_size
integer :: time_array(8)
integer, allocatable :: seed(:)

!find seed size
call random_seed(size = seed_size)
allocate(seed(seed_size))

!create seed from current seconds * milliseconds
call date_and_time(values = time_array)
seed(1) = time_array(8) * time_array(7)
call random_seed(put = seed)
!print *, seed_size
!print *, seed(1)
end subroutine