자료처리교안

소개글

자료처리교안에 대한 보고서 자료입니다.

목차

Ⅰ자료처리 이론
Ⅰ). 자료 처리의 개념
2 ). 자료 처리의 과정
3 ). 자료 처리의 방식
4 ). 자료의 관리와 전산실

2. 자료구조의 개요
1) 배열과 레코드
2) 연결 리스트
3) 스택과 큐
4) 트리와 그래프
5) 검색과 정렬

본문내용

: n(n-1) / 2
⑥ 연산 시간 : O(n2)
예) 데이터 7, 4, 5, 9, 6의 정렬(오름 차순 정렬)
초기 상태 :
7
4
5
9
6
1회전 :
7
4
5
9
6
→
4
7
5
9
6
첫 번째 데이터 7과 나머지 4, 5, 9, 6을 비교하면서 작은 데이터를 첫 번째 자리에 넣는 과정을 반복하면
가장 작은 데이터 4가 첫 번째에 채워짐.
2회전 :
4
7
5
9
6
→
4
7
5
9
6
두 번째 데이터 7과 나머지 5, 9, 6을 비교하면서 작은 데이터를 두 번째 자리에 넣는 과정을 반복하면
가장 작은 데이터 5가 두 번째에 채워짐
3회전 :
4
7
5
9
6
→
4
5
6
9
7
세 번째 데이터와 나머지를 비교하여 가장 작은 데이터를 세 번째에 넣음.
4회전 :
4
5
6
7
9
→
4
5
6
7
9
◆ 선택 정렬은 1회전을 수행하고 나면 가장 작은값의 레코드가 맨 처음에 위치함.
예) 데이터 [ 6, 5, 7, 4, 3 ]을 선택 정렬
단계
교환 데이터
정렬 상태
1회
2회
3회
4회
3 ↔ 6
4 ↔ 5
5 ↔ 7
6 ↔ 7
3 5 7 4 6
3 4 7 5 6
3 4 5 7 6
3 4 5 6 7
▣ 휩 정렬(Heap Sort = Tree Sort) ⇒ 선택법
① 주어진 레코드를 휩트리로 구성한 후 근노드를 제거
② 나머지 트리가 다시 휩트리가 되도록 구성한 후 근노드 제거를 반복
▶ 휩트리 : 부노드 값이 자노드 값보다 작지 않은 전 이진 트리
③ 트리 정렬이라고도 함.
④ 메모리 사용 공간 : S=n+pointer
⑤ 연산 시간 : O(nlog2n)
▣ 차시 과제
● 삽입정렬의 개념과 특징에 대하여 조사 해오기
● 삽입정렬의 알고리즘에 대하여 알아오기
◈ 삽입 정렬(Insertion Sort) ⇒ 삽입법
▣ 본시 학습 목표 ( 9 / 9 )
● 삽입 정렬의 개념과 특징에 대하여 안다.
● 삽입 정렬의 알고리즘에 대하여 안다.
① 한 개의 레코드로부터 시작해서 차례로 삽입
② 다음 레코드가 삽입될 때 마다 이미 들어 있는 레코드와 비교하여 이동 후 삽입.
③ 부분적으로 정렬되어 있는 경우에 효율적임.
④ 삽입된 위치 이후의 레코드들은 한 레코드씩 뒤로 이동되어야 하므로, 시간과 경비를 낭비하게 되는 단점.
⑤ 메모리 사용 공간 : S=n
⑥ 최대 비교 횟수 : n(n-1) / 2
⑦ 최소 비교 횟수 : (n-1)
⑧ 평균 비교 횟수 : n(n-1) / 4
⑨ 연산 시간 : O(n2)
⑩ 예.
n=5 인 경우의 입력 레코드를 ( 5, 3, 2, 4, 1 )이라 할 때 삽입 정렬
초기 상태 :
5,
3,
2,
4,
1
j = 2 :
3,
5,
2,
4,
1,
j = 3 :
2,
3,
5,
4,
1
j = 4 :
2,
3,
4,
5
1
j = 5 :
1,
2,
3,
4,
5
예) 데이터 6, 3, 4, 9, 8의 정렬(오름 차순 정렬)
초기 상태 :
6
← 첫 번째 레코드 삽입
1회전 :
3
6
← 두 번째 레코드 3과 6을 비교하여 작은 데이터를 삽입.
2회전 :
3
4
6
← 세 번째 레코드 4와 3을 비교한 후 다시 6과 비교하여 작은 데이터를 삽입.
3회전 :
3
4
6
9
← 네 번째 레코드 9와 다른 레코드와 비교한 후 작은 데이터를 제일 뒤에 삽입.
4회전 :
3
4
6
8
9
← 다섯 번째 레코드 8과 다른 레코드와 비교한후 작은 데이터를 6과 9사이에 삽입.
셀 정렬(Shell Sort) ⇒ 삽입법
① 삽입 정렬의 확대개념으로 수행 능력이 우수
( 삽입 정렬방식 보다 수행 속도 빠름)
② 일정한 매개 변수에 따라 여러개의 부파일로 간주하여 삽입 정렬로 배열
③ 매개 변수가 1일 때 끝남
④ 평균 수행 시간 : O(n2)
☞ 셀 정렬의 매개 변수
: 여러개의 서브 파일을 형성하기 위한 매개 변수값(즉, 간격)은 점점작게하여 간격이 1일 때 정렬이 완료됨.
⑤ 예. 8, 5, 6, 9, 7을 셀 정렬로 정렬(단, 매개변수= {1,2,3})
⑴ 매개 변수가 3일 때, 3칸씩 띄어서 8과 9, 5와 7, 6을 삽입.
1회전 :
8
5
6
9
7
(변화없음)
⑵ 매개 변수가 2일 때, 2칸씩 띄어서 8과 6과 7, 5와 9를 비교 후 삽입.
2회전 :
6
5
7
9
8
(8, 6, 7 교환)
⑶ 매개 변수가 1일 때, 모두 비교 후 삽입
3회전 :
5
6
7
8
9
(6, 5 교환, 9, 8 교환)
기수 정렬(Radix Sort) ⇒ 분배법
① 다중키 정렬, 진법 변환 정렬, 버킷 정렬, 스캐터 정렬이라고도 함.
② 데이터를 자릿수별로 나누어 각 해당큐( 또는 스택)에 넣고 그것을 다시 정렬하여 자릿수만큼 반복.
③ 따라서 진법에 따라 그 수만큼 버킷을 준비한다.
④ 메모리 사용 공간 : S=(n+1)q ▶q= Queue의 수
⑤ 평균 수행 시간 : O(k(n+q)) ▶q= Queue의 수, k=digit 수
2-웨이 머지 정렬(2-way merge Sort) ⇒ 병합법
① 이미 순서 배열된 두 개의 파일을 병합하여 하나의 정렬된 파일로 만드는 정렬 방식.
② 수행시간 : O(nlog2n)
③ 메모리 사용 공간 : S=2n
④ 전체 수행 단계 횟수(패스 횟수) : log2n
◈ 외부 정렬
: 보조 기억 장치를 이용한 정렬 방식
1) K-웨이 머지 정렬(K-way merge sort)
▶ 완전히 순서 배열된 K개의 파일을 1개의 파일로 합침.
▶ 디스크장치를 이용하여 머지함.
2) 밸런스드 머지 정렬(Balanced merge sort)
▶ 테이프장치를 이용하여 정렬함.
▶ 2K개의 테이프가 필요(K개는 입력, K개는 출력용)
▶ 최소한 3개의 테이프가 필요
▶ 최저 2-way로 운영
3) 폴리페이즈 머지 정렬 (Polyphase merge sort)
▶ 피보나치 수열을 이용하여 머지함.
▶ 다상 정렬이라고도 함.
4) 캐스캐이드 머지 정렬(Cascade merge sort)
▶ 여러개의 테이프를 한꺼번에 처리하다가 그 중 1개의 테이프가 끝나면 멈추는 방식.
5) 오실레이팅 머지 정렬 (Oscillating merge sort)
▶ 테이프의 역으로 읽는 방식을 이용하여 머지함.
◆ 모든 머지는 외부 정렬이지만 머지를 생략하여 부르기도 함.

키워드

전산교육,   자료처리,   교안,   교안서,   컴퓨터교육,   전산실습