Insertion sort using linked list

linked list를 이용한 insertion sort

PROGRAM insertion_sort

IMPLICIT NONE

TYPE :: int_value
INTEGER :: value
TYPE(int_value), POINTER :: next_value
END TYPE

TYPE(int_value), POINTER :: head
TYPE(int_value), POINTER :: tail
CHARACTER(LEN = 20) :: filename
INTEGER :: istat
CHARACTER(LEN = 40) :: iostatmsg
INTEGER :: nvals = 0
TYPE(int_value), POINTER :: ptr
TYPE(int_value), POINTER :: ptr1
TYPE(int_value), POINTER :: ptr2
INTEGER :: temp

WRITE (*,*) 'Enter the file name with the data to be sorted: '
READ (*,'(A20)') filename

OPEN (UNIT = 9, FILE = filename, STATUS = 'OLD', ACTION = 'READ', IOSTAT = istat, IOMSG = iostatmsg)

IF ( istat == 0 ) THEN ! 파일을 잘 열었다.
DO
READ(9, *, IOSTAT = istat) temp
IF ( istat /= 0 ) EXIT ! 레코드를 잘 못 읽었으면 나가자
nvals = nvals + 1

ALLOCATE(ptr, STAT = istat) ! 이름이 없는 int_value 타입의 data object를 만들고 그걸 ptr이 포인트한다.
IF ( istat /= 0 ) EXIT ! 잘 못 하였으면 나가자
ptr%value = temp ! prt이 point하고 있는 이름 없는 int_value data object의 value component에 값을 저장

IF ( .NOT. ASSOCIATED(head)) THEN ! head pointer가 아무것도 point하고 있지 않다면, 즉 처음으로 자료를 읽었다면
head => ptr ! head가 ptr를 point하라
tail => head ! tail이 head를 point하라
NULLIFY(ptr%next_value) ! prt이 point하고 있는 이름 없는 int_value data object의 next_value component를 확실하게 disassociated상태로 함
ELSE ! 자료를 처음으로 읽는 것이 아니다.
IF (ptr%value < head%value) THEN ! 현재 읽은 자료가 linked list의 맨 처음 자료보다 작다면
ptr%next_value => head ! 현재 ptr의 다음 자료가 head 자료가 되게 함
head => ptr ! 현재 자료를 linked list의 처음으로 함
ELSE IF (tail%value <= ptr%value) THEN ! 현재 자료가 linked list의 맨 끝 자료 즉 최대값보다 크다면
tail%next_value => ptr ! linked list의 끝에 현재 자료를 추가
tail => ptr ! 현재 자료가 linked list의 끝이라는 것을 표시
NULLIFY (tail%next_value) ! linked list의 마지막을 확실히 disassociated 상태로 함
ELSE ! 즉 linked list의 중간에 들어가야 함
ptr1 => head ! ptr1이 linked list의 맨 처음을 point
ptr2 => ptr1%next_value ! ptr2가 linked list의 두 번째 값을 point
DO
IF ((ptr%value >= ptr1%value) .AND. (ptr%value < ptr2%value)) THEN ! 현재 값이 두 임시 값의 사이에 있다면
ptr%next_value => ptr2 ! 현재값의 뒤에 임시 값의 큰 값을 link 하고 즉 두 값 사이에 현재 값을 추가한 것
ptr1%next_value => ptr ! 임시값의 작은 값 뒤에 현재값을 link 하고
EXIT ! DO loop 문을 나가자
END IF ! 현재 값이 두 값 사이에 있지 않다면
ptr1 => ptr2 ! ptr1은 그 다음 값(ptr2)으로 이동
ptr2 => ptr2%next_value ! ptr2를 그 다음 값(ptr2%next_value)으로 이동
END DO
END IF
END IF
END DO

! 자료를 다 읽어 순서대로 linked list를 만들었다면 출력하자
ptr => head ! 임시값이 linked list의 맨 처음 값을 갖는다.
DO
IF (.NOT. ASSOCIATED(ptr)) EXIT ! ptr이 link list의 맨 마지막 값의 next_value이면
WRITE (*,'(1X,I10)') ptr%value
ptr => ptr%next_value
END DO
ELSE ! 파일을 잘 못 열었다.
WRITE (*,'(1X,A,A))') 'File open failed : ', iostatmsg
END IF

END PROGRAM insertion_sort

위 소스를 insertion_sort.f95로 저장

7
2
11
-1
3
2
0

위 자료를 input1.dat로 저장

컴파일 및 프로그램 테스트