Sorting algorithms/Radix sort: Difference between revisions
Content added Content deleted
Line 1,272: | Line 1,272: | ||
! End of LSD sort with any Radix |
! 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 |
* RSORT - sort a list of integers by the Radix Sort algorithm |