목차
Ⅰ.문 제··············1
Ⅱ.Program············1 ~ 6
1)기본 설명············1
2)주요소스 및 설명··········1 ~ 6
Ⅲ.프로그램 실행화면··········7 ~ 9
Ⅳ.결 과··············10 ~ 11
Ⅴ.참고문헌 및 사이트········11
Ⅱ.Program············1 ~ 6
1)기본 설명············1
2)주요소스 및 설명··········1 ~ 6
Ⅲ.프로그램 실행화면··········7 ~ 9
Ⅳ.결 과··············10 ~ 11
Ⅴ.참고문헌 및 사이트········11
본문내용
< list[right] ) )
// 중간 값 list[mid]
SWAP(list[left], list[mid], temp);
// 중간값 list[left]
pivot = list[left]; /* 피벗설정*/
do {
do
low++;
/* 왼쪽 리스트에서 피벗보다 큰 레코드선택*/
while(low<=right &&list[low]
do
high--;
/* 오른쪽 리스트에서 피벗보다 작은 레코드선택*/
while(high>=left && list[high]>pivot);
if(low
} while(low
SWAP(list[left], list[high], temp); /* 인텍스j가 가리키는 레코드와 피벗교환*/
return high;
}
void quickSort(int list[], int left, int right)
{
if(left
int q=partition(list, left, right);
quickSort(list, left, q-1); /* 왼쪽부분 리스트를 퀵 정렬*/
quickSort(list, q+1, right); /* 오른쪽부분 리스트를 퀵 정렬*/
}
}
- Merge 정렬
int sorted[1000000];
/* I는 정렬된 왼쪽리스트에 대한 인덱스
j는 정렬된 오른쪽리스트에 대한 인덱스
k는 정렬될 리스트에 대한인덱스*/
void merge(int list[], int left, int mid, int right)
{
int i, j, k, l;
i=left; j=mid+1; k=left;
/* 분할정렬된list의합병*/
while(i<=mid && j<=right){
if(list[i]<=list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if(i>mid) /* 남아있는레코드의일괄복사*/
for(l=j; l<=right; l++)
sorted[k++] = list[l];
else /* 남아있는레코드의일괄복사*/
for(l=i; l<=mid; l++)
sorted[k++] = list[l];
/* 배열sorted[]의리스트를배열list[]로재복사*/
for(l=left; l<=right; l++)
list[l] = sorted[l];
}
void mergeSort(int list[], int left, int right)
{
int mid;
if(left
mid = (left+right)/2; // 리스트의 균등분할
mergeSort(list, left, mid); // 부분리스트 정렬
mergeSort(list, mid+1, right); // 부분리스트 정렬
merge(list, left, mid, right); // 합병
}
}
- Sort별 속도측정
thou=makeRand(1000); // 난수 1000개 생성
tenThou=makeRand(10000); // 난수 10000개 생성
hundThou=makeRand(100000); // 난수 100000개 생성
start=clock( ); // 정렬별 프로그램 동작 속도 측정을 위한 clock() 사용
Sort(thou, 1000); // 정렬함수 호출
stop=clock( ); // clock() 정지
duration=(double)(stop-start); // 시간차 확인하여 수행시간 측정
Ⅲ. 프로그램 실행화면 (1번 정렬, 2번 난수계산)
■ InsertionSort
■ BubbleSort
■ HeapSort
■ QuickSort
■ MergeSort
Ⅳ. 결 과
아무래도 정렬 알고리즘은 조건에 맞게 사용되어야 최적의 효과를 발휘할 수 있다.
이번 프로그램에서의 목적은 정렬방법에 알고리즘 흐름 확인과 동등한 조건에 상황처리
속도를 확인하는 것이다. 정렬별 속도처리를 확인하겠다.
- 5가지 정렬 알고리즘의 3가지 난수 집합(1000개, 10000개, 100000개)에 대한 수행 속도
Sort
Duration
Insertion
Bubble
Heap
Quick
Merge
1000
0
0
0
0
0
10000
188
547
0
16
0
100000
20109
56063
31
15
31
위 표에서 확인 할 수 있듯이1000개의 변수에 대해서는 모두 동일한 속도를 보여주고 있다.
그러나 만개 이상 올라가면서 점차 처리속도의 차이의 변화를 보여주고 있다. 또한, 난수가
상승 할수록 특정 정렬 알고리즘들은 기하급수적으로 처리속도가 증가함을 확인 할 수 있다
1000개를 수행한 순서
Insertion = Bubble = Heap = Quick = erge
10000개를 수행한 순서
Bubble > Insert = Heap = Quick = Merge
100000개를 수행한 순서
Bubble > Insertion > Heap = Quick = Merge
- 각 정렬 알고리즘의 대한 수행시간 그래프
Bubble / Insertion 정렬은 시간복잡도의 의해 데이터의 양이 상승할수록 그 수행 시간도
비례 한다. 다만 Insertion 경우는 이미 정렬된 배열에 집어넣는 방식으로 Bubble보다는
처리속도가 빨랐다.
Heap, quick, merge sort는 시간 복잡도의 의해 결과에서 확인 할 수 있듯이 데이터양의
상승에도 빠른 처리속도를 보여주며, 결과에서 확인 할 수 있듯이 적은 데이터양의 처리
경우에는 어떤 정렬 알고리즘을 사용하여도 무리가 없겠지만 데이터양이 상승에 있어서
조금씩 처리 속도의 차이를 가지고 있어 시스템 설계 시 시스템에 맞는 효율적인 시간 복잡도를
가지는 알고리즘을 사용해야 된다.
Ⅴ. 참고 문헌 및 사이트
· 이상진『열혈강의 자료구조』프리렉, 2010
· 김상형『혼자연구하는 C, C++』와우북스, 2009
· 이지영『C로 배우는 쉬운 자료구조』프리렉, 2005
· 위키백과 http://ko.wikipedia.org
// 중간 값 list[mid]
SWAP(list[left], list[mid], temp);
// 중간값 list[left]
pivot = list[left]; /* 피벗설정*/
do {
do
low++;
/* 왼쪽 리스트에서 피벗보다 큰 레코드선택*/
while(low<=right &&list[low]
high--;
/* 오른쪽 리스트에서 피벗보다 작은 레코드선택*/
while(high>=left && list[high]>pivot);
if(low
return high;
}
void quickSort(int list[], int left, int right)
{
if(left
quickSort(list, left, q-1); /* 왼쪽부분 리스트를 퀵 정렬*/
quickSort(list, q+1, right); /* 오른쪽부분 리스트를 퀵 정렬*/
}
}
- Merge 정렬
int sorted[1000000];
/* I는 정렬된 왼쪽리스트에 대한 인덱스
j는 정렬된 오른쪽리스트에 대한 인덱스
k는 정렬될 리스트에 대한인덱스*/
void merge(int list[], int left, int mid, int right)
{
int i, j, k, l;
i=left; j=mid+1; k=left;
/* 분할정렬된list의합병*/
while(i<=mid && j<=right){
if(list[i]<=list[j])
sorted[k++] = list[i++];
else
sorted[k++] = list[j++];
}
if(i>mid) /* 남아있는레코드의일괄복사*/
for(l=j; l<=right; l++)
sorted[k++] = list[l];
else /* 남아있는레코드의일괄복사*/
for(l=i; l<=mid; l++)
sorted[k++] = list[l];
/* 배열sorted[]의리스트를배열list[]로재복사*/
for(l=left; l<=right; l++)
list[l] = sorted[l];
}
void mergeSort(int list[], int left, int right)
{
int mid;
if(left
mergeSort(list, left, mid); // 부분리스트 정렬
mergeSort(list, mid+1, right); // 부분리스트 정렬
merge(list, left, mid, right); // 합병
}
}
- Sort별 속도측정
thou=makeRand(1000); // 난수 1000개 생성
tenThou=makeRand(10000); // 난수 10000개 생성
hundThou=makeRand(100000); // 난수 100000개 생성
start=clock( ); // 정렬별 프로그램 동작 속도 측정을 위한 clock() 사용
Sort(thou, 1000); // 정렬함수 호출
stop=clock( ); // clock() 정지
duration=(double)(stop-start); // 시간차 확인하여 수행시간 측정
Ⅲ. 프로그램 실행화면 (1번 정렬, 2번 난수계산)
■ InsertionSort
■ BubbleSort
■ HeapSort
■ QuickSort
■ MergeSort
Ⅳ. 결 과
아무래도 정렬 알고리즘은 조건에 맞게 사용되어야 최적의 효과를 발휘할 수 있다.
이번 프로그램에서의 목적은 정렬방법에 알고리즘 흐름 확인과 동등한 조건에 상황처리
속도를 확인하는 것이다. 정렬별 속도처리를 확인하겠다.
- 5가지 정렬 알고리즘의 3가지 난수 집합(1000개, 10000개, 100000개)에 대한 수행 속도
Sort
Duration
Insertion
Bubble
Heap
Quick
Merge
1000
0
0
0
0
0
10000
188
547
0
16
0
100000
20109
56063
31
15
31
위 표에서 확인 할 수 있듯이1000개의 변수에 대해서는 모두 동일한 속도를 보여주고 있다.
그러나 만개 이상 올라가면서 점차 처리속도의 차이의 변화를 보여주고 있다. 또한, 난수가
상승 할수록 특정 정렬 알고리즘들은 기하급수적으로 처리속도가 증가함을 확인 할 수 있다
1000개를 수행한 순서
Insertion = Bubble = Heap = Quick = erge
10000개를 수행한 순서
Bubble > Insert = Heap = Quick = Merge
100000개를 수행한 순서
Bubble > Insertion > Heap = Quick = Merge
- 각 정렬 알고리즘의 대한 수행시간 그래프
Bubble / Insertion 정렬은 시간복잡도의 의해 데이터의 양이 상승할수록 그 수행 시간도
비례 한다. 다만 Insertion 경우는 이미 정렬된 배열에 집어넣는 방식으로 Bubble보다는
처리속도가 빨랐다.
Heap, quick, merge sort는 시간 복잡도의 의해 결과에서 확인 할 수 있듯이 데이터양의
상승에도 빠른 처리속도를 보여주며, 결과에서 확인 할 수 있듯이 적은 데이터양의 처리
경우에는 어떤 정렬 알고리즘을 사용하여도 무리가 없겠지만 데이터양이 상승에 있어서
조금씩 처리 속도의 차이를 가지고 있어 시스템 설계 시 시스템에 맞는 효율적인 시간 복잡도를
가지는 알고리즘을 사용해야 된다.
Ⅴ. 참고 문헌 및 사이트
· 이상진『열혈강의 자료구조』프리렉, 2010
· 김상형『혼자연구하는 C, C++』와우북스, 2009
· 이지영『C로 배우는 쉬운 자료구조』프리렉, 2005
· 위키백과 http://ko.wikipedia.org
추천자료
- C 언어 프로그래밍
- 함수형 프로그래밍
- [C언어]프로그래밍(C언어)에 대한 PPT자료
- c로 배우는 프로그래밍 5장 이해점검
- C로 배우는 프로그래밍 기초 (2nd edition) - 4장 내용점검 문제
- 플로이드 알고리즘 (C로 구현)
- C로 배우는 프로그래밍 기초 1,2장 문제 풀이
- C로 배우는 프로그래밍 기초 Solution (chatper 1)
- 2008년 1학기 웹프로그래밍 중간시험과제물 A~C형(계산기)
- c로 배우는 프로그래밍 언어 2nd 6장 내용점검, 프로그래밍실습과제
- c로 배우는 프로그래밍 기초
- c로 배우는 프로그래밍 기초
- C로 배우는 프로그래밍 기초 2nd Chapter 01
- C로 배우는 프로그래밍 기초 2nd Chapter 8장 및 exchange sort 프로그래밍