알고리즘 - 합병정렬, 퀵정렬

소개글

알고리즘 - 합병정렬, 퀵정렬에 대한 보고서 자료입니다.

목차

1. 프로그램 소스
합병정렬(링크를 사용하는) : lec4-5, 퀵정렬(순환버전) : lec5-1 사용

CompareMeasure.java
MergeSortClass.java
QuickSortClass.java


2. 수행 결과

본문내용

e elements a[p],..., a[q] which reside in
// the global array a[1:n] into ascending order; a[n+1]
// is considered to be defined and must be >= all the
// elements in a[1:n].
{
if (p < q) { // If there are more than one element
// divide P into two subproblems.
int j = Partition(a, p, q + 1);
// j is the position of the
// partitioning element.
// Solve the subproblems.
QuickSort(p, j - 1);
QuickSort(j + 1, q);
// There is no need for combining solutions.
}
}
int Partition(int a[], int m, int p)
// Within a[m], a[m+1],..., a[p-1] the elements
// are rearranged in such a manner that if
// initially t==a[m], then after completion
// a[q]==t for some q between m and p-1, a[k]<=t
// for m<=k=t for q {
// int v=a[m]; int i=m, j=p;
int v = a[m];
int i = m, j = p;
do {
do
i++;
while (a[i] < v);
do
j--;
while (a[j] > v);
if (i < j)
Interchange(a, i, j);
} while (i < j);
a[m] = a[j];
a[j] = v;
return (j);
}
void Interchange(int a[], int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
2. 수행 결과
<성능측정표>
인자 수
1,000
5,000
10,000
20,000
50,000
100,000
합병정렬
1.587
1.933
1.608
3.397
9.460
21.620
퀵 정렬
0.564
1.921
1.238
2.579
7.031
14.160
<성능 측정에 따른 그래프>

키워드

java,   자바,   합병정렬,   퀵정렬,   정렬,   소스코드,   프로그램 소스,   알고리즘