www.gisa79.com
105
19 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 정렬 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 3: 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 삽입 정렬 (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort) (Insertion Sort)
삽입 정렬
1.
명의 학생 성적을 입력받아 배열에 저장한 후 저장된 자료를 오름차순으로 정렬하는 순서도 5
를 작성하시오
알고리즘에 사용되는 변수는 다음과 같다.
▸
정렬할 숫자가 저장될 배열 - A(5):
- i: 정렬회전수와 동시에 KEY값의 위치를 지정해주는 변수 즉, i는 2부터 5까지 차례로 변경
비교값의 위치 지정 변수 - J:
기준값을 저장하기 위한 변수 - KEY:
분 석
두 번째 자료
▸ (기준값=KEY)부터 시작해서 그 앞 왼쪽 의 자료들( ) (비교값)과 비교하여 삽입할 위치를 지정 한 후 자료 비교값 를 뒤로 옮기고, ( ) ,
지정한 자리에 자료를 삽입하여 정렬하는 방식 자료는 자료와
2nd 1st
▸
자료는 자료와
3rd 1st, 2nd
자료는 자료와
4th 1st, 2nd, 3rd
자료는 자료와 비교한 후 자료가 삽입될 위치를 찾는다
5th 1st, 2nd, 3rd, 4th .
자료가 삽입될 위치를 찾았으면 그 위치에 자료를 삽입하기 위해
▸
자료를 한 칸씩 뒤 오른쪽 로 이동시킨다( ) . 작은 값을 찾는 검색과정이 필요없음.
▸
www.gisa79.com
107
알고리즘 작성디 버 깅
배열 A에 100, 70, 90, 80, 90이 저장되었을 경우 )
▸
100 70 90 80 90
A(1) A(2) A(3) A(4) A(5)
i J KEY
2 1 70 100 90 80 90 70
3 2 1→ 70 90 100 80 90 90
4 3 2 1→ → 70 80 90 100 90 80
5 4 3 2 1→ → → 70 80 90 90 100 90
문 제
제시된 <그림 은 학생> 20명의 토익성적을 입력받아 오름차순으로 정렬하는 순서도 입니다. <그림 의 괄호>
안 내용에 가장 적절한 항목을 <답항보기 에서 선택>
하여 답안지의 해당번호 (1)~(5)에 마크 하시오. (이 정렬은 삽입정렬을 이용하였다.)
처리조건
< >
사용되는 변수는 다음과 같다
- .
TOE(20) : 20 개의 데이터가 기억된 배열 i : 정렬회전수와 동시에
값의 위치를 지정해주는 변수 Key
즉, i는 2부터 20까지 차례로 변경. J : 입력 받은 숫자의 개수가 저장될 변수 Key : key값이 삽입될 위치를 지정할 변수
배열의 크기가 일 경우 배열의 요소는 부터
- 20 1 20
까지 구성되는 것으로 한다 예를 들어. , TOE 라는 배열의 크기가 20일 경우 TOE(20)으로 표시되고, 배열 요소는 TOE(1) 부터 TOE(20) 으로 구현된다 고 가정한다.
그림 의 순서도에서 마름모의 의미는 마름모 안의 - < >
두 항목을 상호 비교하여 해당 조건에 따라 순서도 의 흐름이 분기되도록 하는 역할을 한다.
- 선택정렬 알고리즘이 정렬되지 않은 데이터 가운데 가장 작은 값을 찾아서 정렬하는 형태의 정렬방식이라 면 삽입 정렬 알고리즘, (Insert Sort Algorithm)은 작 은 값을 찾는 검색 과정이 필요 없는 정렬 알고리즘.
순차적으로 정렬하면서 현재의 값을 정렬된 값들과 -
비교하여 적당한 위치에 삽입하는 방식.
www.gisa79.com
109
답항 보기1 1 2 2 3 Key-1 4 i-1 5 i+1
6 19 7 >= 8 TOE(Key-1) 9 J-1 10 J+1
11 J 12 = 13 Key+1 14 TOE(Key) 15 i=i+2
16 J-2 17 <> 18 3 19 i+19 20 i+20
21 TOE(i+1) 22 TOE(i-1) 23 Index 24 TOE 25 i<>i+1
26 TOE(J+1) 27 TOE(J-1) 28 Key 29 Key+2 30 i<=19
31 i-2 32 YES 33 J<>1 34 Key-2 35 TOE(J)
36 i 37 No 38 20 39 0 40 TOE(i)
디 버 깅
