CHAP 9: 정렬 (part 2) 2016. 11. 17 순천향대학교 컴퓨터학부 하 상 호.

Slides:



Advertisements
Similar presentations
6 장. printf 와 scanf 함수에 대한 고찰 printf 함수 이야기 printf 는 문자열을 출력하는 함수이다. – 예제 printf1.c 참조 printf 는 특수 문자 출력이 가능하다. 특수 문자의 미 \a 경고음 소리 발생 \b 백스페이스 (backspace)
Advertisements

1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
출석수업 과제 – 총 5문제, 10월 25일 제출 정보통계학과 장영재 교수.
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
Chapter 10. 정렬 Chapter 10-1: 단순한 정렬 알고리즘.
분할 정복 (Divide-and-Conquer)
CHAP 9 : 정렬.
정보보안 프로젝트 (Sort Algorithm) 학 부 : 컴퓨터 정보공학부, 네트워크 정보 공학부
자료구조론 11장 정렬(sort).
Chapter 02 순환 (Recursion).
빠른정렬(Quick Sort) – 개요 (1/2)
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Heesang kim PL/SQL 3 Heesang kim.
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
8장 함수 함수의 필요성 라이브러리 함수와 사용자 정의 함수 함수의 정의, 원형, 호출 배열을 함수 인자로 전달 재귀호출.
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express Slide 1 (of 32)
6장. printf와 scanf 함수에 대한 고찰
자료구조: CHAP 4 리스트 (1) 순천향대학교 컴퓨터공학과 하 상 호.
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
프로그래밍 랩 – 7주 리스트.
11장. 1차원 배열.
정렬과 합병.
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 44).
Introduction To Data Structures Using C
CHAP 10:그래프 (2) 순천향대학교 하상호.
11 정렬.
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
3장 상수 변수 기본 자료형 키워드와 식별자 상수와 변수 기본 자료형 형변환 자료형의 재정의.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
Term Projects 다음에 주어진 2개중에서 한 개를 선택하여 문제를 해결하시오. 기한: 중간 보고서: 5/30 (5)
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
5강. 배열 배열이란? 배열의 문법 변수와 같이 이해하는 배열의 메모리 구조의 이해 레퍼런스의 이해 다차원 배열
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
계산기.
객체기반 SW설계 팀활동지 4.
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
데이터 동적 할당 Collection class.
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
자료구조론 12장 검색(search).
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
Homework #12 (1/2) 프로그램을 작성하고, 프로그램과 실행 결과를 프린트하여 제출한다.
빠른정렬(Quick Sort) – 개요 (1/2)
7주차: Functions and Arrays
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
Chapter 10 데이터 검색1.
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
동적메모리와 연결 리스트 컴퓨터시뮬레이션학과 2016년 봄학기 담당교수 : 이형원 E304호,
수치해석 ch3 환경공학과 김지숙.
제 29 강 스트링(string) 다루기 s a i s . s T i h t g r i n.
빠른정렬(Quick Sort) – 개요 (1/2)
Report #2 (기한: 3/16) 데이터 구조 과목의 수강생이 50명이라고 가정한다. 이 학생(학번은 2016????으로 표현됨)들의 중간 시험(0~100), 기말 시험(0~100) 성적을 성적 파일에 작성하라(프로그램을 통해서 또는 수작업으로). 성적 파일을 읽어들여서.
C++ Espresso 제15장 STL 알고리즘.
BoardGame 보드게임 따라가기.
Presentation transcript:

CHAP 9: 정렬 (part 2) 2016. 11. 17 순천향대학교 컴퓨터학부 하 상 호

Remind: 다음 정렬 방법을 비교하시오. 알고리즘의 복잡도는? 더 나은 정렬 알고리즘은? 선택정렬 삽입정렬 버블정렬 쉘 정렬 더 나은 정렬 알고리즘은?

합병정렬 개념 합병정렬은 분할과 정복기법에 기반 리스트를 두 개의 균등한 크기로 분할하고, 분할된 각 부분 리스트를 정렬하고, 2개의 정렬된 부분 리스트를 합병하는 방법

분할정복법 분할정복법(divide and conquer)은 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다. 분리된 문제가 아직도 해결하기 어렵다면, 즉 충분히 작지 않다면 분할정복방법을 다시 적용한다. 이는 재귀호출을 이용하여 구현된다. 1. 분할(Divide): 배열을 같은 크기의 2개의 부분 배열로 분할한다. 2. 정복(Conquer): 부분배열을 정렬한다. 부분배열의 크기가 충분히 작지 않으면 재귀호출을 이용하여 다시 분할정복기법을 적용한다. 3. 결합(Combine): 정렬된 부분배열을 하나의 배열에 통합한다. 입력파일: 27 10 12 20 25 13 15 22 1.분할(Divide): 배열을 27 10 12 20 과 25 13 15 22의 2개의 부분배열로 분리 2.정복(Conquer): 부분배열을 정렬하여 10 12 20 27 과 13 15 22 25를 얻는다. 3.결합(Combine): 부분배열을 통합하여 10 12 13 15 20 22 25 27을 얻는다.

합병정렬의 전체과정

합병정렬 알고리즘 merge_sort(list: array of integers, left, right: integer) if (left < right) then mid = (left+right)/2; merge_sort(list, left, mid); merge_sort(list, mid+1, right); merge(list, left, mid, right); endif end merge_sort 합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것 merge() 알고리즘은?

merge(): 합병과정 임시 배열 sorted 사용 2개 배열로부터 원소를 작은 순서대로 sorted에 이동 어느 한 개의 리스트가 소진될 때까지 위 단계를 반복 다른 리스트의 나머지 원소를 sorted에 이동 배열 sorted

합병 알고리즘 merge(a: array of integers low, mid, high: integer) // 2개의 인접한 배열 a[left..mid]와 a[mid+1..right]를 합병 b1, b2, e1, e2, idx: integer sorted: array of integers b1←low; e1←mid; // 첫번째 배열 인덱스: (하한,상한) b2←mid+1; e2←high; // 두번째 배열 인덱스:(하한,상한) indx←low; //sorted 배열 인덱스 // 2개 배열을 sorted 배열로 합병: // 2개 배열 원소를 비교하여 오름차순으로 sorte로 이동 // 어느 한 배열이 소진되면, 다른 배열 원소를 sorte로 이동 // sorted 배열을 a 배열로 다시 이동 end merge

합병정렬의 분석 merge_sort(list: array of integers, left, right: integer) if (left < right) then mid = (left+right)/2; merge_sort(list, left, mid); merge_sort(list, mid+1, right); merge(list, left, mid, right); endif end merge_sort 비교횟수 이동횟수

평가: 합병 정렬 최악, 평균, 최상의 경우 차이가 있는가? 단점 배열이 아닌 연결리스트로 표현하면? 임시 배열 사용 이동회수가 많다 배열이 아닌 연결리스트로 표현하면? 이동은 링크만 변경하는 것으로 대체 가능

퀵 정렬(quick sort) 평균적으로 가장 빠른 정렬 방법 개념 분할과 정복의 기법에 기반 합병 정렬과는 달리 비균등 분할 사용 한 항목을 피봇(pivot)으로 사용 (당분간, 리스트의 첫번째 항목으로 고려) 피봇보다 작은 항목은 왼쪽으로, 큰 항목은 오른쪽으로 이동 피봇 기준으로 2개의 리스트 분할 위의 각 부분 리스트에 대해서 위의 과정 반복 pivot low high

퀵정렬 개념 피봇(pivot): 가장 왼쪽 숫자라고 가정 두 개의 변수 low와 high를 사용한다. 정지된 위치의 숫자를 교환 low와 high가 교차하면 종료

퀵정렬 전체과정 밑줄친 숫자: 피봇

퀵정렬 알고리즘 void quick_sort(int list[], int left, int right) if left < right then int q=partition(list, left, right); // 배열을 피봇 기준으로 2개로 분할하고, 피봇 위치 반환 quick_sort(list, left, q-1); quick_sort(list, q+1, right); endif end quick_sort

partition 함수 피봇(pivot): 가장 왼쪽 숫자라고 가정 두개의 변수 low와 high를 사용한다. 정지된 위치의 숫자를 교환 low와 high가 교차하면 종료

Quiz 다음 배열을 퀵 정렬하라. 4 7 1 8 6 2 5 3

partition 함수 구현 int partition(int a[], int left, int right) int pivot, low, high; low = left; high = right+1; // low, high 위치 설정 // 비교 전에 low는 증가, high는 감소 pivot = a[left]; // 피봇은 첫번째 원소로 설정 return high; // 피봇 위치 반환 end partition do // 피봇보다 작은 항목은 왼쪽으로, 큰 항목은 오른쪽으로 // 피봇보다 큰 항목을 찾는다. // 피봇보다 작은 항목을 찾는다 //두 항목을 교체 while (low <high); // 피봇을 중앙에 위치

퀵정렬의 분석 비교 회수 이동 회수 최상, 최악의 경우는?

퀵정렬의 분석 거의 균등한 리스트로 분할되는 경우 패스 수: log2n 각 패스안에서의 비교횟수: n 최상의 경우: 거의 균등한 리스트로 분할되는 경우 패스 수: log2n 2->1 4->2 8->3 … n->log2n 각 패스안에서의 비교횟수: n 총비교횟수: n log2n 총이동횟수: 비교횟수에 비하여 무시가능

퀵정렬의 분석(cont.) 최악의 경우: 불균등한 리스트로 분할되는 경우 패스 수: n 각 패스안에서의 비교횟수: n 총이동횟수: 비교횟수에 비하여 무시가능 (예) 정렬된 리스트가 주어졌을 경우 (1 2  3  4  5  6  7  8  9) 1 (2  3  4  5  6  7  8  9) 1  2 (3  4  5  6  7  8  9) 1  2  3 (4  5  6  7  8  9) 1  2  3  4 (5  6  7  8  9)                     ... 1  2  3  4  5  6  7  8  9

퀵 정렬 평가 동일 복잡도를 가진 정렬 방법 가운데서 가장 빠르다. 그 이유는? 퀵 정렬에서 다음 경우를 고려하면? 불필요한 데이터 이동을 줄이고 먼 거리의 데이터 교환 피봇은 추후 연산에서 고려 제외 퀵 정렬에서 다음 경우를 고려하면? 가장 오른쪽 항목을 피봇으로 선택 첫번째, 중간번째, 마지막번째 값중에서 중간 값을 갖는 항목을 피봇으로 선택

기수정렬(Radix Sort) 개념 예제: 한 자리 수로 이루어진 수: (8 2 7 3 5) 비교 연산 없이 데이터 정렬 기수와 일치하는 다단계 정렬 예제: 한 자리 수로 이루어진 수: (8 2 7 3 5) 10개의 버킷 필요 데이터를 각 자리수 값에 따라 버킷에 넣고 위쪽 버킷부터 순차적으로 버킷 안의 숫자를 읽어들인다. 그 결과는 데이터 정렬

기수정렬 만약 2자리수이면? (28, 93, 39, 81, 62, 72, 38, 26) 방법? 몇 개의 버킷이 필요한가?

기수정렬 만약 2자리수이면? (28, 93, 39, 81, 62, 72, 38, 26) 낮은 자리수로 먼저 분류한다음, 순서대로 읽어서 다시 높은 자리수로 분류하면 된다.

기수정렬 다음에서 필요한 버킷의 개수는 데이터 키가 2진법으로 표현되면? 키가 알파벳 문자이면? 키가 32비트 정수이고, 8비트씩 나누어서 기수정렬 적용하면?

기수정렬 알고리즘 RadixSort(list : array of integers, n: integer) { for d←LSD의 위치 to MSD의 위치 do    d번째 자릿수에 따라 0번부터 9번 버킷에 집어놓는다.    버킷에서 숫자들을 순차적으로 읽어서 하나의 리스트로 합친다.    d++; end for } 버킷은 어떻게 구현하는가?

기수정렬 알고리즘 RadixSort(list : array of integers, n: integer) { QueueType q[BUCKETS]; for (d=0; d<DIGITS; d++) { // 데이터를 버킷에 넣는다 // 데이터를 버킷에서 꺼내어 배열에 저장한다 i=0; for (b=0; b<BUCKETS; b++) do while (!isEmpty(q[b]) do a[i++] = dequeue(q[b]); end while end for }

기수 정렬 알고리즘 분석 복잡도 정렬 데이터의 타입이 정수형으로 제한 데이터의 정수가 d개의 자리수를 가질 경우 실수의 경우는?

정렬 알고리즘의 비교

문제 다음 정렬 방법을 비교하라. 각 정렬방법에 대해서 데이터 항목 수에 따른 실행시간 추이도를 그래프로 그려라 정렬 방법: 삽입, 선택, 버블, 쉘, 퀵, 합병 정렬 대상 데이터 항목: 주어진 개수의 난수(범위: 1~10,000) 발생 오름차순 정렬 분석 기준 (프로그램 실행 5회의 평균치로 측정할 것) 실행 시간 각 정렬방법에 대해서 데이터 항목 수에 따른 실행시간 추이도를 그래프로 그려라 데이터 항목 수: 2만개, 4만개, 6만개, 8만개, 10만개