SlideFinderPowerPoint search engine with thumbnail results
Newest Viewed Downloaded

알고리즘 5.5장 쉘 정렬 (Shell sort) 5.6장 분포수세기(Distribution Counting) 5.7장 퀵 정렬(Quick Sort)유명훈 ymh627@kunsan.ac.kr 군산대학교 정보통계학과 정보과학기술 연구실 2011. 7. 19

알고리즘 5.5장 쉘 정렬 (Shell sort) 5.6장 분포수세기(Distribution Counting) 5.7장 퀵 정렬(Quick Sort)

유명훈 ymh627@kunsan.ac.kr 군산대학교 정보통계학과 정보과학기술 연구실 2011. 7. 19 ‹#›

목차

쉘 정렬 - 쉘 정렬의 전략 - 쉘 정렬의 실제 - C로 구현한 쉘 정렬 - 쉘 정렬의 분석 - 쉘 정력의 개선 분포수세기 - 분포수세기의 전략 - 분포수세기의 실제 - C로 구현한 분포수세기 - 분포수세기의 분석 퀵 정렬 - 퀵 정렬의 전략 - 퀵 정렬의 실제 - C로 구현한 퀵 정렬 - 퀵 정렬의 분석 - 퀵정렬의 개선 1~3 - qsort()함수 2 IST (Information Sciences & Technology) Laboratory

쉘 정렬의 전략

쉘 정렬 - 삽입 정렬(이미 정렬된 배열, 대충 정렬된 배열) 매우 뛰어난 성능 그렇지 않을 경우에는 속도가 느림 - 위와 같은 문제점을 해결하기 위해서 h만큼 간격으로 떨어진 레코드를 삽입 정렬 하는 방법(점진적 형태) 3 IST (Information Sciences & Technology) Laboratory 1.h의 초기값을 구함 2.h가 1보다 작을 시 끝 3.i=0 4.i가 h보다 크거나 같으면 7로 이동 5.(h간격 + i)요소들에 대해서 삽입 정렬을 함 6.i를 하나 증가시키고 4로 감 7.h의 다음 값을 구하고 2로 감

쉘 정렬의 실제

4 IST (Information Sciences & Technology) Laboratory 1.h의 초기값을 구함 2.h가 1보다 작을 시 끝 3.i=0 4.i가 h보다 크거나 같으면 7로 이동 5.(h간격 + i)요소들에 대해서 삽입 정렬을 함 6.i를 하나 증가시키고 4로 감 7.h의 다음 값을 구하고 2로 감 안정성이 없음

C로 구현한 쉘 정렬

5 IST (Information Sciences & Technology) Laboratory

쉘 정렬의 분석

쉘 정렬의 모습 알고리즘의 이상적인 모양 4중 루프 - 속도는 느리지 않음 6 IST (Information Sciences & Technology) Laboratory N 정렬된 배열 난수 배열 반쯤 정렬된 배열 역순 배열 100 0 0 0 1 500 1 2 2 2 1000 2 4 4 4 2000 6 9 8 7 5000 16 30 26 22 7000 22 42 38 31 10000 35 63 63 48 단위 : 틱(약 1/18.2초)

쉘 정렬의 개선

효과적인 개선 - h를 설정 7 IST (Information Sciences & Technology) Laboratory hn = 3*hn-1+1, h1 = 1 N 정렬된 배열 난수 배열 반쯤 정렬된 배열 역순 배열 100 0 0 0 0 500 1 1 1 1 1000 1 3 2 2 2000 3 8 7 5 5000 10 24 22 14 7000 15 34 32 21 10000 23 51 51 34 N 정렬된 배열 난수 배열 반쯤 정렬된 배열 역순 배열 100 0 0 0 1 500 1 2 2 2 1000 2 4 4 4 2000 6 9 8 7 5000 16 30 26 22 7000 22 42 38 31 10000 35 63 63 48

분포수세기

같은 키가 많이 있는 배열에 한해 적용할 수 있음 - 누적분포를 이용 8 IST (Information Sciences & Technology) Laboratory count[1] = 5 count[2] = 6 count[3] = 5 count[4] = 2 count[5] = 2 1 3 2 2 3 1 3 2 4 2 4 3 1 2 1 2 5 1 5 3 count[1] = 5 count[2] = count[ 1] + count[2] = 11 count[3] = count[2] + count[3] = 16 count[4] = count[3] + count[4] = 18 count[5] = count[4] + count[5] = 20 1.count[]배열을 0으로 초기화 2.a[]배열의 키의 빈도를 계산 빈도 count[] 저장 3.count배열을 누적분포로 변환 4.a[] 배열을 뒤에서부터 읽어서 b[--count a[i]]에 저장 5.b[]배열을 a[]배열로 복사

분포수세기의 실제

9 IST (Information Sciences & Technology) Laboratory 안정성이 있음

C로 구현한 분포수세기

10 IST (Information Sciences & Technology) Laboratory

분포수세기의 분석

한정된 용도에만 적합 속도가 빠르지만 메모리 소모가 큼 적당히 작은 N범위의 키 값을 가지는 중복된 키가 많은 경우에 적합 기수정렬에서 강력한 기능을 함 11 IST (Information Sciences & Technology) Laboratory

퀵 정렬

축값을 중심으로 왼쪽은 축값보다 작은 값 오른쪽은 큰 값으로 배열 시킴(분할을 이용) 12 IST (Information Sciences & Technology) Laboratory 안정성이 없음 만약 n >1 이면 N 크기의 a배열을 분할하여 축값의 위치를 mid로 넘김 퀵 정렬 알고리즘

C로 구현한 퀵 정렬

13 IST (Information Sciences & Technology) Laboratory

퀵 정렬의 분석

14 IST (Information Sciences & Technology) Laboratory N 정렬된 배열 난수 배열 반쯤 정렬된 배열 역순 배열 10 0 0 0 0 100 0 0 0 1 500 8 1 2 10 1000 34 2 3 40 2000 135 5 5 162

퀵 정렬의 개선

퀵 정렬 개선(비재귀판) - 오버플로 - 15 이면 15*6 = 90, 20000*6=12000 - push() pop() 사용, 오버헤드 현상으로 속도가 오르지 않음 퀵 정렬 개선(난수 분할) - pivot value 축 값을 임의로 정함 - 역순 / 순차배열에서도 O(NlogN) 성능이 나옴 퀵 정렬 개선(세 값의 중위) - 왼쪽에 가장 작은 값, 중앙에 중간 값, 가장 오른쪽 값 큰 값 15 IST (Information Sciences & Technology) Laboratory N 정렬된 배열 난수 배열 반쯤 정렬된 배열 역순 배열 10 0 0 0 0 100 0 0 0 1 500 9 0 1 10 1000 34 2 2 40 2000 133 4 5 159

qsort()함수

C표준 라이브러리에서 제공하는 퀵 정렬 함수 16 IST (Information Sciences & Technology) Laboratory N 정렬된 배열 난수 배열 반쯤 정렬된 배열 역순 배열 100 0 0 0 0 500 1 3 2 2 1000 4 5 5 4 2000 9 11 11 8 5000 23 31 32 24 7000 33 52 48 35 10000 50 71 68 52

감사합니다

유명훈 ymh627@kunsan.ac.kr ‹#›

Showing 1 - 17 of 17 items Details

Name: 
110719(5.5~5.7장)
Author: 
정혜진
Company: 
ISTLAB
Description: 
알고리즘 5.5장 쉘 정렬 (Shell sort) 5.6장 분포수세기(Distribution Counting) 5.7장 퀵 정렬(Quick Sort)유명훈 ymh627@kunsan.ac.kr 군산대학교 정보통계학과 정보과학기술 연구실 2011. 7. 19
Tags: 
count | ist | technology | laboratory | information | sciences | 정렬된 | 정렬의
Created: 
10/1/2008 1:38:18 PM
Slides: 
17
Views: 
8
Downloads: 
0
Rating: 
0


> Comment



Share this presentation
|

Comments

Share this presentation:

|
Sitemap