병합 정렬 병합 정렬2 석차구하기 가까운 수 구하기 이진검색

Presentation on theme: "병합 정렬 병합 정렬2 석차구하기 가까운 수 구하기 이진검색"— Presentation transcript:

1 병합 정렬 병합 정렬2 석차구하기 가까운 수 구하기 이진검색
6. 정렬과 검색 정렬 선택 정렬 버블 정렬 칵테일 정렬 삽입 정렬 병합 정렬 병합 정렬2 석차구하기 가까운 수 구하기 이진검색

2 정렬(sort) 정렬(Sort)은 데이터를 특정 규칙에 따라 재배열 하는 것 오름차순:작은수 부터 큰 수의 순으로 나열
내림차순:큰 수 부터 작은 수의 순으로 나열

3 정렬(sort) 배열 R에 27, 63, 44, 56, 72, 18, 88, 87 과 같은 숫자열이 입력되어 있다. 배열 R의 값을 오름차순 정렬하여 출력하는 알고리즘을 완성하시오. 제시된 <처리조건>을 참조하여 다음 각 문제의 괄호 안 내용에 가장 적합한 항목을 <답항보기>에서 선택하시오. |처리조건| 1. 배열의 첨자는 0~7로 구성된다. 2. 정렬하는 자료는 100보다 작은 양의 정수로 한다. 3. 알고리즘에 사용되는 변수들은 다음과 같다. - R : 배열 pos：배열 기억 변수 - i, J : 반복변수 min : 최소값

4 정렬(sort)

5 정렬(sort) 100보다 작은 첫 번째 자료부터 비교하여 최소값의 위치를 찾고 그 값을 출력한 후 그 위치의 값을 최대값 100으로 수정한다. 동일한 과정을 자료의 수만큼 반복하여 오름차순으로 정렬한 결과를 출력하는 순서도로 구성.

6 정렬(sort) 오름차순으로 정렬해나가는 과정 Min : 각 단계마다 찾아낸 최소값을 지정
pos : 그 최소값의 위치를 지정.

7 정렬(sort) 알고리즘 시작 초기화 pos=0, R(7) 대상 항 i를 7까지 탐색 대상 항 j를 0부터 7까지 탐색
최초의 최소값 min을 100으로 설정 min=100 배열의 0번째 요소 R(j)와 최소값 비교 R(j)<min 최소값을 R(j)로 설정 min=R(j) 최소값이 나타난 위치 저장 pos=j 최소값 출력 print R(pos) 찾아낸 최소값의 위치에 100을 지정 끝

8 정렬(sort) i 변수 : 정렬단계 지정 J 변수 단계마다 배열요소들 중 최소값 찾기에 사용
변수의 값을 하나씩 증가시켜 7보다 커질 때까지 반복 처리조건에 의하면 배열의 첨자는 0부터 7까지 이므로 0으로 초기화 ① : J=0

9 정렬(sort) min 변수 각 단계마다 최소값을 찾기위해 일단 최대값으로 지정
처리조건에 의하면 자료들이 100보다 작은 양의 정수라 하였으므로 100으로 지정한다. ② : min=100

10 정렬(sort) J번째 배열요소의 자료가 min의 값보다 작은 경우 ③ : R(J)<min
그때의 위치 J를 pos 변수에 지정 ⑤ : pos=J

11 정렬(sort) 단계마다 최소값은 pos 번째 자료 R(pos)의 내용을 출력 ⑥ : R(pos)
비교 대상에서 제외하기 위해 다음 단계의 최소값을 찾기 위해 i 변수의 값을 하나 증가시켜 반복을 계속.

12 정렬(sort) 시작 pos=0, R(j) 반복 i=0,7,1 min=100 반복 j=0,7,1 R(j)<min
No R(j)<min Yes min=R(j) pos=j R(pos) R(pos)=100 끝

13 정렬(sort) - 연습문제 다음은 배열 R에 자료들을 입력받아 내림차순으로 출력하는 알고리즘이다. 제시된 <처리조건>을 참조하여 다음 각 문제의 괄호 안 내용에 가장 적합한 항목을 <답항보기>에서 선택하시오. |처리조건| 1. 정렬하는 자료는 0보다 큰 양의 정수로 한다. 2. read R(i), i=1,10 10개의 자료가 R 배열에 1번째 원소부터 10번째 원소까지 차례대로 입력됨을 나타낸다. 3. 알고리즘에 사용되는 변수들은 다음과 같다. - R(10) : 배열 pos：최소값 위치 변수 - i, J : 반복변수 max : 최대값

14 정렬(sort) - 연습문제

15 정렬(sort) - 연습문제 알고리즘 시작 초기화 R(10) 배열에 자료입력 read R(i)
배열의 최대값 Max=0으로 설정 대상 항 j를 1부터 10까지 탐색 배열의 0번째 요소 R(j)와 최대값 비교 R(j)>Max 최대값을 R(j)로 설정 Max=R(j) 최대값이 나타난 위치 저장 pos=j 최대값 출력 print R(pos) 찾아낸 최대값의 위치에 0을 지정 끝

16 정렬(sort) - 연습문제 시작 pos=0 read R(i) 반복 i=1,10,1 Max=0 반복 j=1,10,1
No R(j)>Max Yes Max=R(j) pos=j R(pos) R(pos)=0 끝

17 선택 정렬(Selection Sort) N개의 DATA를 입력받아 Selection Sort를 이용하여 오름차순으로 정렬한 후, 출력하는 알고리즘이다. 제시된 <처리조건>을 참조하여 다음 <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항보기>에서 선택하시오. |처리조건| 1. READ A(i), i = 1, N N개의 자료가 A 배열에 첫 번째 원소부터 N 번째 원소까지 차례로 입력됨을 나타낸다. 2. 알고리즘에 사용되는 변수 등은 다음과 같다. - A(N) : N 개의 DATA가 입력될 배열 변수 - Temp : SWAP을 위한 임시 변수 - i : 인덱스 변수 J : 인덱스 변수

18 선택 정렬(Selection Sort) 정보처리산업기사 2005년 4회(10.23)

19 선택 정렬(Selection Sort) 선택 정렬(Selection sort)
주어진 파일에서 최소값을 갖는 데이터를 찾아 첫 번째 데이터와 자리를 교환하고, 두 번째부터 마지막 데이터 중에서 최소값의 데이터를 찾아 두 번째 데이터와 자리를 교환한다. 이러한 과정을 (N-1) 번째로 작은 데이터를 찾을 때까지 반복하면서 정렬을 완성한다. 전체적으로 (N-1) 단계를 반복 수행하게 된다.

20 선택 정렬(Selection Sort) 오름차순으로 선택 정렬

21 선택 정렬(Selection Sort) 알고리즘 시작 초기화 배열 A(N) 입력 read A(N)
반복 i를 1부터 N-1까지 탐색 반복 j를 i+1부터 N까지 탐색 A(i)<=A(j), yes이면 goto 1 no이면 위치교환 temp=A(i) A(i)=A(j) A(j)=temp 반복으로 결과 출력 i=1,N print R(pos) 끝

22 선택 정렬(Selection Sort) 중첩된 반복 구조 바깥쪽 반복 구조 안쪽 반복 구조
i가 1~(N-1) 로 변화하며 (N-1)회 반복 i는 i번째 작은 값이 저장될 배열 위치 안쪽 반복 구조 i번째 데이터를 결정하기 위해 A(i)와 A(J)를 비교 A(J)에는 i+1번째부터 N 번째까지의 배열 요소를 차례대로 지정하면 된다. 따라서 안쪽 반복형 구조의 반복 범위는 J가 i+1부터 N이 될 때가지 반복 수행하도록 지정 ① : J=i+1,N

23 선택 정렬(Selection Sort) 안쪽 반복 구조 A(i)와 A(J)를 비교하여 A(i)가 작은 값이 되어야 한다.
Temp 변수 사용하여 두 값의 위치를 교환 ② : Temp=A(i) ③ : A(i)=A(J) ④ : A(J)=Temp

24 선택 정렬(Selection Sort) 정렬이 완료되면 결과 출력 배열 A(i)를 출력하기 위해 또 하나의 반복을 수행
인덱스 i의 값이 모든 데이터의 위치를 지정해야 하므로 i는 1부터 N까지 반복하도록 지정 ⑤ : i=1,N

25 선택 정렬(Selection Sort)

26 선택 정렬 - 연습문제 다음의 순서도는 배열 A에 기억된 N개의 자료를 내림차순 정렬하는 순서도이다. 제시된 <처리조건>을 참조하여 다음 <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항보기>에서 선택하시오. |처리조건| 1. 알고리즘에 사용되는 변수 등은 다음과 같다. - A : N개의 값을 저장할 배열 - I, J : 배열 인덱스 변수 - N : 데이터 수 - TMP : swap을 위한 임시 변수

27 선택 정렬 - 연습문제

28 선택 정렬 - 연습문제 알고리즘 시작 초기화 배열 A(N) 반복 i를 1부터 N-1까지 탐색 반복 j를 i+1부터 N까지 탐색
A(i)<=A(j), no이면 goto 1 yes이면 위치교환 temp=A(i) A(i)=A(j) A(j)=temp 반복으로 결과 출력 i=1,N print R(pos) 끝

29 선택 정렬 - 연습문제 J=I+1 No A(i)<=A(J) Yes A(i) A(J) j<N

30 버블 정렬(Bubble sort) 제시된 <그림>은 배열 A(10)에 기억된 10개의 수치 데이터에 대하여 버블 정렬(Bubble Sort)을 이용하여 오름차순으로 정렬하는 순서도이다. 제시된 <처리조건>을 참조하여 <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항보기>에서 선택하시오. |처리조건| 1. 알고리즘에 사용되는 변수 등은 다음과 같다. - N : 정렬하고자 하는 수치 데이터의 갯수 - i : 정렬의 회전수를 계산하기 위한 변수 - J : 배열의 첨자 등을 위한 변수 - FLAG : 임의의 회전 작업시 데이터의 교환이 발생하지 않을 경우 비교가 반복되는 것을 방지하기 위한 변수 - TM : 주 변수간의 값을 서로 바꾸기 위한 변수

31 버블 정렬(Bubble sort) 2. 본 문제에서는 FLAG를 설정하여 임의의 회전 작업시 교환이 발생하지 않는다면, 정렬이 완료된 상태로 간주하고 작업을 종료시키기로 한다. 3. 배열의 크기가 10일 경우 배열의 요소는 1부터 10까지 구성되는 것으로 한다. 예를들어, A라는 배열의 크기가 10일 경우 A(10)으로 표시되고, 배열 요소는 A(1)부터 A(10)으로 구현된다고 가정한다.

32 버블 정렬(Bubble sort) 정보처리기사 2006년 1회(4.23)

33 버블 정렬(Bubble sort) 버블 정렬
N개의 데이터에 대하여 첫 번째 데이터부터 시작하여 인접한 2개 데이터씩 비교하며 그 결과에 따라 데이터를 교환한다. 오름차순의 경우 첫 번째 데이터와 두 번째 데이터를 비교하여 작은 데이터를 앞에 놓는다. (둘째:세째),(세째:네째).... 의 순으로 계속해서 (N-1) 번째와 N 번째 데이터를 비교 : 1회전 가장 큰 데이터가 N 번째에 위치하게 된다. 첫 번째 데이터로부터 (N-1) 번째 데이터까지 위와 같은 작업을 반복하면 두 번째 큰 값이 (N-1)번째에 위치 이러한 과정을 반복하여 (N-1) 회전, 즉 첫 번째와 두 번째 데이터를 비교하는 것으로 작업이 끝난다.

34 버블 정렬(Bubble sort) 버블 정렬 : 5개의 입력 데이터 (4, 13, 9, 2, 3)

35 버블 정렬(Bubble sort) 알고리즘 시작 배열의 크기 N=10 초기값 i=0, flag=0 i=i+1 j=0 j=j+1
크기비교 A(j)>A(j+1) no이면 goto 10 yes이면 자리바꿈 TM=A(j), A(j)=A(j+1), A(j+1)=TM 자리바꿈이 있으면 flag=1 단계 비교 종료 조건 j>=(N-i) no이면 goto 6 yes이면 i>=(N-1) yes이면 goto 13 no이면 flag==0 no이면 goto 4 끝

36 버블 정렬(Bubble sort)

37 버블 정렬(Bubble sort)

38 버블 정렬(Bubble sort) - 연습문제
제시된 <그림>은 배열 R(10)에 기억된 10개의 수치 데이터에 대하여 버블 정렬(Bubble Sort)을 이용하여 오름차순으로 정렬하는 순서도이다. 제시된 <처리조건>을 참조하여 <그림>의 괄호 안 내용에 가장 적합한 항목을 <답항보기>에서 선택하시오. |처리조건| 1. 알고리즘에 사용되는 변수 등은 다음과 같다. - N : 정렬하고자 하는 수치 데이터의 개수 - K : 정렬의 회전수를 계산하는 변수 - i : 배열의 첨자 등을 위한 변수 - FLAG : 불필요한 비교 반복을 방지하기 위한 변수 - TM : 주 변수간의 값을 서로 바꾸기 위한 변수

39 버블 정렬(Bubble sort) - 연습문제
2. FLAG를 설정하여 임의의 회전 작업시 교환이 발생하지 않는다면, 정렬이 완료된 상태로 간주하고 작업을 종료시키기로 한다.

40 버블 정렬(Bubble sort) - 연습문제
알고리즘 시작 FLAG=TRUE 반복횟수 K=N-1 FLAG==1 NO이면 PRINT R(I),STOP YES이면 FLAG=FALSE 반복 I=1,K,1 크기비교 R(I)>R(I+1) NO이면 GOTO 6 YES이면 자리바꿈 TM=R(I), R(I)=R(I+1), R(I+1)=TM FLAG=1 K=K-1 GOTO 4

41 버블 정렬(Bubble sort) - 연습문제

42 버블 정렬(Bubble sort) - 연습문제
FLAG=1 K R(i+1) 1 K-1

43 삽입정렬(Insertion Sort) 삽입정렬을 이용하여 전산실 직원 20명의 토익점수가 저장되어 있는 배열A(20)의 데이터를 오름차순으로 정렬 처리조건 A(20) : 20개의 데이터가 기억된 배열 Key : 비교 기준이 되는 키 값 저장 변수 i:인덱스 변수 J:인덱스 변수 배열의 요소는 A(1) 부터 A(20)으로 가정

44 삽입정렬(Insertion Sort) 삽입정렬은 첫번째 데이터 부터 하나씩 삽입되며 정렬이 수행
첫번째 데이터의 삽입은 그 자체로 정렬이 완료된 것이므로 실질적인 삽입은 두번째 데이터부터 시작 데이터 순서 17, 6, 15, 2, 8 1단계 2단계 3단계 4단계

45 삽입정렬(Insertion Sort) 알고리즘 시작 시작위치 값 초기화 i=2 시작 위치 값을 Key에 저장 key=A(i)
i-1번째 위치 지정 J=i-1 비교 key < A(j) no이면 goto 9 Yes이면 큰값을 뒤로 삽입 A(J+1) = A(J) 앞쪽 비교위해 J값 수정 J=J-1 맨 앞까지 했는지 비교 J>=1 Yes이면 goto 3 No이면 앞쪽값 위치 지정 A(J+1)=key 다음단계 i=i+1 종료 조건 i>20 no이면 goto 3 Yes이면 End

46 삽입정렬(Insertion Sort) 시작 시작 i=2 반복 i=2,20,1 Key=A(i) Key=A(i) J=i-1
No 반복 j=i-1,1,-1 Key<A(J) Yes No Key<A(J) A(J+1)=A(J) Yes J=J-1 A(J+1)=A(J) Yes J>=1 A(J+1)=key A(J+1)=key i=i+1 끝 No i>20 Yes 끝

47 석차구하기(334p.) 1차원 배열을 이용하여 학생 50명의 성명, 국어점수, 영어점수, 수학점수를 입력받아 총점을 계산하고 계산된 총점으로 석차를 구하여 출력하는 알고리즘이다. |처리조건| NAM(50), K(50), E(50), M(50):성명, 국어점수, 영어점수, 수학점수 배열 SUM(50)총점, RANK 석차, I,J,L 배열첨자 변수 2. 학생의 총점이 높은 순우로 석차를 부여하며, 학생별로 총점이 동일한 경우는 없다고 가정한다.

48 석차구하기 알고리즘 시작 초기화 NAM(50), SUM(50), K(50), E(50), M(50)
입력을 위한 배열 첨자 I=1 입력 READ NAM(I), K(I), E(I), M(I) 총점 구하기 SUM(I)=K(I)+E(I)+M(I) I=I+1 입력종료조건 I<=50 YES이면 GOTO 4 NO이면 석차구하기(J번째 학생) J=1,50,1 순위변수 초기화 RANK=1 J번째 학생의 순위를 위해 마지막학생까지 반복 L=1,50,1 총점비교 SUM(J)<SUM(L) NO이면 GOTO  YES이면(J번째 학생의 점수가 작다면) RANK=RANK+1 출력 PRINT NAM(J), SUM(J), RANK(J) 끝

49 석차구하기 시작 NAM(50), SUM(60), K(50), E(50), M(50) 반복 J=1,50,1 RANK=1 I=1
반복 L=1,50,1 read NAM(I), K(I), E(I), M(I) No SUM(J)<SUM(L) Yes SUM(I)=K(I)+E(I)+M(I) RANK=RANK+1 I=I+1 NAM(J), SUM(J), RANK(J) Yes I<=50 No 끝