Sorting algorithms/Radix sort: Difference between revisions
Content added Content deleted
Line 1,169: | Line 1,169: | ||
! |
! |
||
! No Copyright is exerted due to considerable prior art in the Public Domain. |
! No Copyright is exerted due to considerable prior art in the Public Domain. |
||
! This Fortran version by Peter Kelly ~ peter.kelly@acm.org |
! This Fortran version by Peter Kelly ~ peter.kelly@acm.org |
||
! |
! |
||
! Permission is hereby granted, free of charge, to any person obtaining |
! Permission is hereby granted, free of charge, to any person obtaining |
||
Line 1,276: | Line 1,276: | ||
! |
! |
||
! No Copyright is exerted due to considerable prior art in the Public Domain. |
! No Copyright is exerted due to considerable prior art in the Public Domain. |
||
! This Fortran version by Peter Kelly ~ peter.kelly@acm.org |
! This Fortran version by Peter Kelly ~ peter.kelly@acm.org |
||
! |
! |
||
! Permission is hereby granted, free of charge, to any person obtaining |
! Permission is hereby granted, free of charge, to any person obtaining |
||
Line 1,295: | Line 1,295: | ||
! SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
! SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. |
||
! |
! |
||
! Implementation of a |
! Implementation of a classic Radix Sort LSD style :) |
||
! Works well, Integers only but it goes faster than a comparison sort |
! Works well, Integers only but it goes faster than a comparison sort |
||
CONTAINS |
CONTAINS |
||
Line 1,355: | Line 1,355: | ||
! End of Classic LSD sort with Radix 10 |
! 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 |
* RSORT - sort a list of integers by the Radix Sort algorithm |