Anonymous user
Sorting algorithms/Radix sort: Difference between revisions
→{{header|Fortran}}
Line 1,169:
!
! 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
Line 1,276:
!
! 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
Line 1,295:
! SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
!
! Implementation of a
! Works well, Integers only but it goes faster than a comparison sort
CONTAINS
Line 1,355:
! End of Classic LSD sort with Radix 10
!***************************************************************************
!Superfast FORTRAN LSD sort
! Dataset is input array, Scratch is working array
!
SUBROUTINE FASTLSDRAD(Dataset , Scratch , Dsize)
!
! 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.
!
! This LSD sort is optimized to a base 16,Radix 256 sort which is about as fast as LSD gets. As well as a fast
! algorithm, it has great cache coherency so performs exceptionally on large data sets,
! I have optimized out all the divide and modulus functions and replaced them with bit shifts for speed.
! A further speed optimization is obtained by using pointers to the DATA and TEMP arrays and swapping them each pass of
! the LSB calculation. In FORTRAN this is a bit clunky but much faster than copying data back and forth between arrays.
!
! All arrays are zero based as this makes the indexing calculations straightforward without the need for
! subsequent adds and subtracts to track the correct index
! .
IMPLICIT NONE
!
! Dummy arguments
!
INTEGER :: Dsize
INTEGER , TARGET , DIMENSION(0:Dsize - 1) :: Scratch ! Declared as TARGET as we will manipulate with pointers
INTEGER , TARGET , DIMENSION(0:Dsize - 1) :: Dataset
INTENT (IN) Dsize
INTENT (INOUT) Scratch , Dataset
!
! Local variables
!
INTEGER , POINTER , DIMENSION(:) :: a ! The pointer to the data
INTEGER , POINTER , DIMENSION(:) :: b ! The pointer to the buffer
INTEGER :: i
INTEGER :: j
INTEGER :: m
INTEGER , DIMENSION(0:255,0:3) :: stats_table
INTEGER :: n
LOGICAL :: swap
INTEGER :: u
!
stats_table = 0 ! index matrix
swap = .TRUE. ! For swapping pointers
!
a => Dataset
b => Scratch
!
DO i = 0 , Dsize - 1 , 1 ! generate histograms
u = a(i)
DO j = 0 , 3 , 1
n = IAND(u , z'FF')
u = SHIFTR(u , 8)
stats_table(n,j) = stats_table(n,j) + 1
END DO
END DO
!
DO i = 0 , 3 , 1 ! convert to indices
m = 0
DO j = 0 , 255 , 1
n = stats_table(j , i)
stats_table(j , i) = m
m = m + n
END DO
END DO
!
DO j = 0 , 3 , 1 ! Radix Sort, sort by LSB
DO i = 0 , Dsize - 1 , 1
u = a(i)
m = IAND(SHIFTR(u,SHIFTL(j,3)) , z'FF') ! Eliminate the MOD 16 and div with shifts
b(stats_table(m,j)) = u ! Push the data into the buffer
stats_table(m,j) = stats_table(m,j) + 1
END DO
!
! Instead of copying back from the temp values swap the array pointers
!
IF( swap )THEN
a => Scratch ! A now points to the b buffer
b => Dataset ! B now is the data set
ELSE
a => Dataset
b => Scratch
END IF
swap = .NOT.swap ! Set to swap back and forth every pass
END DO
!
RETURN
END SUBROUTINE FASTLSDRAD
!***************************************************************************
! End of Superfast LSD sort
!***************************************************************************
*=======================================================================
* RSORT - sort a list of integers by the Radix Sort algorithm
| |||