Fortran Coder

标题: [第一讲] 快速排序算法 [打印本页]
作者: aliouying    时间: 2014-3-2 09:56
标题: [第一讲] 快速排序算法
在数值计算中，不可避免的需要用到排序，对于快速排序算法，数值分析的书里面介绍非常详细，这里我们不讨论具体算法，只讨论程序的标准性、通用性、可扩展性

大家可以从以下方面来讨论：

1、程序的错误地方，需改进的地方
2、跟常用算法库的程序进行对比，贴出相应的效率对比分析，并注明编译器、系统、版本等信息
3、数组大小与时间的效率图
4、针对自己的问题，贴出相关的效率图
5、网络上存在的快速排序算法都有哪些，效率、通用性等

当然，欢迎灌水

抛砖引玉：
[Fortran] 纯文本查看 复制代码
Module QuickSortMod

!

! quick sort algorithm

!

    Integer,    Parameter :: RealPrec = kind(0.0d0)

    !

    ! InterFace

    !

    Interface QuickSort

        Module Procedure quick_sort_i

        Module Procedure quick_sort_d

    End InterFace QuickSort

    

    Contains

!****************************************************************!******************************************************************************!

    Recursive Subroutine quick_sort_i(ilist1,ilist2,dlist1,zlist1) 

       Integer,    dimension(:), intent(in out)             :: ilist1

       Integer,    dimension(:), intent(in out), optional   :: ilist2

       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist1

       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1

       

       Integer              :: i, j, n 

       Integer              :: chosen, temp

       complex(RealPrec)           :: ztemp

       Integer, parameter   :: max_simple_sort_size = 6

       

       n = size(ilist1) 

       

       If (n <= max_simple_sort_size) Then 

          ! Use interchange sort for small lists 

          If ( (Present(ilist2)) .and. (Present(dlist1)) .and. (Present(zlist1)) ) Then

                call interchange_sort(ilist1,ilist2=ilist2,dlist1=dlist1,zlist1=zlist1) 

          ElseIf ( (Present(dlist1)) .and. (Present(zlist1)) ) Then

                call interchange_sort(ilist1,dlist1=dlist1,zlist1=zlist1) 

          ElseIf ( (Present(ilist2)) .and. (Present(dlist1)) ) Then

                call interchange_sort(ilist1,ilist2=ilist2,dlist1=dlist1) 

          ElseIf ( (Present(ilist2)) .and. (Present(zlist1)) ) Then

                call interchange_sort(ilist1,ilist2=ilist2,zlist1=zlist1)       

          ElseIf ( (Present(dlist1)) ) Then

                call interchange_sort(ilist1,dlist1=dlist1)      

          ElseIf ( (Present(ilist2)) ) Then

                call interchange_sort(ilist1,ilist2=ilist2)      

          ElseIf ( (Present(zlist1)) ) Then

                call interchange_sort(ilist1,zlist1=zlist1)         

          Else

                call interchange_sort(ilist1) 

          endif

       Else 

          ! Use partition (“quick”) sort 

          chosen = ilist1(n/2) 

          i = 0 

          j = n + 1 

          Do 

             ! Scan list from left End 

             ! until element >= chosen is found 

             Do 

                i = i + 1 

                If (ilist1(i) >= chosen) exit 

             End Do 

             ! Scan list from right End 

             ! until element <= chosen is found 

             Do 

                j = j - 1 

                If (ilist1(j) <= chosen) exit 

             End Do    

             If (i < j) Then 

             

                ! Swap two out of place elements 

                temp      = ilist1(i) 

                ilist1(i) = ilist1(j) 

                ilist1(j) = temp                 

                 

                If (Present(ilist2)) Then

                    temp      = ilist2(i) 

                    ilist2(i) = ilist2(j) 

                    ilist2(j) = temp                       

                endif

                 

                If  (Present(dlist1)) Then  

                    ztemp     = dlist1(i) 

                    dlist1(i) = dlist1(j) 

                    dlist1(j) = ztemp 

                endif

                

                If  (Present(zlist1)) Then  

                    ztemp     = zlist1(i) 

                    zlist1(i) = zlist1(j) 

                    zlist1(j) = ztemp 

                endif

                

             Else If (i == j) Then 

                i = i + 1 

                exit 

             Else 

                exit 

             End If 

          End Do 

       

          If ( (Present(ilist2)) .and. (Present(dlist1)) .and. (Present(zlist1)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),dlist1=dlist1(:j),zlist1=zlist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),dlist1=dlist1(i:),zlist1=zlist1(i:)) 

          ElseIf ( (Present(dlist1)) .and. (Present(zlist1)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),dlist1=dlist1(:j),zlist1=zlist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),dlist1=dlist1(i:),zlist1=zlist1(i:)) 

          ElseIf ( (Present(ilist2)) .and. (Present(dlist1)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),dlist1=dlist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),dlist1=dlist1(i:)) 

          ElseIf ( (Present(ilist2)) .and. (Present(zlist1)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j),zlist1=zlist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:),zlist1=zlist1(i:))      

          ElseIf ( (Present(dlist1)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),dlist1=dlist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),dlist1=dlist1(i:))   

          ElseIf ( (Present(ilist2)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),ilist2=ilist2(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),ilist2=ilist2(i:))      

          ElseIf ( (Present(zlist1)) ) Then

                If (1 < j) call quick_sort_i(ilist1(:j),zlist1=zlist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:),zlist1=zlist1(i:))        

          Else

                If (1 < j) call quick_sort_i(ilist1(:j)) 

                If (i < n) call quick_sort_i(ilist1(i:))   

          endif

       End If  ! test for small array 

    End Subroutine quick_sort_i 

!****************************************************************!******************************************************************************!

    Subroutine interchange_sort(ilist1,ilist2,dlist1,zlist1)

     

       Integer,    dimension(:), intent(in out)             :: ilist1

       Integer,    dimension(:), intent(in out), optional   :: ilist2

       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist1

       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1

       

       Integer      :: i, j 

       Integer      :: temp 

       complex(RealPrec)   :: ztemp

       

       Do i = 1, size(ilist1) - 1 

       

          Do j = i + 1, size(ilist1) 

          

             If (ilist1(i) >  ilist1(j)) Then 

             

                temp      = ilist1(i) 

                ilist1(i) = ilist1(j) 

                ilist1(j) = temp 

                             

                If (Present(ilist2)) Then

                    temp      = ilist2(i) 

                    ilist2(i) = ilist2(j) 

                    ilist2(j) = temp                       

                endif

                 

                If  (Present(dlist1)) Then  

                    ztemp     = dlist1(i) 

                    dlist1(i) = dlist1(j) 

                    dlist1(j) = ztemp 

                endif

        

                If  (Present(zlist1)) Then  

                    ztemp     = zlist1(i) 

                    zlist1(i) = zlist1(j) 

                    zlist1(j) = ztemp 

                endif

                                

             End If 

          End Do 

       End Do 

    End Subroutine interchange_sort     

!****************************************************************!******************************************************************************!  

    Recursive Subroutine quick_sort_d(dlist1,dlist2,ilist1,zlist1) 

       Real(RealPrec),    dimension(:), intent(in out)             :: dlist1

       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist2

       Integer,    dimension(:), intent(in out), optional   :: ilist1

       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1

   

       

       Integer              :: i, j, n 

       Integer              :: temp

       real(RealPrec)              :: dtemp, chosen

       Complex(RealPrec)           :: ztemp

       Integer, parameter   :: max_simple_sort_size = 6

       

       n = size(dlist1) 



       If (n <= max_simple_sort_size) Then 

          ! Use interchange sort for small lists 

           If ( (Present(ilist1)).and.(Present(dlist2)) .and. (Present(zlist1)) ) Then

                call interchange_sort_d(dlist1,dlist2=dlist2,ilist1=ilist1,zlist1=zlist1)   

           ElseIf( (Present(ilist1)) .and. (Present(zlist1)) ) Then

               call interchange_sort_d(dlist1,ilist1=ilist1,zlist1=zlist1)   

            ElseIf ( (Present(dlist2)) .and. (Present(zlist1)) ) Then

                call interchange_sort_d(dlist1,dlist2=dlist2,zlist1=zlist1) 

            ElseIf ( (Present(dlist2)) .and. (Present(ilist1)) ) Then 

                call interchange_sort_d(dlist1,dlist2=dlist2,ilist1=ilist1) 

          ElseIf ( (Present(ilist1)) ) Then

                call interchange_sort_d(dlist1,ilist1=ilist1)    

          ElseIf ( (Present(zlist1)) ) Then 

              call interchange_sort_d(dlist1,zlist1=zlist1)  

          ElseIf ( (Present(dlist2)) ) Then

                call interchange_sort_d(dlist1,dlist2=dlist2)          

          Else

                call interchange_sort_d(dlist1) 

          endif

       Else 

          ! Use partition (“quick”) sort 

          chosen = dlist1(n/2) 

          i = 0 

          j = n + 1 

          Do 

             ! Scan list from left End 

             ! until element >= chosen is found 

             Do 

                i = i + 1 

                If (dlist1(i) >= chosen) exit 

             End Do 

             ! Scan list from right End 

             ! until element <= chosen is found 

             Do 

                j = j - 1 

                If (dlist1(j) <= chosen) exit 

             End Do    

             If (i < j) Then 

             

                ! Swap two out of place elements 

                dtemp     = dlist1(i) 

                dlist1(i) = dlist1(j) 

                dlist1(j) = dtemp                 

                 

                If (Present(ilist1)) Then

                    temp      = ilist1(i) 

                    ilist1(i) = ilist1(j) 

                    ilist1(j) = temp                       

                endif

                

                If (Present(dlist2)) Then

                    dtemp     = dlist2(i) 

                    dlist2(i) = dlist2(j) 

                    dlist2(j) = dtemp                       

                endif

                

                If  (Present(zlist1)) Then  

                    ztemp     = zlist1(i) 

                    zlist1(i) = zlist1(j) 

                    zlist1(j) = ztemp 

                endif

             Else If (i == j) Then 

                i = i + 1 

                exit 

             Else 

                exit 

             End If 

          End Do 

            

           If ( (Present(ilist1)).and.(Present(dlist2)) .and. (Present(zlist1)) ) Then

                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),ilist1=ilist1(:j),zlist1=zlist1(:j)) 

                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),ilist1=ilist1(i:),zlist1=zlist1(i:))   

           ElseIf( (Present(ilist1)) .and. (Present(zlist1)) ) Then

               If (1 < j) call quick_sort_d(dlist1(:j),ilist1=ilist1(:j),zlist1=zlist1(:j)) 

               If (i < n) call quick_sort_d(dlist1(i:),ilist1=ilist1(i:),zlist1=zlist1(i:))   

            ElseIf ( (Present(dlist2)) .and. (Present(zlist1)) ) Then

                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),zlist1=zlist1(:j)) 

                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),zlist1=zlist1(i:)) 

            ElseIf ( (Present(dlist2)) .and. (Present(ilist1)) ) Then 

                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j),ilist1=ilist1(:j)) 

                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:),ilist1=ilist1(i:)) 

          ElseIf ( (Present(ilist1)) ) Then

                If (1 < j) call quick_sort_d(dlist1(:j),ilist1=ilist1(:j)) 

                If (i < n) call quick_sort_d(dlist1(i:),ilist1=ilist1(i:)) 

          ElseIf ( (Present(zlist1)) ) Then 

               If (1 < j) call quick_sort_d(dlist1(:j),zlist1=zlist1(:j)) 

               If (i < n) call quick_sort_d(dlist1(i:),zlist1=zlist1(i:)) 

          ElseIf ( (Present(dlist2)) ) Then

                If (1 < j) call quick_sort_d(dlist1(:j),dlist2=dlist2(:j)) 

                If (i < n) call quick_sort_d(dlist1(i:),dlist2=dlist2(i:))      

          Else

                If (1 < j) call quick_sort_d(dlist1(:j)) 

                If (i < n) call quick_sort_d(dlist1(i:)) 

          endif

 

       End If  ! test for small array 

    End Subroutine quick_sort_d 

!****************************************************************!******************************************************************************!

    Subroutine interchange_sort_d(dlist1,dlist2,ilist1,zlist1)

     

       Real(RealPrec),    dimension(:), intent(in out)             :: dlist1

       Real(RealPrec),    dimension(:), intent(in out), optional   :: dlist2

       Integer,    dimension(:), intent(in out), optional   :: ilist1

       Complex(RealPrec), dimension(:), intent(in out), optional   :: zlist1

       

       Integer      :: i, j 

       Integer      :: temp 

       real(RealPrec)      :: dtemp

       complex(RealPrec)   :: ztemp

       

       Do i = 1, size(dlist1) - 1 

       

          Do j = i + 1, size(dlist1) 

          

             If (dlist1(i) >  dlist1(j)) Then 

             

                dtemp     = dlist1(i) 

                dlist1(i) = dlist1(j) 

                dlist1(j) = dtemp 

                

                If (Present(dlist2)) Then

                    dtemp     = dlist2(i) 

                    dlist2(i) = dlist2(j) 

                    dlist2(j) = dtemp                       

                endif          

                 

                If (Present(ilist1)) Then

                    temp      = ilist1(i) 

                    ilist1(i) = ilist1(j) 

                    ilist1(j) = temp                       

                endif

                

                If  (Present(zlist1)) Then  

                    ztemp     = zlist1(i) 

                    zlist1(i) = zlist1(j) 

                    zlist1(j) = ztemp 

                endif

             End If 

          End Do 

       End Do 

       Return

    End Subroutine interchange_sort_d  

!****************************************************************!******************************************************************************!

End Module

主程序：
[Fortran] 纯文本查看 复制代码
Program QuickSortMain

    Use QuickSortMod

    Implicit None

    Integer :: N

    Integer,    allocatable :: IntDat(:)

    Real(8),    allocatable :: RealDat(:)

    Complex(8), allocatable :: ComplexDat(:)

    real,       allocatable :: Dat(:)

    

    N = 10

    

    allocate( IntDat(N), RealDat(N), ComplexDat(N), Dat(N) )

    

    Call Random_Seed()

    

    ! set integer data

    Call Random_number(Dat)

    

    IntDat = Int( (2*Dat-1)*100 )

    

    ! set real data

    Call Random_number(Dat)

    

    RealDat = (2*Dat-1)*100

    

    ! set complx data

    Call Random_number(Dat)

    

    ComplexDat = (2*Dat-1)*100

    

    Call QuickSort(IntDat,dlist1=RealDat,zlist1=ComplexDat)

    

    Call QuickSort(RealDat,ilist1=IntDat,zlist1=ComplexDat)

Stop

End Program QuickSortMain

作者: 楚香饭    时间: 2014-3-2 20:17
我这里找了三个快速排序算法。

楼主这个，我称为 QuickSortMod，Intel Fortran 扩展的 Qsort，以及 Juli Rew（Fortran.com）写的（http://www.fcode.cn/code_prof-38-1.html）

用的 IVF for windows XE2013 SP1 编译，win7sp1 运行。

一些N长度与耗时的曲线如图（X轴为N数据量，Y轴为耗时 mSec ）：


我很奇怪Intel Fortran 的 Qsort 为啥后面斜率变低了，实验了多次。很是奇怪。数据量稍低时，JuliRew的算法效率高，数据量大时，IVF所带的QSort表现不错。

但是这三者又各有优点：
QuickSortMod，允许有其他数组随之而排序，而其他两者只允许一个数组排序。这可能是影响它效率发挥的原因。
IVF扩展的QSort，支持各种数据类型，包括用户自己的 type 类型。（需指定数据单个所占的字节数，需书写外部比较函数）自己书写外部比较函数，可以实现类似时间日期的排序。但通用性不好，只能在 VF 上使用。
JuliRew 算法，简单，高效，代码精炼。

最后，提个题外话，如果数据中已有一定的顺序，比如：1，2，3，7，4，5，6，8，9。用堆排序效率很高。

作者: aliouying    时间: 2014-3-2 20:51
chuxf 发表于 2014-3-2 20:17
我这里找了三个快速排序算法。

楼主这个，我称为 QuickSortMod，Intel Fortran 扩展的 Qsort，以及 Juli R ...

若楼上仔细看下我的算法，其实我的算法就是冒泡排序算法，只是我的程序做了太多的IF用于判断后面跟随的扩展数组
作者: 楚香饭    时间: 2014-3-2 21:50
aliouying 发表于 2014-3-2 20:51
若楼上仔细看下我的算法，其实我的算法就是冒泡排序算法，只是我的程序做了太多的IF用于判断后面跟随的扩 ...

呵呵，确实没有仔细看。
只大致看了接口处。快速排序就是根据冒泡算法修改的，所以有相似之处。
作者: aliouying    时间: 2014-3-3 08:51
chuxf 发表于 2014-3-2 21:50
呵呵，确实没有仔细看。
只大致看了接口处。快速排序就是根据冒泡算法修改的，所以有相似之处。 ...

不是相似，是算法就是一样的，只是我的partition部分直接在程序里面
作者: fcode    时间: 2014-3-3 09:35
我理解的冒泡法是不进行 partition 的，相邻两个点对比，调换，走完整个数组，然后循环大约N次。
而先调换一半，就是改进后的快速排序。
作者: aliouying    时间: 2014-3-3 23:26
fcode 发表于 2014-3-3 09:35
我理解的冒泡法是不进行 partition 的，相邻两个点对比，调换，走完整个数组，然后循环大约N次。
而先调换 ...

嗯，是的

在比较小的时候没必要partition，我设的是6，其实这个没有多大必要，所以直接用改进的快速排序算法即可，可以精简程序
作者: aliouying    时间: 2014-3-3 23:27
fcode 发表于 2014-3-3 09:35
我理解的冒泡法是不进行 partition 的，相邻两个点对比，调换，走完整个数组，然后循环大约N次。
而先调换 ...

石头，你的F币刷得这么高了！！！
作者: fcode    时间: 2014-3-3 23:29
aliouying 发表于 2014-3-3 23:27
石头，你的F币刷得这么高了！！！

嘘，这个可以作弊的
作者: aliouying    时间: 2014-3-4 12:22
fcode 发表于 2014-3-3 23:29
嘘，这个可以作弊的

作者: pasuka    时间: 2014-3-4 20:43
为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可
作者: 楚香饭    时间: 2014-3-4 21:03
pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可

做这点计算，Fortran还是足以应对的。
作者: aliouying    时间: 2014-3-4 23:26
pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可

欢迎大家把自己熟悉的代码拿过来做对比，我发这个贴只是抛砖引玉
算法一样时，计算机语言、编译器、系统等不同效率可能都有差别，所以可以让感兴趣的爱好者一起来参与
作者: pasuka    时间: 2014-3-10 13:25
chuxf 发表于 2014-3-2 20:17
我这里找了三个快速排序算法。

楼主这个，我称为 QuickSortMod，Intel Fortran 扩展的 Qsort，以及 Juli R ...

简单测试了一下，分别调用QuickSortMod和Juli Rew 的qsort（修改为整数排序）以及gcc自带的qsort，随机整型数组的长度由10的1次方增加到10的7次方（受制于内存，未测试更大的动态数组）测试平台：

OS： Debian 7.2 32bit

CPU： ARMv6-compatible processor 700Mhz OC 1000Mhz
Memory: 437.7MB
CC： gcc-4.7
FC： gfortran-4.7
计算结果：
=========================================================================
Fortran version of Quick Sort I
Len of array:        10 Time =  0.000 seconds.
Fortran version of Quick Sort II
Len of array:        10 Time =  0.000 seconds.
Fortran call C version of qsort
Len of array:        10 Time =  0.000 seconds.
Fortran version of Quick Sort I
Len of array:       100 Time =  0.000 seconds.
Fortran version of Quick Sort II
Len of array:       100 Time =  0.000 seconds.
Fortran call C version of qsort
Len of array:       100 Time =  0.000 seconds.
Fortran version of Quick Sort I
Len of array:      1000 Time =  0.000 seconds.
Fortran version of Quick Sort II
Len of array:      1000 Time =  0.000 seconds.
Fortran call C version of qsort
Len of array:      1000 Time =  0.010 seconds.
Fortran version of Quick Sort I
Len of array:     10000 Time =  0.010 seconds.
Fortran version of Quick Sort II
Len of array:     10000 Time =  0.020 seconds.
Fortran call C version of qsort
Len of array:     10000 Time =  0.010 seconds.
Fortran version of Quick Sort I
Len of array:    100000 Time =  0.180 seconds.
Fortran version of Quick Sort II
Len of array:    100000 Time =  0.160 seconds.
Fortran call C version of qsort
Len of array:    100000 Time =  0.110 seconds.
Fortran version of Quick Sort I
Len of array:   1000000 Time =  1.500 seconds.
Fortran version of Quick Sort II
Len of array:   1000000 Time =  1.750 seconds.
Fortran call C version of qsort
Len of array:   1000000 Time =  1.370 seconds.
Fortran version of Quick Sort I
Len of array:  10000000 Time = 17.660 seconds.
Fortran version of Quick Sort II
Len of array:  10000000 Time = 20.340 seconds.
Fortran call C version of qsort
Len of array:  10000000 Time = 16.110 seconds.

*******************************************************************************************************************************
初步意见：
1、ISO_C_BINDING对于混合编程相当便捷，fortran可以方便的使用成熟的C代码；
2、大数组排序，在linux或mingw环境下直接调用qsort更具优势
********************************************************************************************************************************
主程序
[Fortran] 纯文本查看 复制代码
program SortTest

use QuickSortMod

use qsort_c_module

implicit none

interface

        subroutine qsort(a,length)bind(c,name="sort_integer")

        use,intrinsic::iso_c_binding

        integer(c_int),value::length        

        integer(c_int)::a(length)

        end subroutine

end interface



integer::N,i

integer,allocatable::IntDat(:),intDat2(:),intdat3(:)

real,allocatable::dat(:)

real::start,finish

do i=1,7

        N=10**i

        if(allocated(intdat))deallocate(intdat)

        if(allocated(intdat2))deallocate(intdat2)

        if(allocated(dat))deallocate(dat)

        if(allocated(intdat3))deallocate(intdat3)

        allocate(IntDat(n),intDat2(n),dat(n),intdat3(n))

        call random_seed()

        call random_number(dat)

        intDat = int((2*Dat-1)*100)

        intdat2 = intdat

        intdat3 = intdat

        call cpu_time(start)

        call quick_sort_i(intdat)

        call cpu_time(finish)

        write(*,*)"Fortran version of Quick Sort I"

        write(*,'("Len of array:",i10," Time = ",f6.3," seconds.")')n,finish-start

        

        call cpu_time(start)

        call QsortC(intdat3)

        call cpu_time(finish)

        write(*,*)"Fortran version of Quick Sort II"

        write(*,'("Len of array:",i10," Time = ",f6.3," seconds.")')n,finish-start

        

        call cpu_time(start)

        call qsort(intdat2,n)

        call cpu_time(finish)

        write(*,*)"Fortran call C version of qsort"

        write(*,'("Len of array:",i10," Time = ",f6.3," seconds.")')n,finish-start

        deallocate(intdat,intdat2,dat,intdat3)

enddo



end program


c接口程序代码：
[C] 纯文本查看 复制代码
#include <stdlib.h> 

#include <stdio.h> 

/* qsort int comparison function */ 

int int_cmp(const void *a, const void *b) 

{ 

    const int *ia = (const int *)a; // casting pointer types 

    const int *ib = (const int *)b;

    return *ia  - *ib; 

        /* integer comparison: returns negative if b > a 

        and positive if a > b */ 

} 

/* integer array printing function */ 

void print_int_array(const int *array, size_t len) 

{ 

    size_t i;

    for(i=0; i<len; i++) 

        printf("%d | ", array);

    putchar('\n');

} 

void sort_integer(int *a,size_t a_len)

{

        /* print original integer array */ 

    //print_int_array(a, a_len);        

        /* sort array using qsort functions */ 

    qsort(a, a_len, sizeof(int), int_cmp);

}





作者: aliouying    时间: 2014-3-11 18:57
pasuka 发表于 2014-3-10 13:25
简单测试了一下，分别调用QuickSortMod和Juli Rew 的qsort（修改为整数排序）以及gcc自带的qsort，随机整 ...

从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew的QSortC跟石头测出来的效率对比图恰恰相反，是否修改时出了点问题？
作者: pasuka    时间: 2014-3-11 20:25
aliouying 发表于 2014-3-11 18:57
从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew ...

gcc和gfortran都是默认的优化设置，没有修改过
我只是去掉了QuickSortMod的interface，因为gfotran编译报错
作者: pasuka    时间: 2014-3-11 20:26
aliouying 发表于 2014-3-11 18:57
从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew ...

如果有兴趣，还可以gfortran调用gsl再测试一下
作者: aliouying    时间: 2014-3-12 16:58
pasuka 发表于 2014-3-11 20:26
如果有兴趣，还可以gfortran调用gsl再测试一下

我在写毕业论文，所以没多少时间，等过段时间测试下
作者: 岸边的鱼    时间: 2014-4-11 22:29
排序是个很好的课题，方法应该有很多种，期待看到别的排序方法，都拿来比较下
作者: 山大克鲁士    时间: 2014-5-26 14:02
快排纵然好理解，但是个人总感觉递归的效率可能不高，正如Davis将所有递归利用压栈弹栈来操作一样，虽然在汇编级递归确实也是不断的弹栈压栈过程。。。
不知诸君有何见解？
作者: 楚香饭    时间: 2014-5-26 14:14
山大克鲁士 发表于 2014-5-26 14:02
快排纵然好理解，但是个人总感觉递归的效率可能不高，正如Davis将所有递归利用压栈弹栈来操作一样，虽然在 ...

递归一定会慢的。尤其是局部变量比较多的函数。

如果不考虑编译器的优化作用的话。
作者: glodve    时间: 2016-7-28 16:21
实际上，并归排序也是一个不错的排序方法。不知道对于快速排序和并归排序在实际应用中的效率哪一个好
作者: chiangtp    时间: 2018-6-1 14:56
分享一個 Quick Sorting 的 "簡潔" Fortran code
http://bbs.06climate.com/forum.php?mod=viewthread&tid=32383
作者: chiangtp    时间: 2018-6-1 17:01

優點: 簡單就是美?
缺點: may runtime stack overflow (compiler and array-size dependent),
        Array size越大效率越差 (相對於"正常"coding)
作者: 渡箭    时间: 2018-6-20 20:09
你们都这么niubility



欢迎光临 Fortran Coder (http://bbs.fcode.cn/) Powered by Discuz! X3.2