[알고리즘] 2원 합병 정렬 merge sort
2원 합병 정렬 주요 특징 대표적인 분할 및 정복 기법 자료를 거의 동일한 크기의 두 그룹으로 나누고, 각각을 별도로 정렬한 후, 합병 순환 알고리즘 방식 복잡도분석 합병(merge)에 따른 비교회수 : n번 = O(n) 순환방정식 : T(n) = 2 T(n/2) + n 전체 비교 회수 : O(n log n) 장단점 수행 시간 우수, 단 순환 알고리즘의 한계 내포 추가 기억장소 사용량 : 추가 배열용 n개 필요 전체 총 2n개의 기억장소 필요, O(n) void merge_sort(data A[], int L, int R) { int m; if(R > L) { m = (R+L) / 2; merge_sort(A, L, m); merge_sort(A, m+1, R); merge(A, L, R, m); } }..
[알고리즘] 정렬 / 정렬 프로그램 완성
정렬 내부정렬 주기억장치내 저장된 소규모 자료 대상 삽입정렬, 선택정렬, 버블정렬, 쉘정렬, 퀵정렬, 2원합병정렬, 히프정렬, 기수정렬 등 외부정렬 테이프 등에 저장된 대규모 자료 대상 자연2원합병, 균형2원합병, 균형m원합병, 다단계합병 등 내부정렬 입력 자료 입력 데이터는 대부분 배열에 저장 일부는 연결리스트 사용 A[1],A[2],...,A[n]을 입력으로 봄 간혹, 경우에 따라 A[0]를 포함하기도 함 ( C 언어의 경우, A[0]부터 시작 ) 정렬 프로그램 완성 void sort() { /* 이 곳에 알맞은 내용을 추가하시오. */ /* 입력 데이타는 L[]에 들어 있으면, 전체 원소 개수는 SIZE이다. */ } #include using namespace std; const int SIZE ..
[알고리즘] 순환 알고리즘 Recursion / 하노이 탑
순환 알고리즘 (recursive algorithm) 직접순환(direct recursion), 간접순환(indirect recursion) 간결하고 명확 but, 일반적으로 수행속도 및 기억장소 사용에 비효율적이다. 순환(recursion) vs 반복(iteration) 순환 알고리즘의 적용 예 Factorial : n! = n * (n-1)! = n*(n-1)*...*2*1 Fibonacci 수열 : 1, 1, 2, 3, 5, 8, 13, 21, .... BNF(Backus Naur Form) 합계 계산(SUM) 정렬, 탐색, 트리 문제 등 다양한 경우에 실제 적용된다. 순환 알고리즘의 복잡도 순환 알고리즘의 일반적인 단계 분할, 정복, 결합 단계 순환 방정식(recurrence equation) 이..
