합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.

Slides:



Advertisements
Similar presentations
서울지하철노조 설립. 1. 전형적 공기업 군사 문화 가 일 개통 1 호선 서울시 공무원으로 운영 일 3.4 호선 건설한 공사와 합병 공무원신분에서 신분변경 나. 공사 내부의 군사 조직과 군사문화 - 공사 사장 감사 이사 ( 별.
Advertisements

YES C 제 1 장 C 언어의 개요 1/34 제 1 장 C 언어의 개요 문봉근. YES C 제 1 장 C 언어의 개요 2/34 제 1 장 C 언어의 개요 1.1 프로그램과 C 언어의 특징 1.2 C 언어의 프로그램 구성 1.3 비주얼 C++ 통합 환경 들어가기.
명품 JAVA Programming 제 3 장 반복문, 배열, 예외처리.
아름다운 이들의 행복한 길음안나의 집.
어서와 Java는 처음이지! 제3장선택과 반복.
Recursion SANGJI University KO Kwangman
제1장 소프트웨어 프로젝트 개요 1.1 프로젝트개요 1.2 프로젝트 유형 1.3 프로젝트 관리의 중요성과 실패 원인
7장 배열 ②.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
자바란 무엇인가? JDK의 다운로드 및 설치 방법 Hello, Java 프로그램의 작성 자바 프로그램의 작동 원리
10장 정렬.
Chapter 02 자바 기본구조 자바 프로그래밍의 기초적인 문법을 소개
알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2
Power Java 제4장 자바 프로그래밍 기초.
Autokey Cipher 자동키 암호 Department of Cyber Security / 박건주.
Choi, Namseok Java 기초 (Java의 제어문과 배열) Choi, Namseok
분할 정복 (Divide-and-Conquer)
CHAP 9 : 정렬.
알고리즘(Algorithm) – Greedy Method (탐욕적 방법)
빠른정렬(Quick Sort) – 개요 (1/2)
DataScience Lab. 박사과정 김희찬 (월)
점화와 응용 (Recurrence and Its Applications)
교육수료증 재발급 사유서 SK하이닉스 이천안전팀 업체 명 : 담당자 (인) 업 체 명 : 이 름 : 서명
제 4주 2014년 1학기 강원대학교 컴퓨터학부 담당교수: 정충교
12 검색.
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
목차 INDEX 1. 회원가입 및 로그인 2. 업체정보 3. 제조검사 신청 4. 인보이스 5. 검사진행현황(현장검사 신청)
어서와 Java는 처음이지! 제4장 배열 IT응용시스템공학과 김형진 교수.
프로그래밍 보고서 작성법 순천향대학교 컴퓨터공학과 하 상 호.
DataScience Lab. 박사과정 김희찬 (월)
Ch.1 Iterator Pattern <<interface>> Aggregate +iterator
Ch.02 Divide and Conquer (분할정복)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
[CPA340] Algorithms and Practice Youn-Hee Han
윤성우의 열혈 C 프로그래밍 윤성우 저 열혈강의 C 프로그래밍 개정판 Chapter 09. C언어의 핵심! 함수!
알고리즘 강의 슬라이드 2 분할정복 분할정복법 도경구역, 알고리즘, 사이텍미디어, 1999.
 Divide and Conquer (분할정복)
Java의 정석 제 4 장 조건문과 반복문 Java 정석 남궁성 강의
프로그래밍 기초와 실습 Chapter 11 Recursion.
자바 5.0 프로그래밍.
 Divide and Conquer (분할정복)
센서값 전송하기 WiFi 시리얼 보드 활용가이드 김영준 헬로앱스 (
업무 메뉴얼 1. 사무용품/소모품 청구의뢰서 작성요령 2. 법인 등기부등본/법인 인감증명 발급 요청서 작성요령
 Divide and Conquer (분할정복)
생체현상계측 ․ 기록장비 이봉준.
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
JVM의 구조와 메모리 모델 JVM의 내부 구조 클래스 파일 클래스 로더 메소드(method) 영역 힙(heap) 영역
과제물 3호 1번 문제 설명자료 엑셀과 파워포인트의 기초 엑셀과 파워포인트를 접해본 적이 없다는 가정하에
정렬(Sorting)과 해싱(Hashing)
제 8 장 계산복잡도 개론 검색 문제 알고리즘 강의 슬라이드 8 검색 문제
빠른정렬(Quick Sort) – 개요 (1/2)
점화와 응용 (Recurrence and Its Applications)
알고리즘 강의 슬라이드 2 분할정복 제 2 장 분할정복 도경구역, 알고리즘, 사이텍미디어, 1999.
코딩체험교실 아두이노 로봇 코딩 4차산업기술 체험 (SW코딩/자율주행기술).
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
1차 발표: 낚였다 !! 학번: 이름: 배상하.
6월 1주 주간메뉴표 NEW 엄마손 조식 쉐프 삼촌 중식 참새 방앗간 석식 ◎원산지 안내 : 쌀(국내산)
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
알고리즘(Algorithm) – Divide and Conquer (분할정복)
자료구조 강의소개 정성훈 연락처 : 이메일 : 연구실 : 연219호 연락처 : 이메일 : 홈페이지: 정성훈.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
DataScience Lab. 박사과정 김희찬 (화)
조 병 규 Software Quality Lab. 한 국 교 통 대 학 교
책을 읽읍시다  탈향 진지하게 설명해드림 1303 김소희 1309박지호 1315이지수.
제 1장 프로그래밍 언어 소개 1.1 프로그래밍 언어란 무엇인가 1.2 프로그래밍 언어를 배워야 하는 이유
빠른정렬(Quick Sort) – 개요 (1/2)
2016년 제1차 운영위원회 평택시건강가정 ∙다문화가족지원센터
알고리즘 강의 슬라이드 7 정렬문제 알고리즘 해석 강의 슬라이드 #7
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
Presentation transcript:

합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오. 입력: 정수 n, 크기가 n인 배열 S[1..n] 출력: (비내림차순으로) 정렬된 배열 S[1..n] 사용 알고리즘: 합병 정렬 (Merge Sorting) 각 단계별로 두 그룹의 정렬된 데이터를 서로 합쳐서 정렬된 더 큰 그룹으로 만들어 나아가는 정렬

합병정렬(Merge Sort) (2/2) 설계 전략 [분할] 배열을 반으로 나누어서 2 개의 부분배열로 분할한다. 각 부분 배열의 크기가 1일 될때까지 계속하여 분할한다. [정복] 가장 작은 수의 인접한 부분 배열 2개로 부터 정렬된 1개의 배열을 얻어낸다. [통합] 정렬된 부분 배열들을 합병하여 하나의 정렬된 배열로 만든다.

합병정렬: 알고리즘 void mergesort (int n, keytype[] S){ if (n > 1) { int h =  n/2 , m = n - h; keytype[] U = new keytype[1..h]; keytype[] V = new keytype[1..m]; copy S[1] through S[h] to U[1] through U[h]; copy S[h+1] through S[n] to V[1] through V[m]; mergesort(h,U); mergesort(m,V); merge(h,m,U,V,S); } nV, hV, mV, UV, VV, SV nU, hU, mU, UU, VU, SU n, h, m, U, V, S S의 크기가 4일 때… 크기 2 크기 2

합병정렬: 합병 문제: 두 개의 정렬된 배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 양의 정수 h, m, (2) 정렬된 배열 U[1..h], V[1..m] (3) 원래의 배열 S[1..h+m] 출력: U와 V에 있는 키들을 하나의 배열에 정렬한 S[1..h+m]

합병정렬: 합병 알고리즘 (1/2) [알고리즘 2.3] (P.55) void merge(int h, int m, keytype[] U, keytype[] V, keytype[] S) { index i, j, k; i = 1; j = 1; k = 1; while (i <= h && j <= m) { if (U[i] < V[j]) { S[k] = U[i]; i++; } else { S[k] = V[j]; j++; } k++; if(i > h)copy V[j] through V[m] to S[k] through S[h+m]; else copy U[i] through U[h] to S[k] through S[h+m]; i=1 j=1 j=2 i=3 j=3 i=5

합병정렬: 합병 알고리즘 (2/2) 알고리즘 2.3 설명 각 서브 그룹당 포인터 한 개씩 필요 (i 와 j) 각 포인터가 가리키는 데이터 두 개를 비교하여 더 작은 것을 S 배열에 복사 복사한 것에 대해서는 포인터를 다음으로 움직임 (i++ or j++) 두 그룹 중 하나는 먼저 처리가 완료되어 포인터가 밖으로 나감 (while (i <= h && j <= m) {…}) 남은 그룹의 데이터를 순서대로 S 배열의 남은 저장공간으로 그대로 복사 (while 절 이후…)

합병정렬: 최악의 경우 시간 복잡도 (1/3) 최악의 경우 [알고리즘 2.3]의 시간 복잡도 분석 단위연산: U[i]와 V[j]의 비교 입력크기: 2개의 입력 배열에 각각 들어 있는 항목의 개수: h, m 분석: i = h이고, j = m인 상태로 루프(loop)에서 빠져 나가는 것이 최악의 경우임 이때, 단위연산 의 실행 횟수는 h + m – 1 이다. 따라서, 최악의 경우 합병하는 시간복잡도는 W(h, m) = h + m – 1

합병정렬: 최악의 경우 시간 복잡도 (2/3) 최악의 경우 [알고리즘 2.2]의 시간 복잡도 분석 단위연산: merge() 함수 입력크기: 배열 S에 들어 있는 항목의 개수 n(=h+m) 분석 1): 최악의 경우 수행시간은 W(n) = W(h) + W(m) + h + m – 1 이 된다. W(h)는 U를 정렬하는데 걸리는 시간 W(m)은 V를 정렬하는데 걸리는 시간, h + m – 1 은 합병하는데 걸리는 시간 정수 n을 2k(k  1)이라고 가정하면, h = m = n/2 이 된다.

합병정렬: 최악의 경우 시간 복잡도 (2/3)   (p.556)    

The Master Theorem (1/4) Proof of the theorem is …. omitted. [부록 B]의 p.564, 정리 B.5 Consider a function f(n) that, for all n=bk for all kZ+, satisfies the recurrence relation: (n=bk 일 때, 다음 점화 관계가 성립하면) f(n) = af(n/b) + cnd with real a≥1, integer b>1, real c>0, d≥0. Then:   Proof of the theorem is …. omitted.

The Master Theorem (2/4)    

The Master Theorem (3/4)    

The Master Theorem (4/4)    

합병정렬: 최악의 경우 시간 복잡도 (3/3)      

[부록 B] P.562

[부록 B] P.562

[부록 B] P.562

합병정렬: 공간 복잡도 (1/3) 그러면 합병정렬 알고리즘은 얼마만큼의 추가적인 저장장소가 필요할까? 함수 mergesort를 호출할 때마다 크기가 S의 절반이 되는 U, V가 추가로 필요. 함수 merge에서는 U와 V가 주소로 전달이 되어 그냥 사용되므로 추가적인 저장장소를 만들지 않는다. 따라서, mergesort를 재귀호출할 때마다 얼마만큼의 추가적인 저장장소가 만들어져야 하는지를 계산해 보면 된다. 처음 S의 크기가 n이면, 추가적으로 필요한 U와 V의 저장장소 크기의 합은 n이 된다. 다음 재귀 호출에는 n/2, 그 다음에는 n/4 등으로 추가적인 저장장소가 필요하다. 이들 저장장소의 크기를 합하면, 이 된다. 이 분석이 맞는 분석일까?...

합병정렬: 공간 복잡도 (2/3) n개 n개 lgn +1 번 n개 n개 = n(lgn +1) 의 저장장소 필요  

합병정렬: 공간 복잡도 (3/3)  

합병정렬: 공간 복잡도 향상 알고리즘 (1/4) 문제: n개의 정수를 (비내림차순으로) 정렬하시오. 입력: (1) 크기가 n인 배열 S[1..n]  전역적으로 정의 (2) low - 배열의 첫번째 인덱스, high – 배열의 마지막 인덱스 출력: (비내림차순으로) 정렬된 배열 S[1..n] void mergesort2 (index low, index high){ index mid; if (low < high) { mid = (low + high) / 2; mergesort2(low, mid); mergesort2(mid+1, high); merge2(low, mid, high); } ... mergesort2(1, n);

합병정렬: 공간 복잡도 향상 알고리즘 (2/4) mergesort2(1,8) mergesort2(1,4)

합병정렬: 공간 복잡도 향상 알고리즘 (3/4) 합병(merge2) 문제: 두 개의 정렬된 부분배열을 하나의 정렬된 배열로 합병하시오. 입력: (1) 전역적으로 선언되어 있는 부분 배열 S[low..high] (단, S[low..mid]와 S[mid+1..high]는 이미 각각 정렬이 완료됨) (2) 첨자 low, mid, high 출력: 정렬이 완료된 부분배열 S[low..high]

합병정렬: 공간 복잡도 향상 알고리즘 (4/4) void merge2(index low, index mid, index high){ index i, j, k; keytype[] U = new keytype[low..high]; i = low; j = mid + 1; k = low; while (i <= mid && j <= high) { if (S[i] < S[j]) { U[k] = S[i]; i++; } else { U[k] = S[j]; j++; } k++; if(i > mid) copy S[j] through S[high] to U[k] through U[high]; else copy S[i] through S[mid] to U[k] through U[high]; copy U[low] through U[high] to S[low] through S[high]; 이 알고리즘이 정말 공간 복잡도를 향상 시키는가?

합병정렬: 공간 복잡도 향상 알고리즘 (4/4) keytype[] U = new keytype[1..n]; void main() { … mergesort2(1,n) … } void mergesort2 (index low, index high){ … merge2(…) … } void merge2(index low, index mid, index high){ index i, j, k; i = low; j = mid + 1; k = low; while (i <= mid && j <= high) { if (S[i] < S[j]) { U[k] = S[i]; i++; } else { U[k] = S[j]; j++; } k++; if(i > mid) copy S[j] through S[high] to U[k] through U[high]; else copy S[i] through S[mid] to U[k] through U[high]; copy U[low] through U[high] to S[low] through S[high];  

[실습 3] 합병 정렬 합병 정렬에 대한 [알고리즘 2.2., 2.3]과 제자리정렬(In-place) 기법인 [알고리즘 2.4, 2.5]를 Java 프로그램으로 작성해보자. SortMain.java 를 분석하기 완성되지 않은 다음 네 함수를 작성한다. public static long mergeSort(int n, int[] s) public static void merge(int h, int m, int[] u, int[] v, int[] s) public static void inPlaceMergeSort(int low, int high) public static void inPlaceMerge(int low, int mid, int high) num 값을 키워가며 각 방법에 대한 수행 시간을 비교한다. 단계별로 num 값을 증가시키면서 수행 시간을 비교해보자. 공간 복잡도를 좋게 만드는 것이 수행시간에도 영향을 미치는가? 그 정도는?