신속정렬(Quick Sort)

Quick Sort 방법에 의한 정렬

PROGRAM Main

IMPLICIT NONE

REAL, DIMENSION(:), ALLOCATABLE :: FailureTime
INTEGER :: NumTimes, I, OpenStatus, InputStatus
CHARACTER(20) :: FileName

WRITE (*, '(1X, A)', ADVANCE = "NO") "자료 파일 이름(20자 이내)을 입력하시오 : "
READ *, FileName

OPEN (UNIT = 15, FILE = FileName, STATUS = "OLD", IOSTAT = OpenStatus)

IF (OpenStatus > 0) THEN
STOP "*** 파일을 열 수 없음 ***"
END IF

NumTimes = 0

DO

READ (UNIT = 15, FMT = *, IOSTAT = InputStatus)

IF (InputStatus > 0) THEN
STOP "*** 입력 에러 ***" ! 프로그램 종료하기
END IF

IF (InputStatus < 0) THEN
EXIT ! DO 루프 빠져나가
END IF

! 파일에 들어 있는 데이터 세기
NumTimes = NumTimes + 1

END DO

REWIND(UNIT = 15)

ALLOCATE(FailureTime(NumTimes))

DO I = 1, NumTimes

READ (UNIT = 15, FMT = *, IOSTAT = InputStatus) FailureTime(I)

IF (InputStatus > 0) THEN
STOP "*** 입력 에러 ***" ! 프로그램 종료하기
END IF

IF (InputStatus < 0) THEN
EXIT ! DO 루프 빠져나가
END IF

END DO

CLOSE(15)

PRINT *, FailureTime

PRINT *, "Sorting ..."
PRINT *,

CALL QuickSort(FailureTime,1, NumTimes)

PRINT *, FailureTime

CONTAINS

RECURSIVE SUBROUTINE QuickSort(Item, First, Last)

REAL, DIMENSION(:), INTENT(INOUT) :: Item
INTEGER, INTENT(IN) :: First, Last
INTEGER :: Mid

IF (First < Last) THEN
Call Split(Item, First, Last, Mid)

Call QuickSort(Item, First, Mid - 1)
Call QuickSort(Item, Mid + 1, Last)
END IF
END SUBROUTINE QuickSort

SUBROUTINE Split(Item, Low, High, Mid)

REAL, DIMENSION(:), INTENT(INOUT) :: Item
INTEGER, INTENT(IN) :: Low, High
INTEGER, INTENT(OUT) :: Mid
INTEGER :: Left, Right
REAL :: Swap, Pivot

Left = Low
Right = High
Pivot = Item(Low)

DO
IF (Left >= Right) EXIT

DO
IF (Left >= Right .OR. Item(Right) < Pivot) EXIT
Right = Right - 1
END DO

DO
IF (Left >= Right .OR. Item(Left) > Pivot) EXIT
Left = Left + 1
END DO

IF (Left < Right) THEN
Swap = Item(Left)
Item(Left) = Item(Right)
Item(Right) = Swap
END IF

END DO

Item(Low) = Item(Right)
Item(Right) = Pivot
Mid = Right

END SUBROUTINE Split

END PROGRAM Main

위 소스를 08_06_QuickSort.f95로 저장

정렬할 자료

99.5
133.8
84.2
217.5
188.8
103.1
93.9
165.0
68.3
111.
88.8
88.2
90.1
70.2
150.5
122.9
138.8
99.9
111.6
155.7
133.4
122.2
93.4
101.5
109.9
103.3
177.7
188.1
99.8
144.4
87.5
79.3
190.2
190.3
170.1
160.9
121.1
95.6
140.5
177.2
150.1
140.3
139.2
113.8
155.9
144.4
88.3
83.5
101.1
112.8

위 자료를 08_01_Failure.dat로 저장

소스 컴파일 및 프로그램 테스트