Anonymous user
Sorting algorithms/Radix sort: Difference between revisions
→{{header|Fortran}}
Line 1,272:
! End of LSD sort with any Radix
!***************************************************************************
MODULE LEASTSIG
IMPLICIT NONE
!
! 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.
!
! Implementation of a classi Radix Sort LSD style :)
! Works well, Integers only but it goes faster than a comparison sort
CONTAINS
! Main Radix Sort sort function
SUBROUTINE LSDRADIXSORT(A , N)
IMPLICIT NONE
!
! Dummy arguments
!
INTEGER :: N
INTEGER , target, DIMENSION(0:N - 1) :: A ! All arrays based off zero, one day I'll fix it
INTENT (IN) N
INTENT (INOUT) A
!
! Local variables
!
INTEGER , DIMENSION(0:9) :: counts
INTEGER :: digitplace
INTEGER :: i
INTEGER :: j
INTEGER :: largestnum
INTEGER, DIMENSION(0:N - 1) :: results
!
digitplace = 1 ! Count of the keys
largestnum = MAXVAL(A)
DO WHILE ( (largestnum/digitplace)>0 )
counts = 0 ! Init the count array
DO i = 0 , N - 1 , 1
J = (A(i)/digitplace)
J = MODULO(j , 10)
counts(j) = counts(j) + 1
END DO
! Change count(i) so that count(i) now contains actual position of this digit in result()
! Working similar to the counting sort algorithm
DO i = 1 , 9 , 1
counts(i) = counts(i) + counts(i - 1) ! Build up the prefix sum
END DO
!
DO i = N - 1 , 0 , -1 ! Move from left to right
j = (A(i)/digitplace)
j = MODULO(j, 10)
results(counts(j) - 1) = A(i) ! Need to subtract one as we are zero based but prefix sum is 1 based
counts(j) = counts(j) - 1
END DO
!
DO i = 0 , N - 1 , 1 ! Copy the semi-sorted data into the input
A(i) = results(i)
END DO
!
digitplace = digitplace*10
END DO ! While loop
RETURN
END SUBROUTINE LSDRADIXSORT
END MODULE LEASTSIG
!***************************************************************************
! End of Classic LSD sort with Radix 10
!***************************************************************************
*=======================================================================
* RSORT - sort a list of integers by the Radix Sort algorithm
| |||