PowerPoint 프레젠테이션

Transcription

1 정렬알고리즘 9 장. 정렬알고리즘 가장많이, 그리고가장잘알려진알고리즘방법과효율빅오기호로분석 학습목표 정렬알고리즘의분류방법을이해한다. 정렬알고리즘별로작동원리에대해이해한다. 정렬알고리즘별로효율분석방법을이해한다. 정렬알고리즘에따라효율을개선하기위한방법을이해한다. 1

2 Section 01 정렬의분류 - 정렬의분류정렬 정렬의대상 = 레코드정렬의기준 = 정렬키 (Sort Key) 필드 오름차순, 내림차순 오름차순 : 키크기가증가하는순 내림차순 : 키크기가감소하는순 [ 그림 9-1] 오름차순, 내림차순 2

3 정렬의분류내부정렬, 외부정렬 내부정렬 정렬대상을한꺼번에메인메모리에올릴수있을때 외부정렬 정렬대상을한꺼번에메인메모리로올릴수없을때 메인메모리와보조메모리사이를들락날락하면서정렬 3

4 정렬의분류안정정렬 (Stable Sorting) 과불안정정렬 (Unstable Sorting) 1차키 : 학점 2차키 : 학년 1차키로정렬하더라도이전의 2차키정렬순서가유지됨 성명 학년 학점 주소지 김용태 1 C 대구 정지희 1 B 서울 유일근 1 A 서울 박하영 3 B 전주 정건호 3 C 인천 김무성 3 A 수원 최석 4 A 용인 [ 표 9-1] 신상정보 성명 학년 학점 주소지 김무성 3 A 수원 최석 4 A 용인 유일근 1 A 서울 박하영 3 B 전주 정지희 1 B 서울 김용태 1 C 대구 정건호 3 C 인천 [ 표 9-2] 불안정정렬 성명 학년 학점 주소지 유일근 1 A 서울 김무성 3 A 수원 최석 4 A 용인 정지희 1 B 서울 박하영 3 B 전주 김용태 1 C 대구 정건호 3 C 인천 [ 표 9-3] 안정정렬 4

5 정렬의분류 직접정렬 (Direct Sorting) 과간접정렬 (Indirect Sorting) 입력 인덱스 레코드김모 90 박모 50 최모 70 [ 표 9-4] 입력레코드 직접정렬 인덱스 레코드박모 50 최모 70 김모 90 [ 표 9-5] 직접정렬 간접정렬 인덱스 인덱스 [ 표 9-6] 인덱스데이터 [ 표 9-7] 간접정렬 5

6 Section 02 선택정렬 - 선택정렬 가장큰것을선택하여가장마지막것과스와핑 [ 그림 9-2] 선택정렬 6

7 코드 9-1: 선택정렬 선택정렬의효율 void Selection(int A[ ], int N) A는배열이름, N은정렬대상레코드수 { for (int Last = N-1; Last >= 1; --Last) 마지막인덱스를왼쪽으로이동하면서 { int Largest = 0; 일단처음것이가장크다고보고 for (int Current=1; Current<=Last; Current++) 처음부터마지막까지 { if (A[Current] > A[Largest]) 현재것이더크면 Largest = Current; 현재인덱스를가장큰레코드의인덱스로 } int Temp = A[Last]; 이동을위해마지막레코드를잠시저장 A[Last] = A[Largest]; 가장큰레코드를마지막으로이동 A[Largest] = Temp; 마지막것을가장큰레코드위치로이동 } } if 문 : (N-1) + (N-2) = (N-1)N/2 번실행, 비교와할당으로구성기타할당문 : 4(N-1) 효율 : 2(N-1)N/2 + 4(N-1) = N 2 + 3N - 4 = O(N 2 ) 대략적분석 : 왼쪽위의삼각형면적이비교의횟수임. O(N 2 /2) = O(N 2 ) 7

8 이중선택정렬한번의스캔에최대치와최소치를동시에발견하고스와핑 MinMax Sorting O(N 2 /2) = O(N 2 ) 단계의수가반으로감소계수를줄이는노력 단계결과 단계결과 단계결과 단계결과 [ 표 9-8] 이중선택정렬 8

9 Section 03 버블정렬 - 버블정렬 버블정렬 9

10 버블정렬 가장큰레코드가한칸씩오른쪽끝으로떠올라오는정렬 한쌍씩비교하되이전쌍의둘째레코드가다음쌍의첫레코드가되게중복 [ 그림 9-4] 버블정렬 10

11 단계수 데이터 N 개라면버블정렬의단계수는대략 N. 어떤단계에서스와핑이한번도일어나지않았다면 ( 이어지는한쌍끼리모두 ) 정렬완료된것임. 코드 9-2: 버블정렬 void Bubble(int A[ ], int N) A 는배열이름, N 은정렬대상레코드수 { bool Sorted = FALSE; 스와핑이전혀없는단계에서빠져나가기위한변수 for (int Pass = 1; (Pass < N) && (!Sorted); ++Pass) { Sorted = TRUE; 스와핑이전혀없다고초기화 for (int Current=0; Current<N-Pass; ++Current) { if A[Current] > A[Current+1] 현재것이다음것보다크면 { int Temp = A[Current]; 스왑 A[Current] = A[Current+1]; ] A[Current+1] = Temp; Sorted = FALSE; 스왑이한번이라도일어나면다음단계로 안쪽루프내부의명령은 (N-1) + (N-2) = (N-1)N/2 번수행. 루프내부의비교문은 (N-1)N/2 번. 할당문각각이 (N-1)N/2 번. 최종효율 (N-1)N/2 + 2(N-1)N = O(N 2 ) 버블정렬 11

12 버블정렬, 선택정렬단계 단계별로가장큰것이가장오른쪽으로이동한다는점에서동일선택정렬은가장큰것과가장오른쪽것이한번에스와핑. 버블정렬은가장큰것이한칸씩오른쪽으로이동 스와핑 ( 교환, 복사 ) 에걸리는시간 큰레코드에대해서버블정렬은선택정렬보다불리 이미정렬된데이터 버블정렬이최선의효율 1단계에서끝남. ( 스와핑이전혀없음 ). O(N) 의효율선택정렬은여전히 O(N 2 ) 의효율. 가장큰데이터인마지막데이터가자기자신과스왑 (Self Swap) 12

13 Section 04 삽입정렬 - 삽입정렬왼쪽정렬된그룹을점차키워간다. 1 단계 : 가장왼쪽첫레코드하나만주목. 그자체로정렬 2 단계 : 다음레코드를왼쪽것과비교. 37은 22보다크므로그대로둠. 3 단계 : 15는 37의왼쪽으로가야한다. 풀스왑 : 삽입할레코드가계속적으로왼쪽으로옮김 하프스왑 : 삽입될레코드는단한번만움직임 [ 그림 9-5] 삽입정렬 13

14 코드 9-3: 삽입정렬 void Insertion(int A[ ], int N) { for (int Pick=1; Pick<N; ++Pick) 왼쪽부터카드를하나씩집어내면서 { int Current = Pick; 집어낸카드의인덱스를현재인덱스로 } } 삽입정렬의효율 for (; (Current > 0) && (A[Current-1]>A[Pick]); --Current) A[Current] = A[Current-1]; 집어낸카드보다크면오른쪽으로이동 A[Current] = A[Pick]; 집어낸카드를제위치에삽입 ( 하프스왑 ) 효율안쪽루프명령문은 (N-1) = (N-1)N/2 번실행 for 문자체에비교 2 번, 할당 1 번, for 문내부에할당이 1 번총 4(N-1)N/2 = 2(N-1)N = O(N 2 ) 이미정렬된데이터에대해삽입정렬은최선의효율이미정렬된기존사원 2000 명, 신입사원 10 명. 신입사원파일을기존사원파일에붙인이후삽입정렬. 2, 000 명은이미정렬되어있으므로 O(N) 신입사원은최악의경우배열의맨앞까지가면서비교와스왑. 이작업은 10 명에불과하므로 10N 의시간. 따라서전체적인효율은 O(N) + O(10N) = O(N) 14

15 선택, 버블, 삽입 최악의효율은모두 O(N 2 ) 으로서동일 버블정렬과삽입정렬는안정정렬 레코드들이하나하나순차적으로이동 (Shift) 하기때문에원래의순서가유지 선택정렬은불안정정렬 스왑 (Swap) 에의해단번에멀리떨어진곳으로 선택정렬 버블정렬 삽입정렬 효율 O(N 2 ) O(N 2 ) O(N 2 ) 안정정렬 No Yes Yes [ 표 9-9] 기본정렬방식의효율 15

16 Section 05 셀정렬 - 셸정렬 셀정렬 [ 그림 9-6] 삽입정렬과셸정렬 16

17 삽입정렬을개선. 한칸씩이동하는하는대신한번에여러칸이동 4- 정렬의예 셸정렬 [ 그림 9-7] 4- 정렬 일련의 h- 정렬 최종적으로는 1- 정렬. 효율은 O(N 3/2 ). 삽입정렬의 O(N 2 ) 보다는빠르지만 O(NlogN) 보다는느린효율 [ 그림 9-8] h- 정렬의필요성 17

18 Section 06 합병정렬 - 합병 합병 18

19 합병 정렬된그룹의합병 19

20 합병함수 코드 9-4: 합병함수 void Merge(dataType A[ ], int F, int Mid, int L) F, Mid, L은그룹분리를위한인덱스 { datatype Temp[MAX]; datatype의배열데이터를가정 int First1 = F; int Last1 = Mid; F부터 Mid까지가첫그룹 int First2 = Mid + 1; int Last2 = L; (Mid+1) 부터 L까지가둘째그룹 int Index = First1; for (; (First1 <= Last1) && (First2 <= Last2); ++Index) 그룹인덱스가밖으로안나갈동안 { if (A[First1] < A[First2]) 첫그룹의데이터가작으면 { Temp[Index] = A[First1]; 임시저장공간에복사 ++First1; 포인터를이동 } else 둘째그룹의데이터가작거나같으면 { Temp[Index] = A[First2]; 임시저장공간에복사 ++First2; 포인터를이동 } } for (; First1 <= Last1; ++First1, ++Index) 첫그룹에남은데이터가있으면 Temp[Index] = A[First1]; 순서대로임시저장공간에복사 for (; First2 <= Last2; ++First2, ++Index) 둘째그룹에남은데이터가있으면 Temp[Index] = A[First2]; 순서대로임시저장공간에복사 for (Index = F; Index <= L; ++Index) 임시저장공간의데이터를 A[Index] = Temp[Index]; 원래배열로복사시킴 } 20

21 합병정렬메인함수코드 9-5: 합병정렬의메인함수 void MergeSort(int A[ ], int First, int Last) { if (First < Last) { int Middle = (First + Last) / 2; MergeSort(A, First, Middle); MergeSort(A, Middle+1, Last); Merge(A, First, Middle, Last); } } 합병정렬 반잘라서왼쪽재귀호출, 오른쪽재귀호출. 결과를합병 베이스케이스로부터빠져나와호출함수로되돌아오는과정에서 Merge(A, First, Middle, Last) 즉, 합병에의해정렬 21

22 합병정렬들어가고나오기 합병정렬들어가고나오기 [ 그림 9-11] 합병정렬의실행과정 22

23 합병정렬의효율 효율 O(NlgN) 호출의단계수가 lgn 각단계별로합병에 O(N) [ 그림 9-11] 합병정렬의실행과정 23

24 효율 삽입정렬과합병정렬 O(N 2 ) 대 O(NlgN) 좋은알고리즘은슈퍼컴퓨터보다낫다. 삽입정렬 컴퓨터 N=10 3 N=10 6 N=10 9 PC 순간적 2.8 시간 317 년 수퍼컴퓨터순간적 1 초 1.7 주 [ 표 9-10] 삽입정렬 (O(N2)) 합병정렬 컴퓨터 N=10 3 N=10 6 N=10 9 PC 순간적 1초 18분 수퍼컴퓨터순간적 순간적 순간적 [ 표 9-11] 합병정렬 (O(NlgN)) 24

25 Section 07 쾌속정렬 - 쾌속 쾌속 25

26 쾌속정렬합병정렬과쾌속정렬 재귀호출의순서에유의실제정렬작업이어디서일어나는지유의 MergeSort { MergeSort (Left); MergeSort (Right); Merge; } QuickSort { Partition; QuickSort(Left); QuickSort(Right); } [ 표 9-12] 합병정렬과쾌속정렬비교 26

27 쾌속정렬 코드 9-6: 파티션함수 int partition(int A[ ], int first, int last) { int low, high, pivotindex, p; p = A[last]; 마지막요소를피벗으로 low = first; 업포인터를처음으로 high = last-1; 다운포인터를마지막직전요소로 while (low < high) 크로스오버가없을때까지 { while (p > A[low]) low++; 피벗보다크거나같은것찾기 while (p < A[high]) high--; 피벗보다작거나같은것찾기 if (low < high) 크로스오버가아니면 Swap(A, low, high); 작은것과큰것을스왑 } Swap(A[low], A[last]); 업포인터레코드와피벗레코드를스왑 return (low); 피벗인덱스를리턴 } 27

28 코드 9-7: 쾌속정렬의메인함수 쾌속정렬메인함수 void QuickSort(int A[ ], int First, int Last) { if (First < Last) { int PivotIndex = Partition(A, First, Last); QuickSort(A, First, PivotIndex-1); QuickSort(A, PivotIndex+1, Last); } } [ 그림 9-14] 쾌속정렬 28

29 효율 쾌속정렬 단계의수에따라결정단계의수는파티션결과좌우정확히양분되면 lgn 균형 (Balancing) 이좋을때효율은 O(NlgN0 정렬된데이터에최악의효율파티션결과하나씩만나가떨어진단계의수는거의 N [ 그림 9-15] 정렬된데이터 29

30 쾌속정렬의균형 파티션방법더나은균형을위하여같은키에서도스와핑 피벗의선택 ( 세개중메디안 파티션 ) 처음세개, 마지막세개, 처음, 마지막, 중간것랜덤함수에의한추출어느경우든선택을위한시간이소요됨. 시스템정렬샘플정렬 램덤하게여러샘플추출, 정렬, 그중중간값을피벗으로벤틀리매클로이방식 한번에 3 개의샘플을사용하여메디안을구함 3 번반복하여 3 개의메디안을구한뒤, 그중의메디안값을피벗으로 파티션의최종단계예를들어데이터 10 개이하직접삽입정렬에의해정렬재귀호출에따른활성화레코드생성, 복원에따르는시간배제 30

31 합병정렬, 쾌속정렬효율비교 합병정렬은매단계마다완벽한균형합병정렬은최악의경우에도 O(NlgN) 을보장쾌속정렬은최악의경우 O(N 2 ) 쾌속정렬은임시저장공간이불필요한제자리연산 (In-Place Computation) 합병정렬은임시저장공간에옮겨가고옮겨오는시간이필요평균적으로는쾌속정렬이빠름 31

32 정렬방식비교 합병정렬 쾌속정렬 N=10 3 N=10 6 N=10 9 PC 순간적 1초 18분 수퍼컴 순간적 순간적 순간적 N=10 3 N=10 6 N=10 9 PC 순간적 0.3초 6분 수퍼컴 순간적 순간적 순간적 [ 표 9-13] 합병정렬 (O(NlgN)) [ 표 9-14] 쾌속정렬 (O(NlgN)) 삽입, 쾌속, 합병 [ 표 9-15] 정렬방식의비교 삽입정렬 쾌속정렬 합병정렬 최악의효율 N 2 N 2 NlgN 최선의효율 N NlgN NlgN 평균적효율 N 2 NlgN NlgN 이미정렬된데이터 N N 2 NlgN 반대로정렬된데이터 N 2 N 2 NlgN 공간 N N 2N 안정정렬 Yes No YES 32

33 Section 08 외부정렬- 외부정렬기본적으로합병정렬 1 단계 : 입력파일 : D A T A S T R U C T U R E A N D A L G O R I T H M 메인메모리용량이세개단위로읽어들여정렬가능하다고가정 파일 1: ADT * RTU * GOR * 파일 2: AST * AEN * HIT * 파일 3: CRU * ADL * M * 2 단계 : (3 개씩합병 ) 파일 4: AACDRSTTU * 파일 5: AADELNRTU * 파일 6: GHIMORT * 3 단계 : (3 개씩합병 ) 파일 1: AAAACDDEGHILMNORRSTTTTUU * 33

34 외부정렬 1 단계 : 파일 1: ADT * RTU * GOR * 파일 2: AST * AEN * HIT * 파일 3: CRU * ADL * M * 2 단계 : (2 개씩합병 ) 파일 4: AADSTT * AADELN * M 파일 5: CRRTUU * GHIORT * 3 단계 : (2 개씩합병 ) 파일 1: AACDRRSTTTUU * M 파일 2: AADEGHILNORT * 4 단계 :(2 개씩합병 ) 파일 3: AAAACDDEGHILNORRSTTTTUU * 파일 4: M 5 단계 (2 개씩합병 ) 파일 1: AAAACDDEGHILMNORRSTTTTUU * 34

35 합병 외부정렬 모든블록이합병에참가하기만하면합병의순서는관계없음 효율 CPU 연산시간 << 입출력시간외부정렬의효율은입출력시간에좌우됨몇단계에걸쳐파일출력이일어나는가가관건 1 단계실행결과정렬된블록의개수는 N/M 개 p 개단위의합병 합병한번에블록의개수는 1/p 씩줄어듬 따라서정렬의효율은대략 log p (N/M) 35

36 Section 09 최선의정렬효율 - 최선의정렬효율 버블정렬의결정트리 3 개의키이므로크기순서의조합은 3! = 6 불필요한비교를감안하면일반적으로리프노드의수는 N! 개이상 [ 그림 9-16] 버블정렬의결정트리 트리의높이는최소한 log 2 (N!) 보다크고최소비교의회수는 log 2 (N!). 스털링 (Stirling) 의공식 : log 2 (N!) log 2 (N/e)N = Nlog 2 N - Nlog2e. 따라서정렬에서가능한최소비교회수는 Nlog 2 N 36

37 Section 10 버켓정렬과셈정렬 - 버켓정렬 버켓정렬 37

38 방법 버켓정렬 키자체를배열인덱스로하여별도배열로옮김효율 O(N). 키비교에의한정렬이아니므로 O(NlgN) 을능가할수있음단점버켓배열의인덱스보다큰키가들어올수없음버켓의크기를최대인덱스크기로설정. 메모리공간낭비가능성이를개선한것이셈정렬 [ 그림 9-18] 버켓정렬 38

39 셈정렬 분포세기 (Distribution Counting) 또는셈정렬 (Count Sorting) 중복키허용키빈도를 Count[ ] 배열에넣음. Count[1]= 4, Count[2] = 2, Count[3] = 1 누계를구하면 Count[1] = 4, Count[2] = = 6, Count[3] = = 7 오른쪽에서왼쪽으로스캔해가면서버켓에삽입삽입위치는현재의카운트값. 삽입직후에는카운트값을하나씩줄임 [ 그림 9-19] 셈정렬 효율 O(N) 로서안정정렬 39

40 Section 11 기수정렬 - 기수정렬 기수 = 키의구성요소. 분해된문자열, 분해된문자 [ 그림 9-20] 문자열키의분해 40

41 기수정렬기수정렬 Radix = 뿌리문자열키의뿌리는문자. 문자의뿌리는비트문자열단위로비교하는대신문자열을잘라서문자단위로비교 기수 8비트 ASCII 코드라면 256가지레이딕스 16비트유니코드 (Unicode) 라면 65,536 가지의레이딕스숫자를문자열로간주하면숫자키에대해서도기수정렬을가할수있음. 41

42 LSD LSD 기수정렬 문자열오른쪽 (Least Significant Digit ) 에서왼쪽으로 제대로동작하는이유는안정성때문. 왼쪽키가같다면오른쪽키는이전에정렬된순서를유지함 문자단위의정렬은셈정렬을사용 문자열길이 W 일때, 효율은 O(WN) 0 a d d 0 c a b 0 c a b 0 a c e 1 c a b 1 a d d 1 b a d 1 a d d 2 f e e 2 b a d 2 d a d 2 b a d 3 b a d 3 d a d 3 a c e 3 b e d 4 d a d 4 b e d 4 a d d 4 b e e 5 b e e 5 f e e 5 b e d 5 c a b 6 b e d 6 b e e 6 f e e 6 d a d 7 a c e 7 a c e 7 b e e 7 f e e [ 그림 9-21] A [ 그림 9-22] B [ 그림 9-23] C [ 그림 9-24] D 42

43 LSD 기수정렬 단점최종단계의정렬이이루어지기전까지는조금이라도정렬된흔적이없음가변길이키에적용하기어려움. cold 와 old 라는키에이방식을가하면뒤에서부터올라오므로마지막첫자리에서 cold 의 c 와비교되어야하는것이 old 에는없으므로아무것도없음을표시하는널문자 (Null Character) 와비교. ASCII 코드표에의하면 c 는십진수 99, 널문자는십진수 0 이므로 old, cold 순의오름차순이된다. 이는잘못된정렬마지막부근의자릿수정렬에많은시간을허비. 만약키가 Kim Pak Cho Rho 등이라면사실은첫자리만보고도정렬이가능한것이다. 패딩 cold, old, at 를비교하자면 cold, old0, at00 등으로마지막에 0 을보충 0 은아스키값십진수 47 로서문자보다는그값이작음숫자를문자열로취급할경우에는거꾸로처음에 0 을넣어서비교 1611, 315, 17 을비교하자면 1611, 0315, 0017 로비교패딩은번거로운작업으로서키의최대길이를찾아내는시간, 패딩하는시간을요한다. 43

44 MSD 기수정렬 MSD 왼쪽 (MSD: Most Significant Digit) 에서오른쪽으로진행셈정렬 (Distribution Counting) 을사용. O(WN) = O(N) 이전의모든문자가일치하는것들만다음문자를비교앞부분이유일 (Uniqueness) 해지면더이상비교대상에서제외 0 a d d 0 a d d 0 a c e 0 a c e 1 c a b 1 a c e 1 a d d 1 a d d 2 f e e 2 b a d 2 b a d 2 b a d 3 b a d 3 b e e 3 b e e 3 b e d 4 d a d 4 b e d 4 b e d 4 b e e 5 b e e 5 c a b 5 c a b 5 c a b 6 b e d 6 d a d 6 d a d 6 d a d 7 a c e 7 f e e 7 f e e 7 f e e [ 그림 9-25] D [ 그림 9-26] E [ 그림 9-27] F [ 그림 9-28] G 44

45 기수교환정렬 기수교환정렬 문자단위의정렬에셈정렬대신쾌속정렬사용 별도메모리대신스와핑사용 3-way 파티션 피벗 b 와일치하지않는키 (add, ace 그룹, dad, fee, cab 그룹 ) 는다시첫문자를기분으로재귀적으로정렬해야함. 피벗 b 와일치하는키 (bed, bad, bee) 는두번째문자를대상으로정렬을진행 0 a d d 1 c a b 2 f e e 3 b a d 4 d a d 5 b e e 6 b e d 7 a c e [ 그림 9-29] H 0 a d d 1 a c e 2 b e d 3 b a d 4 b e e 5 d a d 6 f e e 7 c a b [ 그림 9-30] I 45

46 비트단위의기수교환정렬파티션 파티션결과 0인그룹과 1인그룹으로양분첫문자에재귀적으로파티션할필요가없음비트단위의쾌속정렬비트열이유일 (Uniqueness) 해지면더이상비교대상에서제외시킴 [ 그림 9-31] 비트단위의기수교환정렬 46

47 유일한비트열 비트단위의기수교환정렬 파티션이가해질때마다 N 개의비트값이비교데이터 N 개라면대략적으로 log 2 N 비트만에모든비트열이유일해짐. 기수교환정렬의효율은 O(Nlog 2 N) 통계적분석 효율 통계적으로볼때, 어떤자리수가 0 일확률과 1 일확률이 1/2 로서동일비트단위의파티션을가하면데이터의반이 0 그룹, 나머지반이 1 그룹균형적파티션이므로단계의수는쾌속정렬에서지속적으로균형적인파티션이일어날때의단계수인 log 2 N 과동일균형이일어날확률이높음으로인해쾌속정렬보다 O(Nlog 2 N) 에근접 소요되는시간면에서비트단위의기수교환정렬은쾌속정렬과큰차이기수교환정렬에서 O(Nlog 2 N) 이라고할때에는비트단위의비교회수쾌속정렬에서 O(Nlog 2 N) 라고할때에는문자열단위의비교회수 47

48 Thank you 48