Banzi

■ Homework #2 개요
“ 버블정렬 알고리즘과 빠른정렬 알고리즘을 프로그래밍 한다 .”
“ 키의 개수 (n) 가 변화함에 따른 소팅 속도를 실제 측정하고 비교한다 .”
 
■ 과제 수행 프로세스
Ⅰ . 정확한 소팅 속도 측정을 위해 랜덤수를 미리 생성하여 file 형태로 만든다 .
Ⅱ . 이 파일을 기준으로 버블정렬과 빠른정렬 알고리즘을 수행하여 소팅 속도를 측정한다 .
( 실험 데이터의 정확도를 높이기 위해 5 개의 파일에 대해 실험을 반복한다 .)
Ⅲ . 구현 소팅 알고리즘은 교재의 의사코드를 기준으로 구현한다 .
Ⅳ . 결과로 나온 소팅 속도를 n 이 변화함에 따라 어떻게 달라지는 비교 분석한다 .
 
■ 과제 수행 프로그램 구성
▲ 랜덤 수 생성 프로그램 (1000000 개 ) - console 형태로 구현
▲ 정렬 방법 및 n 에 따른 소팅 속도 측정 프로그램 - MFC(Win32) 형태로 구현
▲ 코드 사용 언어 : C/C++, MFC(Microsoft Foundation Class) 라이브러리
 
■ 프로그램 구현 코드 내용
▲ 랜덤 수 생성 프로그램

//RandomNumMake
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void main()
{
	int i, number;
	FILE *f;
	
	f = fopen("data.txt", "w");
	
	int *s;
	s = (int*)malloc(sizeof(int)*1000000);

	srand(time(NULL));
	for(i=0;i<1000000; i++)
	{
		fprintf(f, "%d ", rand() % 1000000);
	}

	fclose(f);
}

▲ 정렬속도 측정 프로그램(버블정렬, 퀵정렬)

//알고리즘 소스 코드(퀵 정렬: partition, quicksort / 버블 정렬: bubble_sort)
void partition(int *s, int low, int high, int *pivotpoint)
{
	int i, j;
	int temp;
	int pivotitem;

	pivotitem = *(s+low);
	j = low;
	for(i=low+1; i<=high; i++)
	{
		if(*(s+i) < pivotitem) {
			j++;
			temp = *(s+i);
			*(s+i) = *(s+j);
			*(s+j) = temp;
		}
	}
	*pivotpoint = j;
	temp = *(s+low);
	*(s+low) = *(s+(*pivotpoint));
	*(s+(*pivotpoint)) = temp;
}

void quicksort(int *s, int low, int high)
{
	int pivotpoint;

	pivotpoint = low;
    
	if(high>low)
	{
		partition(s,low, high, &pivotpoint);
		quicksort(s,low, pivotpoint-1);
		quicksort(s,pivotpoint + 1, high);
	}
}

void bubble_sort(int *s, int n)
{
	int i, j, temp;
	for(i=0; i<n-1; i++)
	{
		for(j=1; j<n-i; j++)
		{
			if(*(s+(j-1))>*(s+j))
			{
				temp = *(s+(j-1));
				*(s+(j-1)) = *(s+j);
				*(s+j) = temp;
			}
		}
	}
}

▲ 메인 프로그램 소스 코드

//void CNEW_HWDlg::OnButtonRun() 
clock_t start,end;
int i, j, n, number;
int RepeatO1, RepeatO2, RepeatO3;
int *s;
FILE * file;

file = fopen("data.txt", "r");

s = (int*)malloc(sizeof(int)*MAXDATACNT);

for(i=0; i<MAXDATACNT; i++)
{
	fscanf(file, "%d ", &number);
	*(s+i) = number;
}

m_ctrlList.DeleteAllItems();

UpdateData(TRUE);

if(m_Repeat==1) {
	RepeatO1 = m_RepeatO1;
	RepeatO2 = m_RepeatO2;
	RepeatO3 = m_RepeatO3;
}
else {
	RepeatO1 = m_RepeatX1;
	RepeatO2 = m_RepeatX1;
	RepeatO3 = m_RepeatX1;
}

for(n=RepeatO1,i=0; n<=RepeatO2; n+=RepeatO3, i++)
{		
	// start = clock();
	DWORD dwStartTime = timeGetTime();
	if(m_SortMethodSel==0)			// 버블정렬 선택
		bubble_sort(s,n);
	else if(m_SortMethodSel==1)	// 퀵졍렬 선택
		quicksort(s,0,n-1);	
	// end = clock();
	DWORD dwEndTime = timeGetTime();
		
	str.Format("%d", n);
	m_ctrlList.InsertItem(i, str, NULL);
	str.Format("%d", dwEndTime-dwStartTime);
	m_ctrlList.SetItemText(i, 1, str);
}	
free(s);
fclose(file);

■ 프로그램 실행 화면 및 결과
▲ 메인 프로그램 화면

〓〓〓 THE END〓〓〓