Fortran で QuickSort

##クイック・ソート
再帰の例題としてよく使われる quick sort です。Fortran90 で導入された pack 関数を使うと、簡単に書けることが知られています。pack はフィルター関数に当たります。

一般には関数型言語の例題で出てくるように、

res = [pack(x(2:), x(2:) <= x(1)), x(1), pack(x(2:), x(2:) > x(1))]

というように書きます。

ここでは <,=,> の三つの場合に分ける形にしてみました。値の縮退が多い場合に有利になります。

クイック・ソートは再帰でスタック領域を大量に消費するので、リンカのオプションでスタックを増やしておく必要があります。

また intel fortran では Fortran2003 semantics を有効にしておく必要があります。

##プログラム

    module m_sort
      implicit none
    contains  
      recursive function iqsort(ix) result(ires)
        integer, allocatable :: ires(:)
        integer, intent(in)  :: ix(:)
        integer :: k
        if (size(ix) <= 1) then 
          ires = ix
        else  
          k = ix(size(ix) / 2)
          ires = [iqsort(pack(ix, ix < k)), pack(ix, ix == k), iqsort(pack(ix, ix > k))] 
        end if
      end function iqsort  
    end module m_sort  

    program qsort
      use m_sort
      implicit none
      integer :: n = 10**7
      integer, allocatable :: ix(:), iy(:)
      real, allocatable :: x(:)
      allocate( x(n) )
      call random_seed()
      call random_number(x)
      ix = x * 10**6
      iy = iqsort(ix)
      print *, all(iy(1:n - 1) <= iy(2:)), count(iy(1:n - 1) == iy(2:))
    end program qsort

###実行結果

 T 9000046
続行するには何かキーを押してください . . .