Anonymous user
Sorting algorithms/Radix sort: Difference between revisions
→{{header|Fortran}}
m (→{{header|Tailspin}}: Must mark counting numbers as scalars) |
|||
Line 1,164:
=={{header|Fortran}}==
<lang Fortran>
SUBROUTINE VARRADIX(A , Siz)
!
! No Copyright is exerted due to considerable prior art in the Public Domain.
! This Fortran version by Peter Kelly ~ peter.kelly@acm.org
!
! Permission is hereby granted, free of charge, to any person obtaining
! a copy of this software and associated documentation files (the
! "Software"), to deal in the Software without restriction, including
! without limitation the rights to use, copy, modify, merge, publish,
! distribute, sublicense, and/or sell copies of the Software, and to
! permit persons to whom the Software is furnished to do so, subject to
! the following conditions:
! The above copyright notice and this permission notice shall be
! included in all copies or substantial portions of the Software.
! THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
! EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
! MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
! IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
! CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
! TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
! SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
!
!
! LSD sort with a configurable RADIX, Using a RADIX of 256 performs well, hence I have defaulted it in. It is snarly fast.
! It could be optimized by merging the two routines but this way gives greater clarity as to what's going on.
IMPLICIT NONE
!
! PARAMETER definitions
!
INTEGER , PARAMETER :: BASE = 256 ! whatever base you need, just change this
!
! Dummy arguments
!
INTEGER :: Siz
INTEGER , DIMENSION(Siz) :: A
!
! Local variables
!
INTEGER , ALLOCATABLE , DIMENSION(:) :: b
INTEGER , ALLOCATABLE , DIMENSION(:) :: c
INTEGER :: exps
INTEGER :: maxs
!
ALLOCATE(b(Siz))
ALLOCATE(c(BASE))
exps = 1
maxs = MAXVAL(A)
DO WHILE ( (maxs/exps)>0 )
CALL XXCOUNTING_SORT(A , Siz , exps , BASE , b , c)
exps = exps*BASE
END DO
deallocate(C)
deallocate(B)
RETURN
CONTAINS
!
!//b is the base you want
!//exp is the value used for the division
SUBROUTINE XXCOUNTING_SORT(A , Siz , Exps , Base , B , C)
IMPLICIT NONE
! I used zero based arrays as it made the calcs infinitely easier :)
!
! Dummy arguments
!
INTEGER :: Base
INTEGER :: Exps
INTEGER :: Siz ! Size
INTEGER , DIMENSION(0:) :: A
INTEGER , DIMENSION(0:) :: B
INTEGER , DIMENSION(0:) :: C
INTENT (IN) Base , Exps , Siz
INTENT (INOUT) A , B , C
!
! Local variables
!
INTEGER :: i
INTEGER :: k
!
C = 0 ! Init the arrays
B = 0
!
DO i = 0 , Siz - 1 , 1
k = MOD((A(i)/Exps) , Base) ! Fill Histo
C(k) = C(k) + 1
END DO
!
DO i = 1 , Base - 1 , 1
C(i) = C(i) + C(i - 1) ! Build cumulative Histo
END DO
!
DO i = Siz - 1 , 0 , -1
k = MOD(A(i)/Exps , Base) ! Load the Buffer Array in order
B(C(k) - 1) = A(i)
C(k) = C(k) - 1
END DO
!
DO i = 0 , Siz - 1 , 1 ! Copy across
A(i) = B(i)
END DO
RETURN
END SUBROUTINE XXCOUNTING_SORT
END SUBROUTINE Varradix
!***************************************************************************
! End of LSD sort with any Radix
!***************************************************************************
*=======================================================================
* RSORT - sort a list of integers by the Radix Sort algorithm
| |||