[자료구조 자료구조] Sorting(Insertion, Quick, Merge)
*치*
다운로드
장바구니
소개글
C로 구현한 Sorting 소스입니다.3가지 방법으로 Sorting을 하고, 정렬시간을 재는 과제입니다.
Insertion Sorting(선택정렬), Quick Sorting(퀵정렬), Merge Sorting(합병 정렬)
결과를 파워포인터 파일로 그래프를 그려서 첨부하였습니다.
====== 과제 요구 사항 ======
Insertion sorting, quick sorting, merge sorting algorithm 성능 비교 그래프 그리기(엑셀에서 그렸습니다.)
X축 : 입력개수 (10, 100, 1000, 10000, 100000)
Y축 : sorting에 걸리는 시간
각 입력에 대한 실험은 30회
10개의 unsorted(random) integer를 만들고 insertion, quick, merge sorting을 수행한 평균값을 기록
지난 숙제였던 Insertion sorting과 quick sorting에 대한 실험도 같은 환경에서 다시 수행
목차
총 9파일결과그래프.ppt
과제설명.ppt
Sorting.c
Sorting.dsp
Sorting.dsw
Sorting.exe
Sorting.ncb
Sorting.opt
Sorting.plg
본문내용
======= 소스 일부 내용 =======void insertion_sort(int data[]);
void quick_sort(int data[], int start, int end);
void merge_sort(int data[], int low, int high);
void print_data(int data[]);
void swap(int data[], int i, int j);
void main() {
int i, count;
int *data_original; // 원본 입력 데이터 배열
int *data_copy; // 입력 데이터 배열
clock_t start, stop; // 시간을 측정하기 위한 시작, 멈춤 시간 변수
double insertion_duration=0; // insertion sort 측정 시간
double quick_duration=0; // quick sort 측정 시간
double merge_duration=0; // merge sort 측정 시간
srand((unsigned)time(NULL));
// 설정한 루프 횟수 만큼 측정한다.
for(count=0; count<MAX_LOOP; count++) {
data_original = (int *)malloc(sizeof(int) * MAX_INPUT_NUMBER);
data_copy = (int *)malloc(sizeof(int) * MAX_INPUT_NUMBER);
// 데이터 배열에 랜덤한 값을 넣는다.
for(i=0; i<MAX_INPUT_NUMBER; i++) data_original[i] = data_copy[i] = rand()%10;
// printf("=================== Original Data ===================\n");
// print_data(data_original);
start = clock(); // 시작 시간
insertion_sort(data_copy); // insertion sort 실행
stop = clock(); // 멈춘 시간
insertion_duration += ((double) (stop-start))/CLK_TCK; // 측정된 시간을 합한다.
// printf("\n\n=============== Insertion Sorting Data ===============\n");
// print_data(data_copy);
for(i=0; i<MAX_INPUT_NUMBER; i++) data_copy[i] = data_original[i];
start = clock(); // 시작 시간
quick_sort(data_copy, 0, MAX_INPUT_NUMBER-1); // quick sort 실행
stop = clock(); // 멈춘 시간
quick_duration += ((double) (stop-start))/CLK_TCK; // 측정된 시간을 합한다.
// printf("\n\n================= Quick Sorting Data ======<font color=aaaaff>..</font>
참고 자료
없음압축파일 내 파일목록
결과그래프.ppt
Sorting.c
Sorting.dsp
Sorting.dsw
Sorting.exe
Sorting.ncb
Sorting.opt
Sorting.plg
과제설명.ppt
Sorting.c
Sorting.dsp
Sorting.dsw
Sorting.exe
Sorting.ncb
Sorting.opt
Sorting.plg
과제설명.ppt