[알고리즘 Report] C언어로 구현한 합병정렬(Merge Sort) 프로그램 코드와 행렬 곱셈 program 소스, 결과 이미지 및 레포트

소개글

C언어로 구현한 합병정렬 예제 소스입니다.
레포트 안에 코드 소스, 결과 이미지 첨부되어 있으며
관련 내용 및 결과에 대한 설명도 작성해 놓았습니다^^

목차

1. 합병정렬(Merge Sort)
1) 합병정렬 절차
2) 합병 정렬 프로그램 코드
3) 실행화면

2. 행렬곱셈(Matrix)
1) Strassen 행렬곱셈 알고리즘
2) 행렬곱셈 프로그램 코드 (표준 행렬곱셈)
3) 실행화면

본문내용

1. 합병정렬(Merge Sort)

- DAC 설계
➀ 분할(divide) : 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다.
➁ 정복(conquer) : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 재귀 호출을 이용하여 다시 분할 방법을 적용한다.
➂ 통합(combine) : 정렬된 부분 배열들을 하나의 배열에 합병한다.

- 합병정렬 절차
- 이미 순서적으로 배열된 두 개의 파일에서 레코드의 배열 순서에 따라 차례로 한 레코드씩 가져다 비교하여 작은 키 값을 가지는 레코드를 새로운 병합 파일에 출력하고, 작은 레코드를 가져온 파일에서 다음 순서의 레코드를 가져와 이전에 비교한 큰 키 값을 가진 레코드와 비교하는 과정을 반복 수행한다.

- 합병 정렬에서는 두 부분배열의 크기가 항상 같게 분할되며, 최악의 경우에도 수행시간은
이다.

- 임시 기억장소(배열)가 필요하며, 실제로는 수행시간이 많이 걸린다.

<중 략>

2. 행렬곱셈(Matrix)
DAC 설계
➀ 분할(divide) : 행렬을 n/2 x n/2 크기의 부분행렬 네 개로 분할한다.
➁ 정복(conquer) 및 통합(combine) : 보통의 행렬 곱 방식으로 계산

- Strassen 행렬곱셈 알고리즘

void strassen (int n, n * n_matrix A, n * n_matrix B, n * n_matrix C)
{
if ( n <= threshold)
표준 행렬곱셈 알고리즘 C = A * B 계산
else {
A를 4개의 부분행렬로 분할
B를 4개의 부분행렬로 분할
Strassen 행렬곱셈 알고리즘으로 C = A * B 계산
}
}


- 표준 행렬곱셈 알고리즘

가로, 세로를 행렬로 만든 뒤 각각을 곱한다.

참고 자료

없음