fortran66のブログ

fortran について書きます。

Shell sortでTokudaのgap increment sequenceを使うとお得だw

この論文によると、Knuthのgap式よりも性能の良いものがいくつか提案されているようです。その中のTokudaの式h_k=\lceil(9({9\over 4})^k-4)/5)\rceil\quad,\quad h_k < {4\over 9}Nを使うことにします。

■実行結果

確かにKnuthのものより計算量が少なくなっていて、Quick sortと似たような要素数依存性(O(NlogN))を見せています。再帰も要らなければテンポラリメモリーも要らないShell sortに、こんな秘められた力があったとは!Shell sort かわいいよ Shell sort!

ソースコード

必要なオプション
/assume:realloc_lhs

MODULE m_sort
   IMPLICIT NONE
 CONTAINS

   PURE FUNCTION ssort(x) ! Shell Sort
     REAL, ALLOCATABLE :: ssort(:)
     REAL, INTENT(IN) :: x(:)  
     REAL :: tmp
     INTEGER :: i, j, k, kmax, igap
     
     ssort = x
     kmax = 0
     DO
      IF ( INT( (9.0 * (9.0 / 4.0)**(kmax + 1) - 4.0) / 5.0 ) > SIZE(x) * 4.0 / 9.0 ) EXIT
      kmax = kmax + 1
     END DO

     DO k = kmax, 0, -1
      igap = INT( (9.0 * (9.0 / 4.0)**k - 4.0) / 5.0 ) ! Tokuda's gap sequence
      DO i = igap, SIZE(x)
       DO j = i - igap, 1, -igap
        IF ( ssort(j) > ssort(j + igap) ) THEN
          tmp             = ssort(j)
          ssort(j)        = ssort(j + igap)
          ssort(j + igap) = tmp
        ELSE
          EXIT
        END IF
       END DO
      END DO
     END DO
    
     RETURN
   END FUNCTION ssort

END MODULE m_sort
!========================================================
PROGRAM sort
 USE m_sort
 IMPLICIT NONE
 REAL, ALLOCATABLE :: x(:), y(:)
 REAL :: t0, t1
 INTEGER :: i

 CALL RANDOM_SEED()

 DO i = 0, 9
   ALLOCATE( x(10**i) )
   CALL RANDOM_NUMBER(x)
   CALL CPU_TIME(t0)
   y = ssort(x)
   CALL CPU_TIME(t1)
   PRINT *, i, SIZE(x), t1 - t0
   DEALLOCATE( x, y )
 END DO

 STOP
END PROGRAM sort