Quick Sort

Quick Sortプログラムをポインタを返す形式に書き直してみました。手動で割付しているので、開放忘れに注意が必要です。多分大丈夫だと思いますが。

ヒープ領域に動的配列を割り付けることで、大きな配列にも適用できます。

■実行結果

要素１個から10**8（１億）個までの乱数をSortして要した計算時間を出力しています。

Quick Sortの計算量は要素数Nに対して平均でＯ(NlogN)ですが、実行結果から要素数と実行時間の比がほぼ理論値通りになっていることが分かります。

■ソース・プログラム

MODULE m_sort
  IMPLICIT NONE
 CONTAINS
!
  RECURSIVE PURE FUNCTION qsort(x) RESULT(res)
    REAL, INTENT(IN) :: x(:)
    REAL, POINTER :: res(:)
    REAL, POINTER :: lt(:), ge(:)

    ALLOCATE( res(SIZE(x)) )
    IF (SIZE(x) <= 1) THEN
      res = x
    ELSE
      lt => qsort( PACK(x(2:), x(2:) <  x(1)) )
      ge => qsort( PACK(x(2:), x(2:) >= x(1)) )
      res = [ lt, x(1), ge ]
      DEALLOCATE(lt, ge)
    END IF

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

  CALL RANDOM_SEED()

  DO i = 0, 8
    ALLOCATE( x(10**i) )
    CALL RANDOM_NUMBER(x)
    CALL CPU_TIME(t0)
    y => qsort(x)
    CALL CPU_TIME(t1)
    PRINT *, i, 10**i, t1 - t0
    DEALLOCATE( x, y )
  END DO

  STOP
END PROGRAM sort