MIPS Programming을 이용한 Number Counting과 Merge Sorting, 그리고 두 다항식의 곱을 표현

소개

MIPS Programming을 이용한 Number Counting과 Merge Sorting, 그리고 두 다항식의 곱을 표현하는 문제를 프로그래밍하고 결과를 분석

목차

[Problem #1] Polynomial multiplication
① Program explain
② Source code with comments
③ Program result
④ Discussion

[Problem #2] Counting and Sorting
1. Number Counting
① Program explain
② Source code with comments.text
③ Program result
④ Discussion

2. Merge Sorting
① Program explain
② Source code with comments
③ Program result
④ Discussion

본문내용

2. Merge Sorting
If you solve above problem, you can know what numbers are above box. Ignoring overlapped numbers, you can sort above numbers in ascending order. Among sorting algorithms, you must use the merge sort algorithm. Verify the operation of your program showing the result of sorting on console.
① Program explain
일단 Merge sort에 대해서 알아야 한다.
1. Merge sort 개념
- 이미 순서적으로 배열된 두 개의 파일에서 레코드의 배열 순서에 따라 차례로 한 레코드씩 가져다 비교하여 작은 키 값을 가지는 레코드를 새로운 병합 파일에 출력하고, 작은 레코드를 가져온 파일에서 다음 순서의 레코드를 가져와 이전에 비교한 큰 키 값을 가진 레코드와 비교하는 과정을 반복 수행하므로 완전히 순서적으로 배열된 한 개의 파일을 만드는 것을 의미
- Merge sort(합병 정렬)은 Quick sort과 마찬가지로 분할 정복 방식의 알고리즘
- Quick sort에서는 분할되는 두 부분배열의 크기가 다를 수도 있고 이것 때문에 최악의 성능이 O(n2)으로 되었는데 Merge sort에서는 두 부분배열의 크기가 항상 같게 분할 됨.
- Merge sort의 수행시간은 최악의 경우에도 O(NlogN)
- Merge sort은 별도의 임시 기억장소(배열)가 필요
- 실제로는 수행시간이 많이 걸리며, 외부정렬에 주로 활용
 2. Merge sort 방법
(1) Merge sort은 전형적인 분할 정복 방법의 예 분할 정복 방법은 순환적으로 문제를 푸는 방법으로서 주어진 문제를 여러 개의 소문제로 분할하여 이 소문제를 순환적으로 푼 후 이들의 해를 결합하여 원래 문제의 해를 구하는 방식

참고자료

· 없음