Sorting algorithms/Radix sort: Difference between revisions
Content added Content deleted
m (→{{header|Tailspin}}: Must mark counting numbers as scalars) |
|||
Line 1,164: | Line 1,164: | ||
=={{header|Fortran}}== |
=={{header|Fortran}}== |
||
<lang 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 |
* RSORT - sort a list of integers by the Radix Sort algorithm |