Sorting algorithms/Quicksort: Difference between revisions
Content deleted Content added
m →{{header|Java}}: Changed to handle subclasses of E |
added Fortran |
||
Line 190: | Line 190: | ||
dup 2 < if 2drop exit then |
dup 2 < if 2drop exit then |
||
1- cells over + qsort ; |
1- cells over + qsort ; |
||
=={{header|Fortran}}== |
|||
{{Works with|Fortran|90 and later}} |
|||
MODULE Qsort_Module |
|||
IMPLICIT NONE |
|||
CONTAINS |
|||
RECURSIVE SUBROUTINE Qsort(a) |
|||
INTEGER, INTENT(IN OUT) :: a(:) |
|||
INTEGER :: split |
|||
IF(size(a) > 1) THEN |
|||
CALL Partition(a, split) |
|||
CALL Qsort(a(:split-1)) |
|||
CALL Qsort(a(split:)) |
|||
END IF |
|||
END SUBROUTINE Qsort |
|||
SUBROUTINE Partition(a, marker) |
|||
INTEGER, INTENT(IN OUT) :: a(:) |
|||
INTEGER, INTENT(OUT) :: marker |
|||
INTEGER :: left, right, pivot, temp |
|||
pivot = (a(1) + a(size(a))) / 2 ! Average of first and last elements to prevent quadratic |
|||
left = 0 ! behavior with sorted or reverse sorted data |
|||
right = size(a) + 1 |
|||
DO WHILE (left < right) |
|||
right = right - 1 |
|||
DO WHILE (a(right) > pivot) |
|||
right = right-1 |
|||
END DO |
|||
left = left + 1 |
|||
DO WHILE (a(left) < pivot) |
|||
left = left + 1 |
|||
END DO |
|||
IF (left < right) THEN |
|||
temp = a(left) |
|||
a(left) = a(right) |
|||
a(right) = temp |
|||
END IF |
|||
END DO |
|||
IF (left == right) THEN |
|||
marker = left + 1 |
|||
ELSE |
|||
marker = left |
|||
END IF |
|||
END SUBROUTINE Partition |
|||
END MODULE Qsort_Module |
|||
PROGRAM Quicksort |
|||
USE Qsort_Module |
|||
IMPLICIT NONE |
|||
INTEGER, PARAMETER :: n = 100 |
|||
INTEGER :: array(n) |
|||
INTEGER :: i |
|||
REAL :: x |
|||
CALL RANDOM_SEED |
|||
DO i = 1, n |
|||
CALL RANDOM_NUMBER(x) |
|||
array(i) = INT(x * 10000) |
|||
END DO |
|||
WRITE (*, "(A)") "array is :-" |
|||
WRITE (*, "(10I5)") array |
|||
CALL Qsort(array) |
|||
WRITE (*,*) |
|||
WRITE (*, "(A)") "sorted array is :-" |
|||
WRITE (*,"(10I5)") array |
|||
END PROGRAM Quicksort |
|||
=={{header|Haskell}}== |
=={{header|Haskell}}== |